Iterative Depth First Traversal of Graph

Last Updated : 07 May, 2025

Given a directed Graph, the task is to perform Depth First Search of the given graph.

Note: Start DFS from node 0, and traverse the nodes in the same order as adjacency list.

Note : There can be multiple DFS traversals of a graph according to the order in which we pick adjacent vertices. Here we pick vertices as per the insertion order.

Input: adj = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]

Output: [0 1 2 3 4]
Explanation: The source vertex s is 0. We visit it first, then we visit an adjacent.
Start at 0: Mark as visited. Output: 0
Move to 1: Mark as visited. Output: 1
Move to 2: Mark as visited. Output: 2
Move to 3: Mark as visited. Output: 3 (backtrack to 2)
Move to 4: Mark as visited. Output: 4 (backtrack to 2, then backtrack to 1, then to 0)

Not that there can be more than one DFS Traversals of a Graph. For example, after 1, we may pick adjacent 2 instead of 0 and get a different DFS. Here we pick in the insertion order.

Input: [[2,3,1], [0], [0,4], [0], [2]]

Output: [0 2 4 3 1]
Explanation: DFS Steps:

Start at 0: Mark as visited. Output: 0
Move to 2: Mark as visited. Output: 2
Move to 4: Mark as visited. Output: 4 (backtrack to 2, then backtrack to 0)
Move to 3: Mark as visited. Output: 3 (backtrack to 0)
Move to 1: Mark as visited. Output: 1 (backtrack to 0)

The recursive implementation of DFS is already discussed: Depth First Search or DFS for a Graph.

Iterative DFS for Connected Graph – O(V + E) time and O(V) space

The idea is to fist push the given source into the stack. Then keep popping items from the stack while stack has items. Once we pop an item, we add it to the result and then push all its adjacent into the stack in reverse order. Please note that the last added item is going to be removed first.

Step by step approach:

Initialize an empty stack, and push node 0 into it.
Pop a vertex, mark it as visited only if not already visited.
Add the visited vertex to the result collection.
Push all unvisited adjacent vertices to the stack in reverse order.

C++

// C++ program to perform Iterative 
// Depth First Traversal of Graph
#include <bits/stdc++.h>
using namespace std;

vector<int> dfs(vector<vector<int>>& adj) {
    int n = adj.size();
    
    vector<bool> visited(n, false);
    vector<int> res;
    
    // Start DFS from node 0.
    stack<int> st;
    st.push(0);
    
    while (!st.empty()) {
        int node = st.top();
        st.pop();
        
        // If node is already visited, continue
        if (visited[node] == true) {
            continue;
        }
        
        // Mark this node as visited 
        visited[node] = true;
        res.push_back(node);
        
        // Traverse all edges (as stack is used, so 
        // push from right to left)
        int size = adj[node].size();
        for (int i=size-1; i>=0; i--) {
            int v = adj[node][i];
            if (!visited[v]) st.push(v);
        }
    }
    
    return res;
}

int main() {
    vector<vector<int>> adj = 
    {{1, 2}, {2}, {0, 3}, {3}};
    vector<int> res = dfs(adj);
    for (auto node: res) cout << node << " ";
    cout << endl;

    return 0;
}

Java

// Java program to perform Iterative 
// Depth First Traversal of Graph
import java.util.*;

class GfG {

    // Start DFS from node 0.
    static ArrayList<Integer> dfs(ArrayList<ArrayList<Integer>> adj) {
        int n = adj.size();
        
        boolean[] visited = new boolean[n];
        ArrayList<Integer> res = new ArrayList<>();
        
        Stack<Integer> st = new Stack<>();
        st.push(0);
        
        while (!st.isEmpty()) {
            int node = st.pop();
            
            // If node is already visited, continue
            if (visited[node] == true) {
                continue;
            }
            
            // Mark this node as visited 
            visited[node] = true;
            res.add(node);
            
            // Traverse all edges (as stack is used, so 
            // push from right to left)
            int size = adj.get(node).size();
            for (int i = size - 1; i >= 0; i--) {
                int v = adj.get(node).get(i);
                if (!visited[v]) st.push(v);
            }
        }
        
        return res;
    }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        adj.add(new ArrayList<>(Arrays.asList(1, 2)));
        adj.add(new ArrayList<>(Arrays.asList(2)));
        adj.add(new ArrayList<>(Arrays.asList(0, 3)));
        adj.add(new ArrayList<>(Arrays.asList(3)));

        ArrayList<Integer> res = dfs(adj);
        for (int node : res) System.out.print(node + " ");
        System.out.println();
    }
}

Python

# Python program to perform Iterative 
# Depth First Traversal of Graph

