Algorithms in a Nutshell

Depth-First Search | 147

Graph

Algorithms

Assumptions

The algorithm works for undirected as well as directed graphs.

Context

DEPTH-FIRSTSEARCHonly needs to store a color (either white, gray, or black)

with each vertex as it traverses the graph. Thus DEPTH-FIRSTSEARCHrequires

only minimal overhead in storing information while it explores the graph starting

froms.

DEPTH-FIRSTSEARCHcan store its processing information in arrays separately

from the graph. Indeed, the only requirements DEPTH-FIRSTSEARCHhas on the

graph is that one can iterate over the vertices that are adjacent to a given vertex.

This feature makes it easy to perform DEPTH-FIRSTSEARCHon complex informa-

tion, since thedfs_visitfunction accesses the original graph as a read-only

structure. DEPTH-FIRSTSEARCHis a blind search that relies only on local infor-

mation, rather than an intelligent plan, to reach the target vertex,t.

Solution

A sample C++ solution is shown in Example 6-1. Note that vertex color informa-

tion is used only within thedfs_search anddfs_visit methods.

Example 6-1. Depth-First Search implementation

#include "dfs.h"

// visit a vertex, u, in the graph and update information

void dfs_visit (Graph const &graph, int u, /* in */

vector<int> &d, vector<int> &f, /* out */

vector<int> &pred, vector<vertexColor> &color, /* out */

int &ctr, list<EdgeLabel> &labels) { /* out */

color[u] = Gray;

d[u] = ++ctr;

// process all neighbors of u.

for (VertexList::const_iterator ci = graph.begin(u);

ci != graph.end(u); ++ci) {

int v = ci->first;

// Compute edgeType and add to labelings. Default to cross

edgeType type = Cross;

if (color[v] == White) { type = Tree; }

else if (color[v] == Gray) { type = Backward; }

else { if (d[u] < d[v]) type = Forward; }

labels.push_back(EdgeLabel (u, v, type));

// Explore unvisited vertices immediately and record pred[].

// Once recursive call ends, backtrack to adjacent vertices.

if (color[v] == White) {

pred[v] = u;

dfs_visit (graph, v, d, f, pred, color, ctr, labels);

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use