Depth First Search (DFS)
In last post, we learned graph basics and how graphs are represented in programming model. We studied various advantages and disadvantages of adjacency matrix and adjacency list representation of graphs. Today, let’s us discuss traversals of graph. Two kinds of traversals are possible on graph : Depth First search, commonly known as DFS and Breadth First Search, commonly called as BFS.
Depth First Search or traversal explores a given graph depth wise, that means we go down the graph from one node to another till there is no unexplored node down. Once we reach the end of a path going down, backtracking starts and parent of current node is looked for any other unexplored child nodes, and so on.
For above graph depth first search will be 1->6->5->2->3->4
Depth First Search Algorithm
1. Start with a node S, and mark it as visited. 2. Current node u = S 3. While there is edge to be explored 3.1 Move to v where there is an edge (u,v). 3.2 If v is already not visited, mark v as visited 3.3 change u to v and repeat. 4. Move to parent of u.
Recursive implementation of above algorithm of depth first search on graph is very simple as shown below
1 procedure DFS(G,v): 2 label v as discovered 3 for all edges from v to w in G.adjacentEdges(v) do 4 if vertex w is not labeled as discovered then 5 recursively call DFS(G,w)
Iterative implementation of depth first search
1 procedure DFS-iterative(G,v): 2 let S be a stack 3 S.push(v) 4 while S is not empty 5 v = S.pop() 6 if v is not labeled as discovered: 7 label v as discovered 8 for all edges from v to w in G.adjacentEdges(v) do 9 S.push(w)
Below figure explains how iterative depth first traversal works using stacks.
This implementation works only if graph has only one connected component. If graph has more than connected components, depth first search is done starting with each node. For more details on connected components, refer : connected components in graphs
Complexity of depth first search of graph is O(V+E) where V is number of vertices and E is number of edges.
Applications of depth first search
Minimum spanning tree
To check if graph has a cycle.
To find strongly connected components of graph
To find bridges in graph