In this tutorial you will learn about implementation of Depth First Search in Java with example.
To traverse in trees we have traversal algorithms like inorder, preorder, postorder. Same way to traverse in graphs we have mainly two types of algorithms called DFS (Depth First Search) and BFS (Breadth First Search).
In Depth First Search traversal we try to go away from starting vertex into the graph as deep as possible. We may face the case that our search never ends because, unlike tree graph may contains loops. Since this reason we maintain a Boolean array which stores whether the node is visited or not.
Also Read: Breadth First Search (BFS) Java Program
Initially all vertices are marked as unvisited, that means Boolean array contain all zeros. DFS algorithm starts form a vertex “u” from graph. Starting with that vertex it considers all edges to other vertices from that vertex. While going when a new node encountered that corresponding node status in Boolean array will be changed to 1. That unvisited node becomes our new node and we again start our problem of DFS with that node. When we came to already visited node we should do backtracking. This entire process terminates when backtracking drag us to the start vertex where we started initially.
Depth First Search Example
Here initially no node visited we start DFS from node A.
Red color node represents node already visited.
Blue color node represents node not yet visited.
After visiting node A corresponding array value changed to 1.
Here after node A, node B visited.
Node C visited after node B and corresponding value in Boolean array changed to 1.
Node E visited and array updated in its correct position.
All nodes visited. But process of DFS not stopped here.
Now From D it tries to explore any non-visited node. But not able to find non-visited node from D. So it backtrack to node E.
Backtracking to node E from node D.
Next node E tries to explore non-visited vertex. But it not able to find non-visited vertex. So it backtrack to Vertex C.
Backtracking to Vertex C from Vertex E.
Now Vertex C also don’t have any non-visited vertex so it backtrack to Vertex B.
Backtracking to vertex B from vertex C.
Now vertex B do backtracking to vertex A since it don’t have any non-visited vertex.
Backtracking to Vertex A from Vertex B.
Now the termination condition occurred.
We can stop our DFS process because we reached where we started.
Note: When graph is not connected then we should check Boolean array that all nodes visited or not. If not visited then start DFS from that node. Here we will see the code which will run on disconnected components also.
Depth First Search (DFS) Java Program
Below program shows implementation of dfs in Java.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
import java.util.*; public class DFS { //no of vertices. int V; //we are building graph using adjacency list. //so we should have linked list for every node and store adjacent nodes of that node in that list LinkedList<Integer> adjList[]; // constructor DFS(int v) { V = v; adjList = new LinkedList[v]; for (int i=0; i<v; ++i) { adjList[i] = new LinkedList(); //it will create empty list for every node } } //adding edges to graph void addEdgesToGraph(int v, int u) { adjList[v].add(u); //here it will add vertex to adjacency list of another vertex so that edge can be added to graph. } // depth first traversal is used by depth first search. it will traverse one strong component completely void DFTraversal(int v,int visited[]) { visited[v] = 1; System.out.print(v + " "); Iterator<Integer> i = adjList[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (visited[n]==0) DFTraversal(n, visited); } } //depth first search will call depth fist traversal on disconnected components. it will keep track of visited[] array. void DFSearch(int v) { int visited[] = new int[V]; DFTraversal(v, visited); for (int i=1;i<V;i++) { if(visited[i]==0) { DFTraversal(i, visited); } } } public static void main(String args[]) { DFS obj = new DFS(10); obj.addEdgesToGraph(1,2); obj.addEdgesToGraph(1,4); obj.addEdgesToGraph(2,5); obj.addEdgesToGraph(2,6); obj.addEdgesToGraph(4,7); obj.addEdgesToGraph(4,8); obj.addEdgesToGraph(3,9); obj.addEdgesToGraph(3,4); obj.addEdgesToGraph(4,3); obj.DFSearch(1); } } |
Output
1 2 5 6 4 7 8 3 9
Applications of DFS
- Implementing Topological sorting
- Solving different puzzles
- Checking graph connected or not
- To detect cycle in graph
- To test graph is bipartite or not
- To find spanning trees and forests.
- To find connected components of graph
- To find cut vertices of the graph
Comment below if you have queries or found any information incorrect in above Depth First Search Java program.
