Depth first search for a Graph

Traversal of a Graph means visiting each and every nodes present in the Graph. Traversal can be done using various approaches and here we are going to talk about one of most famous and useful traversal algorithm known as Depth first search (DFS). In this algorithm, backtracking and recursion is being used along with a Stack to visit all the nodes. Before going ahead have a look into Graph Basics.

Depth first search (DFS) algorithm

The idea of this algorithm is to visit all the nodes of the graph avoiding any cycles. To do this we are going to need following items:

• Stack
• Recursion
• Backtracking

DFS algorithm steps

• Pick any graph node to start the traversal and push it into a Stack.
• Pop the topmost item of the Stack, marked it as visited.
• Push all the non visited neighbouring nodes of the popped node into the Stack.
• Keep repeating Steps 2 and 3 until all Graph nodes are visited.

Let’s take an example to understand clearly how this algorithm works.
Below is the sample Graph which we are going to traverse using DFS algorithm.

Now, let’s see how DFS actually works step by step.
We are going to start traversal from Node A.

1) Push A into Stack. Stack contains -- A, Visited Nodes -- 0
2) Pop top item A from Stack. Stack contains -- 0. Visited Nodes -- A
3) Push all unvisited neighbouring nodes t of A to Stack. Stack contains -- B, C. Visited Nodes -- A
4) Pop top item C from Stack. Stack contains -- B. Visited Nodes -- A, C
5) Push all unvisited neighbouring nodes C to Stack. Stack contains -- B, B, G. Visited Nodes -- A, C
6) Pop top item G from Stack. Stack contains -- B, B. Visited Nodes -- A, C, G
7) Push all unvisited neighbouring nodes G to Stack. Stack contains -- B, B, D. Visited Nodes -- A, C, G
8) Pop top item D from Stack. Stack contains -- B, B. Visited Nodes -- A, C, G, D
9) Push all unvisited neighbouring nodes D to Stack. Stack contains -- B, B. Visited Nodes -- A, C, G, D
10) Pop top item B from Stack. Stack contains -- B. Visited Nodes -- A, C, G, D, B
11) Push all unvisited neighbouring nodes B to Stack. Stack contains -- B, E, F. Visited Nodes -- A, C, G, D, B
12) Pop top item F from Stack. Stack contains -- B, E. Visited Nodes -- A, C, G, D, B, F
13) Push all unvisited neighbouring nodes F to Stack. Stack contains -- B, E. Visited Nodes -- A, C, G, D, B, F
14) Pop top item E from Stack. Stack contains -- B. Visited Nodes -- A, C, G, D, B, F, E
15) Push all unvisited neighbouring nodes E to Stack. Stack contains -- B. Visited Nodes -- A, C, G, D, B, F, E
16) Pop top item B from Stack. As this node is already visited ignore this node.
17) Traversal done as Stack is empty now.

Let’s have a look into implementation code. Check Graph and its basic implementation before going ahead.

class Graph
{
    private:
        int m_nodes;
        int m_edges;
        int **edges;
        bool isUndirected;

    public:
        Graph (int nodes, bool isUndirected);
        int getNumberOfNodes ();
        int getNumberOfEdges ();
        void getEdges ();
        bool addEdge (int srcNode, int dstNode);
        void DFS (int start);
        ~Graph ();
};

void Graph::DFS (int start)
{
    cout << "Starting DFS traversing of Graph from Node: " << start << endl;
    bool visited[m_nodes] = {false};

    if (m_nodes == 0)
    {
        cout << "There is no nodes present in Graph" << endl;
    }

    if (start < 0)
    {
        start = 0;
    }

    if (start >= m_nodes)
    {
        cout << "Graph traversal not possible as start node not found" << endl;
        return;
    }

    Stack s(m_nodes);
    s.push (start);

    while (!s.isEmpty ())
    {
        int visiting = s.pop ();

        if (visited[visiting])
        {
            cout << "Graph node " << visiting << " Already visited, skipping!!!" << endl;
            continue;
        }

        visited[visiting] = true;

        cout << "Visited node: " << visiting << " in the Graph." << endl;
        for (int i = 0; i < m_nodes; i++)
        {
            if (edges[visiting][i] && !visited[i])
            {
                cout << "Pushing node " << i << endl;
                s.push (i);
            }
        }
    }

    /* Below code is to check whether Graph is connected or not */
    isConnected = -1;
    for (int i = 0; i < m_nodes; i++)
    {
        if (!visited[i])
        {
            isConnected = 0;
            break;
        }
    }

    if (isConnected == -1)
    {
        isConnected = 1;
    }
}

Let’s define a sample Graph and check how this code works.

int main ()
{
    Graph g(5, true);
    g.addEdge (1,2);
    g.addEdge (0,2);
    g.addEdge (3,2);
    g.addEdge (4,2);
    g.addEdge (1,3);
    g.addEdge (1,4);
    g.addEdge (1,5);
    g.addEdge (1,7);
    g.addEdge (1,0);
    g.addEdge (2,2);
    g.addEdge (3,2);
    g.addEdge (4,2);
    g.addEdge (5,2);
    cout << "Graph has nodes: " << g.getNumberOfNodes () << endl;
    cout << "Graph has edges: " << g.getNumberOfEdges () << endl;
    g.DFS (0);
}

Let’s check the output of above code.

Starting DFS traversing of Graph from Node: 0
Visited node: 0 in the Graph.
Pushing node 1
Pushing node 2
Visited node: 2 in the Graph.
Pushing node 1
Pushing node 3
Pushing node 4
Visited node: 4 in the Graph.
Pushing node 1
Visited node: 1 in the Graph.
Pushing node 3
Visited node: 3 in the Graph.
Graph node 3 Already visited, skipping!!!
Graph node 1 Already visited, skipping!!!
Graph node 1 Already visited, skipping!!!

Time Complexity: O(V^2)

Applications of DFS

• Topological sorting
• Cycle detection in Graphs
• Strongly connected Graphs — A graph is called strongly connected if there is a path from every vertex to every other vertex.