Graph search algorithms are used to find specific nodes in a graph. These algorithms allow us to navigate through the graph and search for nodes that satisfy certain conditions. Let's explore some commonly used graph search algorithms.
- Depth-First Search (DFS): DFS explores as far as possible along each branch before backtracking. It traverses the graph using a stack and is often used to find connected components and detect cycles. Here's an example of DFS in Java:
TEXT/X-JAVA
1class Graph {
2 private int V;
3 private LinkedList<Integer>[] adjList;
4
5 Graph(int V) {
6 this.V = V;
7 adjList = new LinkedList[V];
8 for (int i = 0; i < V; i++) {
9 adjList[i] = new LinkedList<>();
10 }
11 }
12
13 void addEdge(int v, int w) {
14 adjList[v].add(w);
15 }
16
17 void DFS(int start) {
18 boolean[] visited = new boolean[V];
19 DFSUtil(start, visited);
20 }
21
22 void DFSUtil(int v, boolean[] visited) {
23 visited[v] = true;
24 System.out.print(v + " ");
25
26 for (int i : adjList[v]) {
27 if (!visited[i]) {
28 DFSUtil(i, visited);
29 }
30 }
31 }
32}xxxxxxxxxxclass Main { public static void main(String[] args) { // replace with your Java logic here }}OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