def dfs(adj):
    n = len(adj)
    
    visited = [False] * n
    res = []
    
    # Start DFS from node 0.
    st = []
    st.append(0)
    
    while st:
        node = st.pop()
        
        # If node is already visited, continue
        if visited[node] == True:
            continue
        
        # Mark this node as visited 
        visited[node] = True
        res.append(node)
        
        # Traverse all edges (as stack is used, so 
        # push from right to left)
        size = len(adj[node])
        for i in range(size - 1, -1, -1):
            v = adj[node][i]
            if not visited[v]:
                st.append(v)
    
    return res

if __name__ == "__main__":
    adj = [[1, 2], [2], [0, 3], [3]]
    res = dfs(adj)
    for node in res:
        print(node, end=" ")
    print()

// C# program to perform Iterative 
// Depth First Traversal of Graph
using System;
using System.Collections.Generic;

class GfG {

    // Start DFS from node 0.
    static List<int> dfs(List<List<int>> adj) {
        int n = adj.Count;
        
        bool[] visited = new bool[n];
        List<int> res = new List<int>();
        
        Stack<int> st = new Stack<int>();
        st.Push(0);
        
        while (st.Count > 0) {
            int node = st.Pop();
            
            // If node is already visited, continue
            if (visited[node] == true) {
                continue;
            }
            
            // Mark this node as visited 
            visited[node] = true;
            res.Add(node);
            
            // Traverse all edges (as stack is used, so 
            // push from right to left)
            int size = adj[node].Count;
            for (int i = size - 1; i >= 0; i--) {
                int v = adj[node][i];
                if (!visited[v]) st.Push(v);
            }
        }
        
        return res;
    }

    static void Main(string[] args) {
        List<List<int>> adj = new List<List<int>>() {
            new List<int>() {1, 2},
            new List<int>() {2},
            new List<int>() {0, 3},
            new List<int>() {3}
        };

        List<int> res = dfs(adj);
        foreach (int node in res) {
            Console.Write(node + " ");
        }
        Console.WriteLine();
    }
}

JavaScript

// JavaScript program to perform Iterative 
// Depth First Traversal of Graph

function dfs(adj) {
    const n = adj.length;
    
    const visited = new Array(n).fill(false);
    const res = [];
    
    // Start DFS from node 0.
    const st = [];
    st.push(0);
    
    while (st.length > 0) {
        const node = st.pop();
        
        // If node is already visited, continue
        if (visited[node] === true) {
            continue;
        }
        
        // Mark this node as visited 
        visited[node] = true;
        res.push(node);
        
        // Traverse all edges (as stack is used, so 
        // push from right to left)
        const size = adj[node].length;
        for (let i = size - 1; i >= 0; i--) {
            const v = adj[node][i];
            if (!visited[v]) st.push(v);
        }
    }
    
    return res;
}

const adj = [[1, 2], [2], [0, 3], [3]];
const res = dfs(adj);
console.log(res.join(" "));

Output

0 1 2 3

Iterative Depth First Traversal of Graph 1

Iterative DFS for Disconnected Graph – O(V + E) time and O(V) space

The above solution works only for connected graph. In this approach, the idea is to ensure that all nodes are visited. If a node is unvisited, start DFS from this node.

C++

// C++ program to perform Iterative 
// Depth First Traversal of Graph
#include <bits/stdc++.h>
using namespace std;

void dfsUtil(int s, vector<vector<int>> &adj, vector<bool> &visited, 
vector<int> &res) {
    
    stack<int> st;
    st.push(s);
    
    while (!st.empty()) {
        int node = st.top();
        st.pop();
        
        // If node is already visited, continue
        if (visited[node] == true) {
            continue;
        }
        
        // Mark this node as visited 
        visited[node] = true;
        res.push_back(node);
        
        // Traverse all edges (as stack is used, so 
        // push from right to left)
        int size = adj[node].size();
        for (int i=size-1; i>=0; i--) {
            int v = adj[node][i];
            if (!visited[v]) st.push(v);
        }
    }
}

vector<int> dfs(vector<vector<int>>& adj) {
    int n = adj.size();
    
    vector<bool> visited(n, false);
    vector<int> res;
    
    for (int i=0; i<n; i++) {
        if (!visited[i]) {
            dfsUtil(i, adj, visited, res);
        }
    }
    
    return res;
}

int main() {
    vector<vector<int>> adj = 
    {{1, 2}, {2}, {0, 3}, {3}};
    vector<int> res = dfs(adj);
    for (auto node: res) cout << node << " ";
    cout << endl;

    return 0;
}

Java

// Java program to perform Iterative 
// Depth First Traversal of Graph

import java.util.*;

class GfG {

    static void dfsUtil(int s, ArrayList<ArrayList<Integer>> adj, 
    ArrayList<Boolean> visited, ArrayList<Integer> res) {
        
        Stack<Integer> st = new Stack<>();
        st.push(s);
        
        while (!st.isEmpty()) {
            int node = st.pop();
            
            // If node is already visited, continue
            if (visited.get(node) == true) {
                continue;
            }
            
            // Mark this node as visited 
            visited.set(node, true);
            res.add(node);
            
            // Traverse all edges (as stack is used, so 
            // push from right to left)
            int size = adj.get(node).size();
            for (int i = size - 1; i >= 0; i--) {
                int v = adj.get(node).get(i);
                if (!visited.get(v)) st.push(v);
            }
        }
    }

