/*******************************************************************************
+
+  LEDA 3.5
+
+  _bfs.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/


//------------------------------------------------------------------------------
// Breadth First Search
//                                                                              
// S. N"aher (1995)
//------------------------------------------------------------------------------



#include <LEDA/graph_alg.h>

list<node> BFS(const graph&, node s, node_array<int>& dist)
{ 
  // performs a breadth first seach on the subgraph induced
  // by all nodes v with dist[v] < 0

  list<node> Q(s);

  dist[s] = 0;

  for (list_item it = Q.first(); it; it = Q.succ(it))
  { node v = Q[it];
    node w;
    forall_adj_nodes(w,v)
      if (dist[w] < 0) 
        { Q.append(w); 
          dist[w] = dist[v]+1;
         }
   }

  return Q;
}

