Depth First Search – DFS

Depth first search in short form DFS is a graph traversal algorithm. The time complexity of DFS is O(V+E) where V is the number of vertex and E is the number of edges

Depth First Search Algorithm

We will maintain a visited list and a stack
The algorithm works as follows

1. We will start this algorithm by putting any nodes at the top of the stack.
2. Take the top node from the stack let’s say it is r. Then add it to the visited list
3. Traverse through the adjacency list of node r. If the adjacent node is not visited, put this node at the top of the stack
4. Repeat 2 and 3 until the stack is empty

Depth First Search Example

Let’s see how the Depth First Search algorithm works with an example. We use an undirected graph with 5 vertices.

Start from node 0. Put 0 at the visited list and put all of it’s adjacent node to the stack.

Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it.

After we visit the last element 3, it doesn’t have any unvisited adjacent nodes, so we have completed the Depth First Traversal of the graph.

DFS Pseudocode (recursive implementation)

The pseudocode of the DFS recursive implementation is given below.

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
     
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
        if u.visited==false
             DFS(G, u)
}

If the graph has more than one connected component then starting from a node will not visit all other nodes. So in the init function, we call dfs for every unvisited node.

DFS Implementation in Python

adj=[]
n=int(input()) # number of vertices.
m=int(input()) # number of edges
 
 
for i in range(n):
    adj.append([])
 
 
# input edge list.
for i in range(m):
    a, b=map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)


visited=[]
for i in range(n):
    visited.append(0)


def dfs(r):
    global visited, adj
    print(r)
    visited[r]=1
    for i in adj[r]:
        if visited[i]==0:
            dfs(i)


for i in range(n):
    if visited[i]==0:
        dfs(i)

DFS Implementation in C++

#include<bits/stdc++.h>
 
using namespace std;
vector<vector<int> > adj;
vector<int> visited;
void dfs(int r)
{
	visited[r]=1;
	cout<<r<<endl;
	for(auto it:adj[r])
	{
		if(visited[it]==0)
		{
			dfs(it);
		}
	}

}
int main()
{
    int n,m;
    cin>>n; // n is the number of vertices
    cin>>m; // m is the number of edges
    adj.resize(n); // n vector for each node
 
    // input edgelist
    for(int i=0;i<m;i++)
    {
        int a, b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    visited.resize(n);
    
    for(int i=0;i<n;i++){
    	if(visited[i]==0)
    	{
    		dfs(i);
    	}
    }
 
    return 0;
}