_components.c

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

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


/*******************************************************************************
*                                                                              *
*  COMPONENTS  (connected components)                                          *
*                                                                              *
*******************************************************************************/


#include <LEDA/graph_alg.h>

#include <LEDA/node_partition.h>


int COMPONENTS(const ugraph& G, node_array<int>& compnum)
{ // computes connected components of undirected graph G
  // compnum[v] = i  iff v in component i
  // number of components is returned

  node v,w;
  list<node> S;
  int count = 0;

  node_array<int> reached(G,false);

  forall_nodes(v,G) 
     if (!reached[v]) 
      { S = DFS(G,v,reached);
        forall(w,S) compnum[w] = count;
        count++; 
       }

  return count;
}



int COMPONENTS1(const ugraph& G, node_array<int>& compnum)
{ 

  node_partition P(G);
  edge e;
  node v;

  forall_nodes(v,G) compnum[v] = 0;

  forall_edges(e,G) P.union_blocks(source(e),target(e));

  int count = 0;
  forall_nodes(v,G) 
   { node w = P.find(v);
     if (compnum[w]==0) compnum[w] = ++count;
    }

  forall_nodes(v,G) compnum[v] = compnum[P.find(v)];

  return count;
}