Back

Table of contents

Next

Depth first search

    The strategy followed by depth-first search is to search "Deeper" in the graph whenever possible. In depth-first search, edges are explored out of the most recently discovered vertex v that still has unexplored edges leaving it. When all of v's edges have been explored, the searchs "backtracks" to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex. If any undiscovered remain, then one of them is selected as a new source and the search is repeated from that source. This entire process is repeated until all vertices are discovered.

    Unlike breadth-first search, whose predecessor sub-graph forms a tree, the predecessor sub-graph produced by a depth-first search may be composed of several trees, because the search may be repeated from multiple sources. As in breadth-first search, vertices are colored during the search to indicate their state. Each vertex is initioally white, is grayed when it is discovered in the search, and is blackened when it is finished, that is, when its adjacency list has been examined completely.

    Besides creating a depth first forest, depth first search also timestamps each vertex. Each vertex v has two-timestamps: The first timestamp d[v] records when v is first discovered, and the second timestamp f[v] records when the search finishes examining v's adjacency list.

    The following pseudocode is the basic depth first search algorithm. The variable time is a global variable that we use for timestamping.
 

DFS(G)

   1   for each vertex u belonging to V[G]
   2           do color[u] <- WHITE
   3                  parent[u] <- NULL
   4   time <- 0
   5   for each vertex u belonging to V[G]
   6           do if color[u ] = WHITE
   7                     then DFS-VISIT(u)

DFS-VISIT(u)

   1   color[u] <- GRAY
   2   d[u] <- time <- time + 1
   3   for each v belonging to Adj[u]  //   White vertex u has just been discovered
   4           do if color[v] = WHITE
   5                    then parent[v] <- u
   6                             DFS-VISIT(v)
   7   color[u] <- BLACK                   //   Blacken u; it is finished.
   8   f[u] <- time <- time + 1