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 the adjacency list data structure to explore the nodes along the depth of the selected path from the visited (current) node.


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
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 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(2E+V) for an undirected graph and O(E+V) for a directed graph.


Python

Python: Depth First Search (DFS) implementation in Python 3


Java

Java : Depth First Search (DFS) implementation in Java 8


C++ : Depth First Search (DFS) implementation in C++11

#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 of depth-first search recursive and depth-first search iterative traversals. Implemented in C++14

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

Copyright © 2019 - 2020, Algotree.org.
All rights reserved.