Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
_dfs.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

_dfs.c：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _dfs.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. *  DFS  (depth first search)                                                   *
  17. *                                                                              *
  18. *******************************************************************************/
  21. #include <LEDA/graph_alg.h>
  22. #include <LEDA/b_stack.h>
  24. list<node> DFS(const graph& G, node v, node_array<bool>& reached)
  25. { 
  26.   int n = G.number_of_nodes();
  28.   b_stack<node> S(n);
  29.   list<node>    L;
  31.   if (!reached[v])
  32.   { reached[v] = true;
  33.     S.push(v);
  34.    }
  36.   while (!S.empty())
  37.   { v = S.pop(); 
  38.     L.append(v);
  39.     node w;
  40.     forall_adj_nodes(w,v) 
  41.       if (!reached[w]) 
  42.        { reached[w] = true;
  43.          S.push(w);
  44.         }
  45.    }
  47.   return L;
  48.  
  49. }