Depth First Search

Idea

Depth First Search also called DFS is a classical algorithm just like BFS. It does recursive calls to find the solution. This algorithm is easier to implement then the BFS, this is why it is very popular in the competitive programming community. It has the same complexity then the BFS. One of the only problems of the DFS is that he uses loads of memory because it uses a recursive stack. The recursive stack is a stack where there is all your recursive calls. Each time it pops the last element of the stack.

Pseudo-code

Here we are implementing the DFS with adj as adjacent list, beg as the begin node, end as the end node, vu is a table of boolean. We are trying to implement a algorithm who tells you if you can go from beg to end.

DFS(adj,beg,end,vu) {
    if beg == end return true
    for all neighbors in adj {
        if !vu[neighbors] {
            vu[neighbors]=true;
            DFS(adj,neighbor,end,vu)
            vu[neighbors]=false;
        }
    }
    return false
}

C++ Code

#include <iostream>
#include <vector>
using namespace std;

inline bool DFS(vector<vector>& adj,vector& vu,int beg,int end){
 if (beg == end) return true;
 for (auto& neighbour:adj[beg]){
  if (!vu[neighbor]){
   vu[neighbour]=true;
   DFS(adj,vu,neighbour,end);
   vu[neighbour]=false;
  }
 }
 return false;
}
int main(){
 ios::sync_with_stdio(0);
 cin.tie(0);
 int n,m;
 // initiation
 // n the number of vertices, m the number of edges
 cin >> n >> m;
 vector<vector> adj(n);
 for (int i=0; i<m; ++i){
                int a,b; // directed graph a to b
   cin >> a >> b;
  adj[a].emplace_back(b);
 }
 vector vu(n);
 if (DFS(adj,vu,0,n-1)) cout << "POSSIBLE\n";
 else cout << "IMPOSSIBLE\n";
 return 0;
}

Applications

DFS and BFS have a lot of same applications but some are unique to BFS and some are unique to DFS.

• Finding Strongly Connected Components of a graph
• To test if a graph is bipartite
• Topological Sorting
• Path Finding
• Detecting cycle in a graph
• Minimum Spanning Tree
• All pair Shortest path
• ......