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

Commit 7191e76

Browse files
author
Lord-of-Algorithms
committed
Implement graph traversal algorithms: DFS and BFS
1 parent dfe1b62 commit 7191e76

14 files changed

+567
-0
lines changed

‎src/graph/traversal/GraphTraversal.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package graph.traversal;
2+
3+
import java.util.List;
4+
5+
/**
6+
* Defines the framework for graph traversal algorithms.
7+
*/
8+
public interface GraphTraversal {
9+
10+
/**
11+
* Traverses the graph starting from the specified vertex.
12+
*/
13+
void traverse(UnweightedGraph graph, Vertex vertex);
14+
15+
/**
16+
* Retrieves the path taken during the traversal as a list of visited vertices.
17+
*/
18+
List<Vertex> getTraversalPath();
19+
20+
/**
21+
* Resets the traversal state, including marking all vertices as unvisited.
22+
*/
23+
void resetState();
24+
}

‎src/graph/traversal/UnweightedGraph.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package graph.traversal;
2+
3+
4+
/**
5+
* Represents an unweighted graph capable of adding edges and finding adjacent vertices.
6+
*/
7+
public interface UnweightedGraph {
8+
9+
/**
10+
* Adds an unweighted edge between two vertices in the graph.
11+
*
12+
* @param source The source vertex of the edge.
13+
* @param destination The destination vertex of the edge.
14+
*/
15+
void setEdge(Vertex source, Vertex destination);
16+
17+
/**
18+
* Finds an unvisited adjacent vertex to the given vertex.
19+
*
20+
* @param vertex The vertex for which to find an unvisited adjacent vertex.
21+
* @return An unvisited adjacent {@link Vertex} vertex if one exists, or null
22+
* if all adjacent vertices have been visited or there are no adjacent vertices.
23+
*/
24+
Vertex findUnvisitedAdjacent(Vertex vertex);
25+
}

‎src/graph/traversal/Vertex.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package graph.traversal;
2+
3+
/**
4+
* Represents a vertex that can be visited during traversal.
5+
*/
6+
public interface Vertex {
7+
8+
/**
9+
* Marks this vertex as visited.
10+
*/
11+
void visit();
12+
13+
14+
/**
15+
* Checks if this vertex has been visited.
16+
*
17+
* @return true if the vertex has been visited, false otherwise.
18+
*/
19+
boolean isVisited();
20+
21+
/**
22+
* Resets the visited status of this vertex, marking it as unvisited.
23+
*/
24+
void resetVisitedStatus();
25+
}

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

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package graph.traversal.algorithms;
2+
3+
import graph.traversal.GraphTraversal;
4+
import graph.traversal.UnweightedGraph;
5+
import graph.traversal.Vertex;
6+
7+
import java.util.*;
8+
9+
/**
10+
* Implements the Breadth-First Search (BFS) traversal algorithm for graphs.
11+
*/
12+
public class BfsTraversal implements GraphTraversal {
13+
14+
private final List<Vertex> traversalPath;
15+
16+
public BfsTraversal() {
17+
traversalPath = new ArrayList<>();
18+
}
19+
20+
@Override
21+
public void traverse(UnweightedGraph graph, Vertex vertex) {
22+
Queue<Vertex> queue = new LinkedList<>();
23+
vertex.visit();
24+
traversalPath.add(vertex);
25+
queue.add(vertex);
26+
while (!queue.isEmpty()) {
27+
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);
33+
}
34+
}
35+
}
36+
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+
50+
@Override
51+
public String toString() {
52+
return "BFS";
53+
}
54+
}

