DFS

Depth First Search

Depth First Search in the graph is similar to Depth-first Traversal in trees. The difference between these two is in graph one or more cycle can be present, but in the tree, there is no cycle. This leads us into a problem to reach the same node more than one time in DFS. To avoid such problem we need one extra array to keep track of the visiting. It uses the stack to keep the tracking. Some basic rules we need to follow to implement DFS. Example

A--------->B
|\         |
| \        |
|  E       |
| /        |
|/         |  
C--------->D

In this above graph if we start the traversal from A. It can go to B, E or C. Let us take B. After this, it can traverse to D or A only if you look at the stack. After traversing D it can travers either B or C since B is visited it will travers to C. Then From C, we can traverse either A or E. Since A is traversed it will travell to E. Let us look at the stack trace->

step 1: stack-> A (Child B, C and E)
step 2: stack-> A B(Child A*, D)
step 3: stack-> A B D(Child B*, C)
step 4: stack-> A B D C(Child A*, D*, E)
step 5: stack-> A B D C E(Child A*, C*)
step 6: stack-> A B D C(Child A*, D*, E*)
step 7: stack-> A B D(Child B*, C*)
step 8: stack-> A B(Child A*, D*)
step 9: stack-> A(Child B*, C*, E*)
step 10: stack-> empty

here * represents visited nodes

Applications

• Formation of Minimum spanning tree
• Detecting a cycle in a graph
• Path Finding
• Topological sorting

Code

import java.io.*; 
import java.util.*; 

class Graph 
{ 
	private int V; // No. of vertices 

	private LinkedList<Integer> adj[]; 

	// Constructor 
	Graph(int v) 
	{ 
		V = v; 
		adj = new LinkedList[v]; 
		for (int i=0; i<v; ++i) 
			adj[i] = new LinkedList(); 
	} 

	void addEdge(int v, int w) 
	{ 
		adj[v].add(w); // Add w to v's list. 
	} 

	void DFSUtil(int v,boolean visited[]) 
	{ 
		visited[v] = true; 
		System.out.print(v+" "); 
		Iterator<Integer> i = adj[v].listIterator(); 
		while (i.hasNext()) 
		{ 
			int n = i.next(); 
			if (!visited[n]) 
				DFSUtil(n, visited); 
		} 
	} 

	void DFS(int v) 
	{ 
		boolean visited[] = new boolean[V]; 
		DFSUtil(v, visited); 
	} 

	public static void main(String args[]) 
	{ 
		Graph g = new Graph(4); 

		g.addEdge(0, 1); 
		g.addEdge(0, 2); 
		g.addEdge(1, 2); 
		g.addEdge(2, 0); 
		g.addEdge(2, 3); 
		g.addEdge(3, 3); 

		System.out.println("Following is Depth First Traversal "+ 
						"(starting from vertex 2)"); 

		g.DFS(2); 
	} 
} 

References

• DFS
• Applications