    static ArrayList<Integer> dfs(ArrayList<ArrayList<Integer>> adj) {
        int n = adj.size();
        
        ArrayList<Boolean> visited = new ArrayList<>();
        for (int i = 0; i < n; i++) visited.add(false);
        ArrayList<Integer> res = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (!visited.get(i)) {
                dfsUtil(i, adj, visited, res);
            }
        }
        
        return res;
    }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        adj.add(new ArrayList<>(Arrays.asList(1, 2)));
        adj.add(new ArrayList<>(Arrays.asList(2)));
        adj.add(new ArrayList<>(Arrays.asList(0, 3)));
        adj.add(new ArrayList<>(Arrays.asList(3)));

        ArrayList<Integer> res = dfs(adj);
        for (int node : res) System.out.print(node + " ");
        System.out.println();
    }
}

Python

# Python program to perform Iterative 
# Depth First Traversal of Graph

# Helper DFS function
def dfsUtil(s, adj, visited, res):
    st = []
    st.append(s)
    
    while st:
        node = st.pop()
        
        # If node is already visited, continue
        if visited[node] == True:
            continue
        
        # Mark this node as visited 
        visited[node] = True
        res.append(node)
        
        # Traverse all edges (as stack is used, so 
        # push from right to left)
        size = len(adj[node])
        for i in range(size - 1, -1, -1):
            v = adj[node][i]
            if not visited[v]:
                st.append(v)

def dfs(adj):
    n = len(adj)
    visited = [False] * n
    res = []
    
    for i in range(n):
        if not visited[i]:
            dfsUtil(i, adj, visited, res)
    
    return res

if __name__ == "__main__":
    adj = [
        [1, 2],
        [2],
        [0, 3],
        [3]
    ]
    res = dfs(adj)
    for node in res:
        print(node, end=" ")
    print()

// C# program to perform Iterative 
// Depth First Traversal of Graph

using System;
using System.Collections.Generic;

class GfG {

    static void dfsUtil(int s, List<List<int>> adj, 
    List<bool> visited, List<int> res) {
        
        Stack<int> st = new Stack<int>();
        st.Push(s);
        
        while (st.Count > 0) {
            int node = st.Pop();
            
            // If node is already visited, continue
            if (visited[node] == true) {
                continue;
            }
            
            // Mark this node as visited 
            visited[node] = true;
            res.Add(node);
            
            // Traverse all edges (as stack is used, so 
            // push from right to left)
            int size = adj[node].Count;
            for (int i = size - 1; i >= 0; i--) {
                int v = adj[node][i];
                if (!visited[v]) st.Push(v);
            }
        }
    }

    static List<int> dfs(List<List<int>> adj) {
        int n = adj.Count;
        
        List<bool> visited = new List<bool>(new bool[n]);
        List<int> res = new List<int>();
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfsUtil(i, adj, visited, res);
            }
        }
        
        return res;
    }

    static void Main(string[] args) {
        List<List<int>> adj = new List<List<int>> {
            new List<int>{1, 2},
            new List<int>{2},
            new List<int>{0, 3},
            new List<int>{3}
        };

        List<int> res = dfs(adj);
        foreach (int node in res) {
            Console.Write(node + " ");
        }
        Console.WriteLine();
    }
}

JavaScript

// JavaScript program to perform Iterative 
// Depth First Traversal of Graph

function dfsUtil(s, adj, visited, res) {
    let st = [];
    st.push(s);

    while (st.length > 0) {
        let node = st.pop();

        // If node is already visited, continue
        if (visited[node] === true) {
            continue;
        }

        // Mark this node as visited 
        visited[node] = true;
        res.push(node);

        // Traverse all edges (as stack is used, so 
        // push from right to left)
        let size = adj[node].length;
        for (let i = size - 1; i >= 0; i--) {
            let v = adj[node][i];
            if (!visited[v]) st.push(v);
        }
    }
}

function dfs(adj) {
    let n = adj.length;
    let visited = new Array(n).fill(false);
    let res = [];

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfsUtil(i, adj, visited, res);
        }
    }

    return res;
}

let adj = [
    [1, 2],
    [2],
    [0, 3],
    [3]
];

let res = dfs(adj);
for (let node of res) {
    process.stdout.write(node + " ");
}
console.log();

Output

0 1 2 3

Applications, Advantages and Disadvantages of Depth First Search (DFS)

Shivam

Improve

Article Tags :

Practice Tags :

Iterative Depth First Traversal of Graph

Iterative DFS for Connected Graph – O(V + E) time and O(V) space

Iterative DFS for Disconnected Graph – O(V + E) time and O(V) space

Similar Reads

DFS in different language

Variations of DFS implementations

Thank You!

What kind of Experience do you want to share?