Depth First Search Algorithm for Graph Traversal

Depth First Search is a recursive algorithm used to traverse a Graph. The algorithm starts with an arbitrary node(in case of a graph) and traverses all the nodes of the graph in a depth-first manner. It uses a stack to store the intermediate visited nodes.

Since it is a recursive algorithm, it uses visited array of size = no. of nodes in the graph, which checks if we have already visited that particular node of not. It contains the value 0/1 or True/False and prevents the algorithm from falling into an infinite loop.

The graph can be represented as Adjacency List or Adjacency Matrix.

Algorithm

1. Start from a given node(or any arbitrary node, if nothing is given), mark it visited, and push it onto the stack.
2. Visit the next adjacent unvisited node of the current node, mark it visited, and push it into the stack.
3. If all adjacent nodes of the current node are visited, go back to the parent, visit the remaining adjacent nodes of the parent node.
4. If all nodes are visited, then stop.

int DFS(vector<vector<int> > &graph, int v){
    if(visited[v] ==1)
        return 0;
    visited[v] = 1;
    cout<<v<<" ";
    
    for(int i=0; i<graph[v].size(); i++)
        DFS(graph,graph[v][i]);
    
    return 0;
}

Implementation of the above algorithm in CPP

#include <bits/stdc++.h>
using namespace std;

vector<int> visited(10,0);

int add_edge(vector<int> adj_list[], int u, int v){
	adj_list[u].push_back(v);
	adj_list[v].push_back(u); //if it's undirected graph
	return 0;
}

int DFS(vector<int> graph[], int v){
	if(visited[v] ==1)
		return 0;
	visited[v] = 1;
	cout<<v<<" ";

	for(int i=0; i<graph[v].size(); i++)
		DFS(graph,graph[v][i]);

	return 0;
}

int main() {
	int n = 7;

	vector<int>adj_list[n];

	add_edge(adj_list,1,6);
	add_edge(adj_list,1,3);
	add_edge(adj_list,1,4);
	add_edge(adj_list,3,2);
	add_edge(adj_list,3,4);
	add_edge(adj_list,4,4);
	add_edge(adj_list,5,2);


	cout<<"Nodes are visited using DFS in following order: ";
	DFS(adj_list, 1);
	cout<<endl;

	return 0;
}

Output

Nodes are visited using DFS in the following order: 1 6 3 2 5 4

The time complexity of the above algorithm is O(E+V), where E is total no. of edges and V is total no. of vertices.

Applications of DFS

1. Shortest Path and Minimum Spanning Tree for unweighted graph
2. Topological Sorting
3. Test if a graph is bipartite
4. Finding connected components.
5. Solving puzzles with only one solution, such as mazes.