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
- Start from a given node(or any arbitrary node, if nothing is given), mark it visited, and push it onto the stack.
- Visit the next adjacent unvisited node of the current node, mark it visited, and push it into the stack.
- If all adjacent nodes of the current node are visited, go back to the parent, visit the remaining adjacent nodes of the parent node.
- 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
- Shortest Path and Minimum Spanning Tree for unweighted graph
- Topological Sorting
- Test if a graph is bipartite
- Finding connected components.
- Solving puzzles with only one solution, such as mazes.