‎src/graph/traversal/algorithms/DfsRecursiveTraversal.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.traversal.GraphTraversal;
4+
import graph.traversal.UnweightedGraph;
5+
import graph.traversal.Vertex;
6+
7+
import java.util.ArrayList;
8+
import java.util.Collections;
9+
import java.util.List;
10+
11+
/**
12+
* Implements the recursive Depth-First Search (DFS) traversal algorithm for graphs.
13+
*/
14+
public class DfsRecursiveTraversal implements GraphTraversal {
15+
16+
private final List<Vertex> traversalPath;
17+
18+
public DfsRecursiveTraversal() {
19+
traversalPath = new ArrayList<>();
20+
}
21+
22+
@Override
23+
public void traverse(UnweightedGraph graph, Vertex vertex) {
24+
recursiveDfs(graph, vertex);
25+
}
26+
27+
/**
28+
* Recursively performs depth-first search starting from the given vertex entity.
29+
*/
30+
private void recursiveDfs(UnweightedGraph graph, Vertex vertex) {
31+
vertex.visit();
32+
traversalPath.add(vertex);
33+
34+
// Recursively visit all unvisited adjacent vertices
35+
Vertex adjacent;
36+
while ((adjacent = graph.findUnvisitedAdjacent(vertex)) != null) {
37+
recursiveDfs(graph, adjacent);
38+
}
39+
}
40+
41+
@Override
42+
public List<Vertex> getTraversalPath() {
43+
return Collections.unmodifiableList(traversalPath);
44+
}
45+
46+
@Override
47+
public void resetState() {
48+
for (Vertex v : traversalPath) {
49+
v.resetVisitedStatus();
50+
}
51+
traversalPath.clear();
52+
}
53+
54+
@Override
55+
public String toString() {
56+
return "Recursive DFS";
57+
}
58+
}

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

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package graph.traversal.algorithms;
2+
3+
import graph.traversal.GraphTraversal;
4+
import graph.traversal.UnweightedGraph;
5+
import graph.traversal.Vertex;
6+
7+
import java.util.*;
8+
9+
/**
10+
* Implements the Depth-First Search (DFS) traversal algorithm for graphs.
11+
*/
12+
public class DfsTraversal implements GraphTraversal {
13+
14+
private final List<Vertex> traversalPath;
15+
16+
public DfsTraversal() {
17+
traversalPath = new ArrayList<>();
18+
}
19+
20+
@Override
21+
public void traverse(UnweightedGraph graph, Vertex vertex) {
22+
Deque<Vertex> stack = new ArrayDeque<>();
23+
vertex.visit();
24+
traversalPath.add(vertex);
25+
stack.push(vertex);
26+
while (!stack.isEmpty()) {
27+
Vertex adjacent = graph.findUnvisitedAdjacent(stack.peek());
28+
if (adjacent == null) {
29+
stack.pop();
30+
} else {
31+
adjacent.visit();
32+
traversalPath.add(adjacent);
33+
stack.push(adjacent);
34+
}
35+
}
36+
}
37+
38+
@Override
39+
public List<Vertex> getTraversalPath() {
40+
return Collections.unmodifiableList(traversalPath);
41+
}
42+
43+
@Override
44+
public void resetState() {
45+
for (Vertex v : traversalPath) {
46+
v.resetVisitedStatus();
47+
}
48+
traversalPath.clear();
49+
}
50+
51+
@Override
52+
public String toString() {
53+
return "DFS";
54+
}
55+
}

‎src/graph/traversal/main/GraphFactory.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package graph.traversal.main;
2+
3+
import graph.traversal.UnweightedGraph;
4+
5+
/**
6+
* Factory for creating instances of {@link UnweightedGraph} based on the specified graph representation.
7+
*/
8+
class GraphFactory {
9+
static UnweightedGraph createGraph(GraphRepresentation representation, GraphVertex[] vertices) {
10+
switch (representation) {
11+
case MATRIX:
12+
return new UndirectedUnweightedMatrixGraph(vertices);
13+
case LIST:
14+
return new UndirectedUnweightedListGraph(vertices);
15+
default:
16+
throw new IllegalArgumentException("Unknown representation method: " + representation);
17+
}
18+
}
19+
}

‎src/graph/traversal/main/GraphRepresentation.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package graph.traversal.main;
2+
3+
/**
4+
* Enumerates the possible graph representations.
5+
*/
6+
public enum GraphRepresentation {
7+
/**
8+
* Represents a graph using an adjacency matrix.
9+
*/
10+
MATRIX,
11+
/**
12+
* Represents a graph using an adjacency list.
13+
*/
14+
LIST
15+
}

‎src/graph/traversal/main/GraphTraversalFactory.java‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package graph.traversal.main;
2+
3+
import graph.traversal.algorithms.BfsTraversal;
4+
import graph.traversal.algorithms.DfsRecursiveTraversal;
5+
import graph.traversal.algorithms.DfsTraversal;
6+
import graph.traversal.GraphTraversal;
7+
8+
/**
9+
* Factory for creating instances of {@link GraphTraversal} based on the specified traversal method.
10+
*/
11+
class GraphTraversalFactory {
12+
static GraphTraversal createTraversal(TraversalMethod method) {
13+
switch (method) {
14+
case DFS:
15+
return new DfsTraversal();
16+
case DFS_RECURSIVE:
17+
return new DfsRecursiveTraversal();
18+
case BFS:
19+
return new BfsTraversal();
20+
default:
21+
throw new IllegalArgumentException("Unknown traversal method: " + method);
22+
}
23+
}
24+
}

‎src/graph/traversal/main/GraphVertex.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package graph.traversal.main;
2+
3+
import graph.traversal.Vertex;
4+
5+
import java.util.Objects;
6+
7+
/**
8+
* Represents a vertex in a graph.
9+
*/
10+
class GraphVertex implements Vertex {
11+
12+
private final String label;
13+
private boolean isVisited;
14+
15+
GraphVertex(String label) {
16+
this.label = label;
17+
}
18+
19+
@Override
20+
public void visit() {
21+
isVisited = true;
22+
}
23+
24+
@Override
25+
public boolean isVisited() {
26+
return isVisited;
27+
}
28+
29+
@Override
30+
public void resetVisitedStatus() {
31+
isVisited = false;
32+
}
33+
34+
@Override
35+
public boolean equals(Object o) {
36+
if (this == o) return true;
37+
if (o == null || getClass() != o.getClass()) return false;
38+
GraphVertex graphVertex = (GraphVertex) o;
39+
return Objects.equals(label, graphVertex.label);
40+
}
41+
42+
@Override
43+
public int hashCode() {
44+
return Objects.hash(label);
45+
}
46+
47+
@Override
48+
public String toString() {
49+
return label;
50+
}
51+
}

0 commit comments

Comments
 (0)