
%\noindent \textbf{Breadth First Search}
\subsection{Breadth First Search}
\small
\begin{verbatim}
BFS (state start, state end)
// worklist, use stack for a depth first search
queue wl
state s
wl.push (start)

while (!wl.empty ())
  s = wl.front () ; wl.pop ()
  if (s != end)
    foreach state s1 in expand (s)
       wl.push (s1)
\end{verbatim}
\normalsize

BFS relies on you defining a ``state'' and providing an
``expansion'' operator.
For a graph traversal, a state
is node in the graph, expand (s) gives the list of
nodes connected to s.

\small
\begin{verbatim}
struct node_t {
  int prev_node; // prev. node in shortest path
  int cost;  // cost from s to this node
  // nodes connected to this node.
  // first = next node, second = edge weight
  vector<pair<int,int> > succ;
}
vector<node_t> nodes;

// initialize nodes
int shortest_path (int start, int end)
{
  int n;
  queue<int> wl;

// for each i in nodes ;
//   nodes [i].cost = very large number
//   nodes [i].prev_node = -1;

  wl.push (start);
  nodes [start].cost = 0;

  while (!wl.empty ()) {
    n = wl.front ();  wl.pop ();
    for (i = 0; i < nodes [n].succ.size (); i++) {
      int s = nodes [n].succ [i].first;
      int c = nodes [n].cost
               + nodes [n].succ [i].second;
      if (c < nodes [s].cost) {
        nodes [s].cost = c;
        nodes [s].prev_node = n;
        wl.push (s);
      }
    }  }
  return (nodes [end].cost);
  // can get path by reading backwards from
  //  nodes [end].prev_node;  
}
\end{verbatim}
\normalsize

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "../ref-doc"
%%% End:
