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

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

数值算法/人工智能

开发平台：

MultiPlatform

_components.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _components.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. /*******************************************************************************
  14. *                                                                              *
  15. *  COMPONENTS  (connected components)                                          *
  16. *                                                                              *
  17. *******************************************************************************/
  20. #include <LEDA/graph_alg.h>
  21. #include <LEDA/node_partition.h>
  22. #include <LEDA/stack.h>
  24. static int count;
  26. static void dfs(const graph& G, node v, node_array<int>& compnum)
  27. { 
  28.   stack<node>  S;
  30.   S.push(v);
  31.   compnum[v] = count;
  33.   while (!S.empty())
  34.    { v = S.pop(); 
  35.      edge e;
  36.      forall_inout_edges(e,v) 
  37.      { node w = G.opposite(v,e);
  38.         if (compnum[w] == -1)
  39.         { compnum[w] = count;
  40.           S.push(w);
  41.          }
  42.       }
  43.     }
  44.  
  45. } 
  47. int COMPONENTS(const graph& G, node_array<int>& compnum)
  48. { // computes the connected components of the underlying undirected graph
  49.   // compnum[v] = i  iff v in component i
  50.   // number of components is returned
  52.   node v;
  54.   forall_nodes(v,G) compnum[v] = -1;
  56.   count = 0;
  58.   forall_nodes(v,G) 
  59.     if (compnum[v] == -1) 
  60.     { dfs(G,v,compnum);
  61.       count++; 
  62.      }
  64.   return count;
  65. }
  69. int COMPONENTS1(const graph& G, node_array<int>& compnum)
  70. { 
  71.   // an alternative implementation using node partitions (union-find)
  73.   node_partition P(G);
  74.   edge e;
  75.   node v;
  77.   forall_nodes(v,G) compnum[v] = -1;
  79.   forall_edges(e,G) P.union_blocks(source(e),target(e));
  81.   int count = 0;
  82.   forall_nodes(v,G) 
  83.    { node w = P.find(v);
  84.      if (compnum[w]==-1) compnum[w] = count++;
  85.      compnum[v] = compnum[w];
  86.     }
  88.   return count;
  89. }