Depth First Search ( DFS )

Graph and tree traversal using depth-first search (DFS) algorithm

  • DFS is an algorithm for traversing a Graph or a Tree.
  • DFS starts with the root node and explores all the nodes along the depth of the selected path before backtracking to explore the next path.
  • DFS makes use of Stack for storing the visited nodes of the graph / tree.

Example: Consider the below step-by-step DFS traversal of the tree. If the source is root (node ‘0’), the nodes ‘2’ & ‘4’ along the depth of the tree are explored before the other nodes in the tree.

DFS_Example_Run



Algorithm : Depth first search (Graph G, Souce_Vertex S)

1.    Create a stack STK to store the vertices.
2.    Push the source vertex S in the stack ‘STK’.
3.    While the stack STK is not empty
4.        Pop the vertex U from the top of the stack. i.e Vertex U = STK.top(), STK.pop()
5.        If the vertex U is not visited, Then
6.            Explore the vertex U and mark U as visited.
7.            For every vertex V adjacent to vertex U
8.                Push the vertex V in the stack STK


Example of depth-first search traversal on a graph : In the below unweighted graph, the DFS algorithm beings by exploring node ‘0’, followed by its adjacent vertex node ‘1’, followed by its adjacent vertex node ‘3’ and so on.

DFS_Graph

Example of depth-first search traversal on a tree : In the below tree, the DFS algorithm beings by exploring node ‘0’ followed by its adjacent vertex node ‘1’, followed by node ‘2’ then node ‘3’ before backtracking to explore the next path.
DFS_Tree

Data structure used for storing graph or tree : Adjacency List
Data structure used for depth first search : Stack
Time complexity of depth first search : O ( V + E ) for an adjacency list implementation of a graph or a tree. ‘V’ is the number of vertices and ‘E’ is the number of edges in a graph/tree.

Why is the time complexity of depth first search algorithm O ( V + E ) : When the graph is stored in an adjacency list, the neighbors of a vertex on the out going edge are explored successively/linearly. As each vertex is explored only once, all the vertices are explored in O ( V ) time. The total number of edges (maintained in the adjacency list) are 2*E (bi-directional) for an undirected graph and E for a directed graph. Thus the time complexity is O ( 2.E + V ) for an undirected graph and O ( E + V ) for a directed graph.



Depth First Search Implementation

from collections import deque
from collections import defaultdict

class Graph:

    def __init__(self, nodes) :
        # Store the adjacency list as a dictionary
        # { 0 : [ 1, 2 ], 1 : [ 3, 4 ] }
        # The default dictionary would create an empty list as a default (value) 
        # for the nonexistent keys.
        self.adjlist = defaultdict(list)
        self.nodes = nodes
        self.visited = [False] * nodes

    def AddEdge (self, src, dst) :

        self.adjlist[src].append(dst)
        self.adjlist[dst].append(src)

    # Recursive version of DFS 
    def DFS (self, src) :

        self.visited[src] = True
        print(src, end = ' ')

        if src in self.adjlist : # Check if the key (src) exists in the dictionary (adjlist)
           for adj_node in self.adjlist[src] :
               if self.visited[adj_node] == False :
                   self.DFS(adj_node)

    # Iterative version of DFS
    def DFSIterative (self, src) :

        stack = deque()
        stack.append(src)

        while stack :
            src = stack.popleft()
            if self.visited[src] == False :
                self.visited[src] = True
                print(src, end = ' ')
                if src in self.adjlist :
                    for adj_node in self.adjlist[src] :
                        stack.appendleft(adj_node)

    def MarkUnvisited(self) :
        # Reset the visited array for next iteration of breadth first search
        self.visited = [False] * self.nodes

def main():

    nodes = 7

    g = Graph(nodes)

    g.AddEdge(0, 1)
    g.AddEdge(0, 2)
    g.AddEdge(1, 3)
    g.AddEdge(1, 4)
    g.AddEdge(2, 3)
    g.AddEdge(3, 5)
    g.AddEdge(4, 6)
    g.AddEdge(5, 6)

    print("\nDFS Graph Traversal Recursive")

    print("Source Node 0 :", end = " ")
    g.DFS(0)
    g.MarkUnvisited()

    print("\nSource Node 3 :", end = " ")
    g.DFS(3)
    g.MarkUnvisited()

    print("\n\nDFS Graph Traversal Iterative")
    print("Source Node 0 :", end = " ")
    g.DFSIterative(0)
    g.MarkUnvisited()

    print("\nSource Node 3 :", end = " ")
    g.DFSIterative(3)

    nodes = 10
    t = Graph(nodes)

    t.AddEdge(0,1)
    t.AddEdge(0,6)
    t.AddEdge(0,7)
    t.AddEdge(1,2)
    t.AddEdge(1,4)
    t.AddEdge(1,5)
    t.AddEdge(2,3)
    t.AddEdge(7,8)
    t.AddEdge(7,9)

    print("\n\nDFS Tree Traversal")
    print("Root Node (0): ", end = " ")
    t.DFS(0)
    t.MarkUnvisited()

    print("\nRoot Node (4): ", end = " ")
    t.DFS(4)
    t.MarkUnvisited()

    print("\n\nDFS Tree Traversal Iterative")
    print("Source Node 0 :", end = " ")
    t.DFSIterative(0)
    t.MarkUnvisited()

    print("\nSource Node 4 :", end = " ")
    t.DFSIterative(4)

