Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
_bfs.c
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 1k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

_bfs.c：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _bfs.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. /*******************************************************************************
  15. *                                                                              *
  16. *  BFS  (breadth first search)                                                 *
  17. *                                                                              *
  18. *******************************************************************************/
  21. #include <LEDA/graph_alg.h>
  23. list<node> BFS(const graph&, node s, node_array<int>& dist)
  24. { 
  25.   // precondition: dist[v] < 0 for all nodes v
  27.   list<node> Q(s);
  28.   node v,w;
  29.   list_item it;
  31.   dist[s] = 0;
  32.   it = Q.first();
  34.   while (it != nil)
  35.     { v = Q[it];
  36.       forall_adj_nodes(w,v)
  37.          if (dist[w] < 0) { Q.append(w); 
  38.                             dist[w] = dist[v]+1;
  39.                            }
  40.       it = Q.succ(it);
  41.      }
  42.   return Q;
  43. }