Graph traversal algorithms are used to explore or visit all the vertices of a graph. They are essential for understanding the structure and connectivity of a graph. Two commonly used graph traversal algorithms are depth-first search (DFS) and breadth-first search (BFS).
Depth-First Search (DFS):
In DFS, we start at a given vertex (usually called the source vertex) and explore as far as possible along each branch before backtracking. This means that we go depth-first, exploring vertices in the order they are encountered until we reach a dead end, and then backtrack to the previous vertex and explore another branch.
DFS can be implemented using either recursion or an explicit stack. Here is a recursive implementation of DFS in Java:
1public class DFS {
2 private boolean[] visited;
3 private Graph graph;
4
5 public DFS(Graph g) {
6 graph = g;
7 visited = new boolean[graph.getVertices()];
8 }
9
10 public void traverse(int source) {
11 visited[source] = true;
12 System.out.print(source + " ");
13
14 for (int neighbor : graph.getNeighbors(source)) {
15 if (!visited[neighbor]) {
16 traverse(neighbor);
17 }
18 }
19 }
20
21 public static void main(String[] args) {
22 int V = 6; // Number of vertices
23 Graph graph = new Graph(V);
24
25 // Add edges
26 graph.addEdge(0, 1);
27 graph.addEdge(0, 2);
28 graph.addEdge(1, 3);
29 graph.addEdge(2, 4);
30 graph.addEdge(3, 5);
31
32 DFS dfs = new DFS(graph);
33 dfs.traverse(0);
34 }
35}Breadth-First Search (BFS):
In BFS, we explore all the vertices at the current level before moving to the next level. This means that we visit all the neighbors of a vertex before visiting the neighbors' neighbors.
BFS can be implemented using a queue data structure. Here is an implementation of BFS in Java:
1import java.util.LinkedList;
2import java.util.Queue;
3
4public class BFS {
5 private boolean[] visited;
6 private Graph graph;
7
8 public BFS(Graph g) {
9 graph = g;
10 visited = new boolean[graph.getVertices()];
11 }
12
13 public void traverse(int source) {
14 Queue<Integer> queue = new LinkedList<>();
15 queue.offer(source);
16 visited[source] = true;
17
18 while (!queue.isEmpty()) {
19 int vertex = queue.poll();
20 System.out.print(vertex + " ");
21
22 for (int neighbor : graph.getNeighbors(vertex)) {
23 if (!visited[neighbor]) {
24 queue.offer(neighbor);
25 visited[neighbor] = true;
26 }
27 }
28 }
29 }
30
31 public static void main(String[] args) {
32 int V = 6; // Number of vertices
33 Graph graph = new Graph(V);
34
35 // Add edges
36 graph.addEdge(0, 1);
37 graph.addEdge(0, 2);
38 graph.addEdge(1, 3);
39 graph.addEdge(2, 4);
40 graph.addEdge(3, 5);
41
42 BFS bfs = new BFS(graph);
43 bfs.traverse(0);
44 }
45}