DFS Overview The Depth First Search(DFS) is the most fundamental search algorithm used to explore the nodes and edges of a graph. It runs with time complexity of O(V+E), where `V`

is the number of nodes, and `E`

is the number of edges in a graph.

`DFS`

is often used as a building block in other algorithms; it can be used to:

DFS Visualization on Maze The source is at the position of left-up, and the target is the position of right-bottom.

As we can see, DFS explores as far as possible along each branch before backtracking:

The maze is generated by disjoint set .

The recursive implementation #include <list> #include <vector> #include <iostream> using namespace std ;class Graph { int V; list <int > *adj; bool DFS_rec (int v, int t, vector <bool >& visited) ;public : Graph(int V); void addEdge (int v, int w) ; bool DFS (int v, int t) ; }; Graph::Graph(int V) { this ->V = V; adj = new list <int >[V]; }void Graph::addEdge (int v, int w) { adj[v].push_back(w); }bool Graph::DFS_rec (int v, int t, vector <bool >& visited) { visited[v] = true ; cout << v << " " ; if (v == t) return true ; for (list <int >::iterator it; it = adj[v].begin(); it != adj[v].end(); ++it) { if (!visited[*it] && DFS_rec(*it, t, visited)) return true ; } return false ; }bool Graph::DFS (int v, int t) { vector <bool > visited (V, false ) ; return DFS_rec(v, t, visited); }int main () { Graph g (4 ) ; g.addEdge(0 , 1 ); g.addEdge(0 , 2 ); g.addEdge(1 , 2 ); g.addEdge(2 , 0 ); g.addEdge(2 , 3 ); g.addEdge(3 , 3 ); cout << "Following is Depth First Traversal (0 -> 3): \n" ; if (g.DFS(0 , 3 )) cout << "\nFind a Path!" << std ::endl ; else cout << "\nNo Path!" << std ::endl ; return 0 ; }

The iterative implementation A non-recursive implementation of DFS needs the data-structure of `stack`

.

The worst-case space complexity is O(E).

bool Graph::DFS (int v, int t) { vector <bool > marked (V, false ) ; stack <int > S; S.push(v); marked[v] = true ; while (!S.empty()) { int n = S.top(); S.pop(); cout << n << " " ; if (n == t) return true ; for (list <int >::iterator it = adj[n].begin(); it != adj[n].end(); ++it) { if (!marked[*it]) { marked[*it] = true ; S.push(*it); } } } return false ; }

References