if __name__ == "__main__" :
    main()

Output

DFS Graph Traversal Recursive
Source Node 0 : 0 1 3 2 5 6 4 
Source Node 3 : 3 1 0 2 4 6 5 

DFS Graph Traversal Iterative
Source Node 0 : 0 2 3 5 6 4 1 
Source Node 3 : 3 5 6 4 1 0 2 

DFS Tree Traversal
Root Node (0):  0 1 2 3 4 5 6 7 8 9 
Root Node (4):  4 1 0 6 7 8 9 2 3 5 

DFS Tree Traversal Iterative
Source Node 0 : 0 7 9 8 6 1 5 4 2 3 
Source Node 4 : 4 1 5 2 3 0 7 9 8 6 
#include<iostream>
#include<list>
#include<vector>
#include<stack>

using namespace std;

class Graph {

    private:

        int nodes;
        list<int> *adjlist;
        vector<bool> visited;

    public:

        Graph() {
        }

        Graph (int nodes) { // Allocate resources 
            adjlist = new list<int> [nodes];
            visited.resize(nodes, false);
            this->nodes = nodes;
        }

        ~Graph () { // Free allocated resources
            delete [] adjlist;
        }

        void AddEdge (int src, int dst) {
            adjlist[src].push_back(dst);
            adjlist[dst].push_back(src);
        }

        // DFS recursive
        void DFS (int src) {
            visited[src] = true;
            cout << src << " ";
            for (auto& adj_node : adjlist[src]) {
                if (!visited[adj_node]) {
                    DFS(adj_node);
                }
            }
        }

       // DFS iterative
       void DFS_Iterative (int src) {

           stack<int> stk;
           visited[src] = true;
           stk.push(src);

           while (!stk.empty()) {
               src = stk.top();
               stk.pop();
               cout << src << " ";
               for (auto &adj_node : adjlist[src]) {
                   if (!visited[adj_node]) {
                       visited[adj_node] = true;
                       stk.push(adj_node);
                   }
               }
           }
       }

        // Mark nodes unvisited for next traversal
        void MarkUnvisited () {
            fill(visited.begin(), visited.end(), false);
        }
};

int main()
{
    Graph g(7);
    g.AddEdge(0,1);
    g.AddEdge(0,2);
    g.AddEdge(1,3);
    g.AddEdge(1,4);
    g.AddEdge(2,3);
    g.AddEdge(3,5);
    g.AddEdge(4,6);
    g.AddEdge(5,6);

    cout << "DFS Recursive Graph Traversal " << endl;
    cout << "Source Node (0): "; g.DFS(0);
    g.MarkUnvisited(); cout << endl;
    cout << "Source Node (3): "; g.DFS(3);
    g.MarkUnvisited(); cout << endl;

    cout << "DFS Iterative Graph Traversal" << endl;
    cout << "Source Node (0): "; g.DFS_Iterative(0);
    g.MarkUnvisited(); cout << endl;
    cout << "Source Node (3): "; g.DFS_Iterative(3);
    g.MarkUnvisited(); cout << endl << endl;

    Graph t(10);
    t.AddEdge(0,1);
    t.AddEdge(0,6);
    t.AddEdge(0,7);
    t.AddEdge(1,2);
    t.AddEdge(1,4);
    t.AddEdge(1,5);
    t.AddEdge(2,3);
    t.AddEdge(7,8);
    t.AddEdge(7,9);

    cout << "DFS Recursive Tree Traversal" << endl;
    cout << "Root Node (0): "; t.DFS(0);
    t.MarkUnvisited(); cout << endl;
    cout << "Root Node (4): "; t.DFS(4);
    t.MarkUnvisited(); cout << endl;

    cout << "DFS Iterative Tree Traversal" << endl;
    cout << "Source Node (0): "; t.DFS_Iterative(0);
    t.MarkUnvisited(); cout << endl;
    cout << "Source Node (4): "; t.DFS_Iterative(4);
    t.MarkUnvisited(); cout << endl;
    return 0;
}

