Iterative Depth First Traversal of Graph

In iterative depth first traversal of graph problem, we have given a graph data structure. Write the program to print the depth first traversal of the given graph using the iterative method.

Example

Input : 0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3

Output : 1 2 0 3

Input : 2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3

Output : 2 0 1 3

Algorithm for Iterative Depth First Traversal of Graph

1. Create a class Graph. Initialize an integer variable to store the vertices and a list of the integer type.
2. Create the parameterized constructor of the class which accepts an integer value of the vertex as it’s a parameter. Store the value passed as a parameter in the vertex variable of the class and create a list in the list of the class.
3. Similarly, create the function to add the edge which accepts a vertex and an edge ending value as it’s a parameter. Push the value of edge in the list of the given vertex.
4. Finally, create the function for depth-first traversal which accepts an integer say s representing the source node as it’s a parameter. Initialize a vector of boolean type and set all the values of the vector as false.
5. Create a stack data structure and store the value of the source node in it.
6. Traverse while the stack is not empty. Update the value of the source node as the element at the top of the stack and pop it from the stack.
7. If the value in the vector at the index s i.e. source node is false, print the source node and update the value in the vector at the index s as true.
8. Traverse through the list of vertex/node s and check if the value at the current index in the vector is false to push it in the stack.

C++ Program for Iterative Depth First Traversal of Graph

#include<bits/stdc++.h> 
using namespace std; 
  
class Graph{ 
    int V;  
    list<int> *adj;  
    
    public: 
        Graph(int V); 
        void addEdge(int v, int w);
        void DFS(int s);  
}; 
  
Graph::Graph(int V){ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int v, int w){ 
    adj[v].push_back(w); 
} 
  
void Graph::DFS(int s){ 
    vector<bool> visited(V, false); 
  
    stack<int> stack; 
  
    stack.push(s); 
  
    while (!stack.empty()){ 
        s = stack.top(); 
        stack.pop(); 
  
        if(!visited[s]){ 
            cout << s << " "; 
            visited[s] = true; 
        } 
  
        for(auto i = adj[s].begin(); i != adj[s].end(); ++i){ 
            if(!visited[*i]){ 
                stack.push(*i);
            }
        }
    } 
} 
  
int main(){ 
    Graph g(5);
    
    g.addEdge(1, 0); 
    g.addEdge(0, 2); 
    g.addEdge(2, 1); 
    g.addEdge(0, 3); 
    g.addEdge(1, 4); 
  
    g.DFS(0); 
  
    return 0; 
}

0 3 2 1 4

Java Program for Iterative Depth First Traversal of Graph

import java.util.*; 
  
class IterativeTraversal{ 
    
    static class Graph{ 
        int V; 
          
        LinkedList<Integer>[] adj; 
          
        Graph(int V){ 
            this.V = V; 
            adj = new LinkedList[V]; 
              
            for(int i = 0; i < adj.length; i++){ 
                adj[i] = new LinkedList<Integer>();
            }
        } 
          
        void addEdge(int v, int w){ 
            adj[v].add(w); 
        } 
          
        void DFS(int s){ 
            Vector<Boolean> visited = new Vector<Boolean>(V); 
            
            for(int i = 0; i < V; i++){ 
                visited.add(false); 
            }
      
            Stack<Integer> stack = new Stack<>(); 
              
            stack.push(s); 
              
            while(stack.empty() == false){ 
                s = stack.peek(); 
                stack.pop(); 
                  
                if(visited.get(s) == false){ 
                    System.out.print(s + " "); 
                    visited.set(s, true); 
                } 
                  
                Iterator<Integer> itr = adj[s].iterator(); 
                  
                while (itr.hasNext()){ 
                    int v = itr.next(); 
                    if(!visited.get(v)){ 
                        stack.push(v); 
                    }
                } 
            } 
        } 
    } 
      
    public static void main(String[] args){ 
        
        Graph g = new Graph(5); 
          
        g.addEdge(1, 0); 
        g.addEdge(0, 2); 
        g.addEdge(2, 1); 
        g.addEdge(0, 3); 
        g.addEdge(1, 4); 
              
        g.DFS(0); 
    } 
}

0 3 2 1 4

Complexity Analysis

Time Complexity: O(V+E) where V and E are the numbers of vertices and edges respectively of the given graph.

Space Complexity: O(V) because we used space for V nodes/elements.

References