Depth First Search Traversal (Graphs and n-ary Trees)

Posted by
Depth First Search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

DFS of a Graph vs Tree:-
In graph, there might be cycles and dis-connectivity. Unlike graph, tree does not contain cycle and always connected. So DFS of a tree is relatively easier. We can simply begin from a node, then traverse its adjacent (or children) without caring about cycles. And if we begin from a single node (root), and traverse this way, it is guaranteed that we traverse the whole tree as there is no dis-connectivity.


DFS in a graph


The following image shows how DFS in a tree works:


DFS can be implemented using both recursive and non recursive code.
Note: Make sure you know how to construct a graph/tree, if you aren't familiar do check out my other blog: 

Graph Notations

DFS on Graph using stack (Iterative Code):

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define mod 1000000007
#define N 100005
#define f(i,a,b) for(i=a;i<b;i++)
#define b(i,a,b) for(i=a;i>=b;i--)
#define vi vector<int>
vi graph[N];
bool vis[N]; // boolean array to store whether a node is visted or not 
//assuming graph to be constructed 
void idfs(int root)
{
    stack <int> st;
    st.push(root);
    vis[root]=true;
    while(! st.empty())
    {
        int current=st.top();
        cout<<"Visited Here: "<<current<<"\n";// prints the the current node
        st.pop();
        for(auto neighbor: graph[current])
            if(! vis[neighbor]){
                st.push(neighbor);
                vis[neighbor]=true;
            }
        /*the loop for(auto neighbour:graph[current]){...} is similar 
to the following
        code snippet:
             for(int i=0;i<graph[current].size();i++)
             {
                 int neighbour=graph[current][i];
                 ...
             } */
    }
}

DFS on Graph (Recursive code):
Everything else will just be same, I'll just make a little change in the DFS function:

void dfs(int current) {
    printf("Visited Here: %d ", current);
    vis[current] = true;
    for(auto neighbor: graph[current])
        if(!vis[neighbor]) 
            dfs(neighbor);
}

DFS on a n-ary Tree :
DFS on a tree can also be done using the above codes, but following code is more optimized as it does not need extra space in form of a "vis" array(the array used to mark whether the current node is visited or not).

void dfsForTree(int curr, int parent) {
    printf("Visited Here: %d ", curr);
 
    for(auto adj: graph[curr])
        if(adj != parent) // since no cycle is present, 
it is confirmed that a node will be visited only once
            dfsForTree(adj, curr);
}

The driving function will be as follows:
signed main() {
    int root=1; //assuming tree is rooted at 1, 
for graph DFS can be started from any node
    dfs(root);
    idfs(root);
    dfsForTree(root,-1);//the second argument accepts the parent node, 
passing -1 since root has no parent
    return 0;
}

The above codes print the nodes in the order of the traversal, they can be easily modified to search a value, take sum of the node values, or into various other searching/traversing algorithms.

Space & Time Complexities of the above functions:
idfs(),dfs(),dfsForTree() have a time complexity of O(|V|+|E|) where |V| is the no. of nodes/ vertices and |E| is the no. of edges.
idfs(),dfs() have space of O(|V|), while dfsForTree() has a space complexity of O(1).(no extra space)

Problems to practice:




Comments

Post a Comment