_dfs.c

数据类型和算法库LEDA 数据类型和算法库LEDA

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _dfs.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/



/*******************************************************************************
*                                                                              *
*  DFS  (depth first search)                                                   *
*                                                                              *
*******************************************************************************/


#include <LEDA/graph_alg.h>
#include <LEDA/b_stack.h>


list<node> DFS(const graph& G, node v, node_array<int>& reached)
{ 
  list<node>  L;
  b_stack<node> S(G.number_of_nodes());
  node w;

  if (!reached[v])
   { reached[v] = true;
     L.append(v);
     S.push(v);
    }

  while (!S.empty())
   { v = S.pop(); 
     forall_adj_nodes(w,v) 
       if (!reached[w]) 
        { reached[w] = true;
          L.append(w);
          S.push(w);
         }
    }

  return L;
 
}