Depth First Search (DFS) - Graphs

In DFS, we start from a vertex and try to move forward and explore vertices, till we find that all the next edges lead to vertices which have already been visited. Then we backtrack along the same path, and try to explore other possibilities.

DFS divides the edges of a graph into 2 categories:

1. Tree edges: Edges through which we reached(discovered) a vertex for the first time, i.e., edges leading to an unexplored vertex.

2. Back edges: Edges which lead back to a vertex already visited.

In the following figure [b], tree edges are shown in dark bold, and back edges are shown in dotted lines.

We also define 2 time-stamps associated with each vertex of the graph, namely:

Arrival time: The time at which the vertex was explored for the first time, and

Departure time: The time at which we have explored all the neighbors of the vertex and we are ready to backtrack.

In the following diagram[b], arrival/departure time slots are shown for each vertex. These time slots are not really used in this example, as we are just exploring the vertices using DFS (Depth-First Search), but will be really useful when we will be studying the applications of DFS including topological sort of vertices based on their departure times.

Algorithm:

DFS(G, s, V, E, arr[], dep[]):

G = the graph

V = set of vertices

E = set of edges

s = starting vertex

        time = 0; 

        visited[s] = true;

        arr[s] = time++;

 

        for all adjacent vertices w of s :

                if( !visited[w]) {

                        DFS(w)

                }

        dep[s] = time++;

Implementation: 

/*

* DFS.cpp

*

* Created on: Feb 14, 2015

* Author: CodingTonic

*/

#include <iostream>

#include <list>

using namespace std;

#define INF 100

// structure defining Node or vertex of a Graph

struct Node

{

    int vert;

    int weight;

    Node(int _v, int _w): vert(_v), weight(_w)

    {

        ;

    }

};

class Graph

{

    int numVert;

    list<Node> *adjList;

public:

    // Constructor for Graph class

    Graph(int nV): numVert(nV)

    {

        adjList = new list<Node>[nV];

    }

    // Destructor

    ~Graph()

    {

        delete []adjList;

    }

    void AddEdge(int u, int v, int w)

    {

        adjList[u].push_back(Node(v, w));

    }

    // Function for Depth-first traversal of Graph

    void DFS(int s, bool bVisited[], int arr[], int dep[])

    {

        bVisited[s] = true;

        static int _time = 0;

        arr[s] = _time++;

        list<Node>::iterator it;

        for(it = adjList[s].begin(); it != adjList[s].end(); it++)

        {

            if(!bVisited[it->vert])

            {

                DFS(it->vert, bVisited, arr, dep);

            }

        }

        dep[s] = _time++;

    }

};

// main function

int main(int argc, char* argv[])

{

    Graph G(5);

    G.AddEdge(0, 1, 1);

    G.AddEdge(0, 3, 2);

    G.AddEdge(1, 2, 5);

    G.AddEdge(1, 3, 1);

    G.AddEdge(2, 4, 4);

    G.AddEdge(3, 2, 3);

    G.AddEdge(3, 4, 7);

    bool visited[5] = {false, false, false, false, false};

    int arr[5] = {-1, -1, -1, -1, -1}; // arrival time-first time a node is visited

    int dep[5] = {-1, -1, -1, -1, -1}; // departure time - the node and all its neighbors are visited

    G.DFS(0, visited, arr, dep);

    for(int i=0; i<5; i++)

    {

        cout << i << ": visited = " << visited[i] << ", arr = " << arr[i] << ", dep = " << dep[i] << endl;

    }

    return (0);

}

/*         1         5
 *  [0]------->[1]------->[2]
 *     \        |        ^ |
 *      \       |       /  |
 *       \      |      /   |
 *      2 \    1|   3 /    |4
 *         \    |    /     |
 *          \   |   /      |
 *           V  v  /       v
 *            [3]-------->[4]
 *                  7
 * */
 
Output:   
0: visited = 1, arr = 0, dep = 9
1: visited = 1, arr = 1, dep = 8
2: visited = 1, arr = 2, dep = 5
3: visited = 1, arr = 6, dep = 7
4: visited = 1, arr = 3, dep = 4