Algorithms in a Nutshell

(^148) | Chapter 6: Graph Algorithms
If thed[]andf[]information is not needed, then the statements that compute
these values (and the parameters to the functions) can be removed from the code
solution in Example 6-1. DEPTH-FIRSTSEARCHcan capture additional informa-
tion about the edges of the graph. Specifically, in the depth-first forest produced
by DEPTH-FIRSTSEARCH, there are four types of edges:
Tree edges
For all verticesvwhosepred[v]=u, the edge (u,v) was used bydfs_visit(u)
to explore the graph. These edges record the progress of DEPTH-FIRST
SEARCH. Edge (s,1) is an example in Figure 6-10.
}
}
color[u] = Black; // our neighbors are complete; now so are we.
f[u] = ++ctr;
}
/**

• Perform Depth-First Search starting from vertex s, and compute the


• values d[u] (when vertex u was first discovered), f[u] (when all


• vertices adjacent to u have been processed), pred[u] (the predecessor


• vertex to u in resulting depth-first search forest), and label edges


• according to their type.
  /
  void dfs_search (Graph const &graph, int s, / in /
  vector &d, vector &f, / out /
  vector &pred, list &labels) / out */
  {
  // initialize d[], f[], and pred[] arrays. Mark all vertices White
  // to signify unvisited. Clear out edge labels.
  int ctr = 0;
  const int n = graph.numVertices( );
  vector color (n, White);
  d.assign(n, -1);
  f.assign(n, -1);
  pred.assign(n, -1);
  labels.clear( );
  // Search starting at the source vertex; when done, visit any
  // vertices that remain unvisited.
  dfs_visit (graph, s, d, f, pred, color, ctr, labels);
  for (int u = 0; u < n; u++) {
  if (color[u] == White) {
  dfs_visit (graph, u, d, f, pred, color, ctr, labels);
  }
  }
  }
  Example 6-1. Depth-First Search implementation (continued)
  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