开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_dfsnum.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：2k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_dfsnum.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _dfsnum.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_NUM (depth first search numbering)                                      *
  17. *                                                                              *
  18. *******************************************************************************/
  21. #include <LEDA/graph_alg.h>
  23. static int dfs_count1,dfs_count2;
  25. static void dfs(node v, node_array<bool>& reached, 
  26.                         node_array<int>& dfsnum, 
  27.                         node_array<int>& compnum,
  28.                         list<edge>& T )
  29. { node w;
  30.   edge e;
  32.   reached[v] = true;
  33.   dfsnum[v] = ++dfs_count1;
  35.   forall_adj_edges(e,v) 
  36.     { w = target(e);
  37.       if (!reached[w]) 
  38.        { T.append(e);
  39.          dfs(w,reached,dfsnum,compnum,T);
  40.         }
  41.      }
  43.   compnum[v] = ++dfs_count2;
  44. } 
  46. list<edge> DFS_NUM(const graph& G, node_array<int>& dfsnum, 
  47.                                    node_array<int>& compnum)
  48. { 
  49.   list<edge> T;
  50.   node_array<bool> reached(G,false);
  51.   node v;
  52.   dfs_count1 = dfs_count2 = 0;
  53.   forall_nodes(v,G) if (!reached[v]) dfs(v,reached,dfsnum,compnum,T);
  54.   return T;
  55. }