home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _dfs.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  1.3 KB  |  55 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _dfs.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. *  DFS  (depth first search)                                                   *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26. #include <LEDA/b_stack.h>
  27.  
  28. declare(b_stack,node)
  29.  
  30. list(node) DFS(const graph& G, node v, node_array(bool)& reached)
  31. { 
  32.   list(node)  L;
  33.   b_stack(node) S(G.number_of_nodes());
  34.   node w;
  35.  
  36.   if (!reached[v])
  37.    { reached[v] = true;
  38.      L.append(v);
  39.      S.push(v);
  40.     }
  41.  
  42.   while (!S.empty())
  43.    { v = S.pop(); 
  44.      forall_adj_nodes(w,v) 
  45.        if (!reached[w]) 
  46.         { reached[w] = true;
  47.           L.append(w);
  48.           S.push(w);
  49.          }
  50.     }
  51.  
  52.   return L;
  53.  
  54. } 
  55.