Depth First Search

The depth-first-search algorithm is similar to the standard algorithm for traversing binary trees; it first fully explores one subtree before returning to the current node and then exploring the other subtree. Another way to think of depth-first-search is by saying that it is similar to breadth-first search except that it uses a stack instead of a queue.

During the execution of the depth-first-search algorithm, each vertex, i, is assigned a colour, c[i]: white if we have never seen the vertex before, grey if we are currently visiting that vertex, and black if we are done visiting that vertex. The easiest way to think of depth-first-search is as a recursive algorithm. It starts by visiting u. When visiting a vertex i, we first mark i as grey. Next, we scan i’s adjacency list and recursively visit any white vertex we find in this list. Finally, we are done processing i, so we colour i black and return.

DFS

Algorithm:

DFS(G)
    for each vertex u ∈ G.V
        u.color = WHITE
        u.π = NIL
    time = 0
    for each vertex u ∈ G.V
        if u.color == WHITE
            DFS-VISIT(G,u)
DFS-VISIT(G,u)
    time = time + 1
    u.d = time
    u.color = GRAY
    for each v ∈ G.Adj[u]
        if v.color == WHITE
            v.π = u
            DFS-VISIT(G,v)
    u.color = BLACK
    time = time + 1
    u.f = time

Implementation:

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#define MAX 101
using namespace std;

enum colors {BLACK, WHITE, GRAY};
int color[MAX], d[MAX], p[MAX], f[MAX], t, vertex, edge;
int NIL = numeric_limits::min();

void DFS(vector[]);
void DFS_VISIT(vector[],int);

int main()
{
    //freopen("dfs.txt", "r", stdin);
    vector adjList[MAX];
    int u, v;
    cin >> vertex >> edge;
    for(int e=1; e<=edge; e++) {
        cin >> u >> v;
        adjList[u].push_back(v);
    }
    DFS(adjList);
    for(int v=1; v<=vertex; v++) {
        printf("v%d (%d,%d)\n", v, d[v], f[v]);
    }
    return 0;
}

void DFS(vector G[]) {
    for(int u=0; u<=vertex; u++) {
        color[u] = WHITE;
        p[u] = NIL;
    }
    t = 0;
    for(int u=1; u<=vertex; u++) {
        if(color[u] == WHITE) {
            DFS_VISIT(G,u);
        }
    }
}

void DFS_VISIT(vector G[], int u) {
    t = t + 1;
    d[u] = t;
    color[u] = GRAY;
    for(int v=0; v<G[u].size(); v++) {
        if(color[G[u][v]] == WHITE) {
            p[G[u][v]] = u;
            DFS_VISIT(G,G[u][v]);
        }
    }
    color[u] = BLACK;
    t = t + 1;
    f[u] = t;
}

Not surprisingly, the running times of DFS(G,u) is the same as that of BFS(G,u).