🌐 AI搜索 & 代理 主页
Skip to content

Commit 4665f71

Browse files
author
Lord-of-Algorithms
committed
Update graph traversal algorithms: streamline file structure, rename classes, and enhance readability
1 parent 2bddacb commit 4665f71

20 files changed

+312
-279
lines changed

‎src/graph/Graph.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package graph;
2+
3+
/**
4+
* Represents a general graph structure.
5+
* It serves as a base interface that other specific
6+
* graph interfaces and classes can extend or implement
7+
* to provide more complex behaviors
8+
* such as adding edges and querying graph properties.
9+
*/
10+
public interface Graph {
11+
/**
12+
* Adds a vertex to the graph.
13+
*/
14+
void addVertex(Vertex vertex);
15+
}

src/graph/traversal/main/GraphRepresentation.java renamed to src/graph/GraphRepresentation.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package graph.traversal.main;
1+
package graph;
22

33
/**
44
* Enumerates the possible graph representations.

‎src/graph/UnweightedGraph.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package graph;
2+
3+
4+
/**
5+
* Represents an unweighted graph capable of adding edges.
6+
*/
7+
public interface UnweightedGraph extends Graph {
8+
/**
9+
* Adds an unweighted edge between two vertices in the graph.
10+
*
11+
* @param source The source vertex of the edge.
12+
* @param destination The destination vertex of the edge.
13+
*/
14+
void setEdge(Vertex source, Vertex destination);
15+
}

‎src/graph/Vertex.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package graph;
2+
3+
/**
4+
* Represents a vertex in a graph. This interface is a marker interface, defining the type for objects
5+
* that can be used as vertices in graph data structures.
6+
*/
7+
public interface Vertex {
8+
}

‎src/graph/VertexImpl.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package graph;
2+
3+
import java.util.Objects;
4+
5+
/**
6+
* A concrete implementation of the {@link Vertex} interface that uses a string label to uniquely identify
7+
* each vertex. This class provides methods to support equality checks, hash code generation, and a string
8+
* representation which are essential for effectively using vertices in various graph-related operations.
9+
*/
10+
public class VertexImpl implements Vertex {
11+
12+
private final String label;
13+
14+
/**
15+
* Constructs a new vertex with the specified label.
16+
*/
17+
public VertexImpl(String label) {
18+
if (label == null) {
19+
throw new IllegalArgumentException("Label cannot be null.");
20+
}
21+
this.label = label;
22+
}
23+
24+
/**
25+
* Determines whether the specified object is equal to this vertex.
26+
* Two vertices are considered equal if they have the same label.
27+
*/
28+
@Override
29+
public boolean equals(Object o) {
30+
if (this == o) return true;
31+
if (o == null || getClass() != o.getClass()) return false;
32+
VertexImpl that = (VertexImpl) o;
33+
return Objects.equals(label, that.label);
34+
}
35+
36+
/**
37+
* Returns a hash code value for this vertex.
38+
*/
39+
@Override
40+
public int hashCode() {
41+
return Objects.hash(label);
42+
}
43+
44+
/**
45+
* Returns a string representation of this vertex.
46+
*/
47+
@Override
48+
public String toString() {
49+
return label;
50+
}
51+
}

‎src/graph/VertexUtil.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package graph;
2+
3+
import java.util.Map;
4+
5+
public class VertexUtil {
6+
7+
private VertexUtil() {
8+
// Prevents instantiation of utility class.
9+
}
10+
11+
// Helper method to find a vertex by its index
12+
public static Vertex getVertexByIndex(
13+
Map<Vertex, Integer> vertexIndexMap,
14+
Integer index
15+
) {
16+
for (Map.Entry<Vertex, Integer> entry : vertexIndexMap.entrySet()) {
17+
if (index.equals(entry.getValue())) {
18+
return entry.getKey();
19+
}
20+
}
21+
return null;
22+
}
23+
}

‎src/graph/traversal/UnweightedGraph.java‎

Lines changed: 0 additions & 25 deletions
This file was deleted.

‎src/graph/traversal/Vertex.java‎

Lines changed: 0 additions & 25 deletions
This file was deleted.

