Algorithms in a Nutshell

(^152) | Chapter 6: Graph Algorithms
Solution
A sample C++ solution is shown in Example 6-2. BREADTH-FIRSTSEARCHstores
its state in a stack, and therefore there are no recursive function calls.
Analysis
During initialization, BREADTH-FIRST SEARCHupdates information for all
vertices, and therefore the initialization cost is O(V). When a vertex is first visited
(and colored gray), it is inserted into the queue, and no vertex is added twice.
Example 6-2. Breadth-First Search implementation
#include "bfs.h"
/**

• Perform breadth-first search on graph from vertex s, and compute BFS


• distance and pred vertex for all vertices in the graph.
  /
  void bfs_search (Graph const &graph, int s, / in /
  vector &dist, vector &pred) / out */
  {
  // initialize dist and pred to mark vertices as unvisited. Begin at s
  // and mark as Gray since we haven't yet visited its neighbors.
  const int n = graph.numVertices( );
  pred.assign(n, -1);
  dist.assign(n, numeric_limits::max( ));
  vector color (n, White);
  dist[s] = 0;
  color[s] = Gray;
  queue q;
  q.push(s);
  while (!q.empty( )) {
  int u = q.front( );
  // Explore neighbors of u to expand the search horizon
  for (VertexList::const_iterator ci = graph.begin(u);
  ci != graph.end(u); ++ci) {
  int v = ci->first;
  if (color[v] == White) {
  dist[v] = dist[u]+1;
  pred[v] = u;
  color[v] = Gray;
  q.push(v);
  }
  }
  q.pop( );
  color[u] = Black;
  }
  }
  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