home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _bfs.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  1.2 KB  |  47 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _bfs.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  BFS  (breadth first search)                                                 *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27. list(node) BFS(const graph&, node s, node_array(int)& dist)
  28. { 
  29.   list(node) Q(s);
  30.   node v,w;
  31.   list_item it;
  32.  
  33.   dist[s] = 0;
  34.   it = Q.first();
  35.  
  36.   while (it != nil)
  37.     { v = Q[it];
  38.       forall_adj_nodes(w,v)
  39.          if (dist[w] < 0) { Q.append(w); 
  40.                             dist[w] = dist[v]+1;
  41.                            }
  42.       it = Q.succ(it);
  43.      }
  44.   return Q;
  45. }
  46.  
  47.