‎src/graph/traversal/algorithms/BaseGraphTraversal.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package graph.traversal.algorithms;
2+
3+
import graph.Vertex;
4+
import graph.traversal.graph.ExplorableGraph;
5+
6+
import java.util.*;
7+
8+
/**
9+
* Base class for graph traversal algorithms. This class provides common functionalities
10+
* needed for traversing a graph, such as marking vertices as visited and tracking the
11+
* traversal path.
12+
*/
13+
abstract class BaseGraphTraversal implements GraphTraversal {
14+
15+
private final Set<Vertex> visitedStatusSet;
16+
private final List<Vertex> traversalPath;
17+
18+
BaseGraphTraversal() {
19+
visitedStatusSet = new HashSet<>();
20+
traversalPath = new ArrayList<>();
21+
}
22+
23+
/**
24+
* Finds an unvisited neighbor of the specified vertex in the given graph.
25+
*
26+
* @param vertex The vertex whose unvisited neighbor is to be found.
27+
* @return The first unvisited neighbor of the vertex, or null if all neighbors have been visited.
28+
*/
29+
Vertex findUnvisitedNeighbor(ExplorableGraph graph, Vertex vertex) {
30+
List<Vertex> neighbors = graph.getNeighbors(vertex);
31+
for (Vertex v : neighbors) {
32+
if (!isVisited(v)) {
33+
return v;
34+
}
35+
}
36+
return null;
37+
}
38+
39+
private boolean isVisited(Vertex vertex) {
40+
return visitedStatusSet.contains(vertex);
41+
}
42+
43+
protected void visit(Vertex vertex) {
44+
visitedStatusSet.add(vertex);
45+
traversalPath.add(vertex);
46+
}
47+
48+
@Override
49+
public List<Vertex> getTraversalPath() {
50+
return Collections.unmodifiableList(traversalPath);
51+
}
52+
53+
@Override
54+
public void resetState() {
55+
visitedStatusSet.clear();
56+
traversalPath.clear();
57+
}
58+
}

‎src/graph/traversal/algorithms/BfsTraversal.java‎

Lines changed: 13 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -1,52 +1,31 @@
11
package graph.traversal.algorithms;
22

3-
import graph.traversal.GraphTraversal;
4-
import graph.traversal.UnweightedGraph;
5-
import graph.traversal.Vertex;
3+
import graph.Vertex;
4+
import graph.traversal.graph.ExplorableGraph;
65

7-
import java.util.*;
6+
import java.util.LinkedList;
7+
import java.util.Queue;
88

99
/**
10-
* Implements the Breadth-First Search (BFS) traversal algorithm for graphs.
10+
* Implements the Breadth-First Search (BFS) traversal algorithm for graph.
1111
*/
12-
public class BfsTraversal implements GraphTraversal {
13-
14-
private final List<Vertex> traversalPath;
15-
16-
public BfsTraversal() {
17-
traversalPath = new ArrayList<>();
18-
}
12+
public class BfsTraversal extends BaseGraphTraversal {
1913

2014
@Override
21-
public void traverse(UnweightedGraph graph, Vertex vertex) {
15+
public void traverse(ExplorableGraph graph, Vertex startVertex) {
2216
Queue<Vertex> queue = new LinkedList<>();
23-
vertex.visit();
24-
traversalPath.add(vertex);
25-
queue.add(vertex);
17+
visit(startVertex);
18+
queue.add(startVertex);
2619
while (!queue.isEmpty()) {
2720
Vertex head = queue.remove();
28-
Vertex adjacent;
29-
while ((adjacent = graph.findUnvisitedAdjacent(head)) != null) {
30-
adjacent.visit();
31-
traversalPath.add(adjacent);
32-
queue.add(adjacent);
21+
Vertex unvisitedNeighbor;
22+
while ((unvisitedNeighbor = findUnvisitedNeighbor(graph, head)) != null) {
23+
visit(unvisitedNeighbor);
24+
queue.add(unvisitedNeighbor);
3325
}
3426
}
3527
}
3628

37-
@Override
38-
public List<Vertex> getTraversalPath() {
39-
return Collections.unmodifiableList(traversalPath);
40-
}
41-
42-
@Override
43-
public void resetState() {
44-
for (Vertex v : traversalPath) {
45-
v.resetVisitedStatus();
46-
}
47-
traversalPath.clear();
48-
}
49-
5029
@Override
5130
public String toString() {
5231
return "BFS";

0 commit comments

Comments
 (0)