Output

DFS Recursive Graph Traversal
Source Node (0): 0 1 3 2 5 6 4
Source Node (3): 3 1 0 2 4 6 5
DFS Iterative Graph Traversal
Source Node (0): 0 2 3 5 6 4 1
Source Node (3): 3 5 6 4 2 0 1

DFS Recursive Tree Traversal
Root Node (0): 0 1 2 3 4 5 6 7 8 9
Root Node (4): 4 1 0 6 7 8 9 2 3 5
DFS Iterative Tree Traversal
Source Node (0): 0 7 9 8 6 1 5 4 2 3
Source Node (4): 4 1 5 2 3 0 7 9 8 6
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
import java.util.Arrays;

class DFSTraversal {

    static class Graph {

        Integer nodes;
        List<List<Integer>> adjlist;
        boolean[] visited;

        Graph (int arg_nodes) {
            nodes = arg_nodes;
            adjlist = new ArrayList<>(nodes);
            for (int i=0; i<nodes; i++)
                adjlist.add(new ArrayList<>());
            visited = new boolean[nodes];
        }

        void AddEdge (int src, int dst) {
            adjlist.get(src).add(dst);
            adjlist.get(dst).add(src);
        }

        // DFS recursive implementation
        void DFS (int src) {
            visited[src] = true;
            System.out.print(src + " ");
            for (int adj_node : adjlist.get(src)) {
                if (!visited[adj_node]) {
                    DFS(adj_node);
                }
            }
        }

        // DFS iterative implementation
        void DFS_Iterative (int src) {
            Stack<Integer> stk = new Stack<>();
            stk.push(src);
            while (!stk.empty()) {
                src = stk.peek();
                stk.pop();
                if (!visited[src]) {
                    visited[src] = true;
                    System.out.print(src + " ");
                    for (int adj_node : adjlist.get(src)) {
                        stk.push(adj_node);
                    }
                }
            }
        }

        // Mark nodes unvisited for next traversal
        void MarkUnvisited () {
            Arrays.fill(visited, false);
        }
    }

    public static void main (String[] args) {

        Graph g = new Graph(7);
        g.AddEdge(0,1);
        g.AddEdge(0,2);
        g.AddEdge(1,3);
        g.AddEdge(1,4);
        g.AddEdge(2,3);
        g.AddEdge(3,5);
        g.AddEdge(4,6);
        g.AddEdge(5,6);

        System.out.println("DFS Recursive Graph Traversal ");
        System.out.print("\nSource Node (0): "); g.DFS(0);

        g.MarkUnvisited();
        System.out.print("\nSource Node (3): "); g.DFS(3);
        g.MarkUnvisited();

        System.out.println("\n\nDFS Iterative Graph Traversal");
        System.out.print("\nSource Node (0): "); g.DFS_Iterative(0);
        g.MarkUnvisited();
        System.out.print("\nSource Node (3): "); g.DFS_Iterative(3);
        g.MarkUnvisited();

        Graph t = new Graph(10);
        t.AddEdge(0,1);
        t.AddEdge(0,6);
        t.AddEdge(0,7);
        t.AddEdge(1,2);
        t.AddEdge(1,4);
        t.AddEdge(1,5);
        t.AddEdge(2,3);
        t.AddEdge(7,8);
        t.AddEdge(7,9);

        System.out.println("\n\nDFS Recursive Tree Traversal");
        System.out.print("\nRoot Node (0): "); t.DFS(0);
        t.MarkUnvisited();
        System.out.print("\nRoot Node (4): "); t.DFS(4);
        t.MarkUnvisited();

        System.out.println("\n\nDFS Iterative Tree Traversal");
        System.out.print("\nSource Node (0): "); t.DFS_Iterative(0);
        t.MarkUnvisited();
        System.out.print("\nSource Node (4): "); t.DFS_Iterative(4);
        t.MarkUnvisited();
    }
}

Output

DFS Recursive Graph Traversal

Source Node (0): 0 1 3 2 5 6 4
Source Node (3): 3 1 0 2 4 6 5

DFS Iterative Graph Traversal

Source Node (0): 0 2 3 5 6 4 1
Source Node (3): 3 5 6 4 1 0 2

DFS Recursive Tree Traversal

Root Node (0): 0 1 2 3 4 5 6 7 8 9
Root Node (4): 4 1 0 6 7 8 9 2 3 5

DFS Iterative Tree Traversal

Source Node (0): 0 7 9 8 6 1 5 4 2 3
Source Node (4): 4 1 5 2 3 0 7 9 8 6


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.