Example Connected Components

The following example shows how to use the LEDA function for connected components.

The program creates a graph G with seven nodes and five edges.

Then COMPONENTS() is called for G and node_array<int> compnum. The values of compnum are in the range [0..c-1] where c is the number of connected components of G. For all nodes v in one connected component of G, compnum[v] has the same value and for two nodes v and w in different connected components compnum[v]!=compnum[w]. COMPONENTS() returns the number c of connected components in G.

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/basic_graph_alg.h>

using namespace leda;

int main()
{
  graph G; 

  node n0=G.new_node();node n1=G.new_node();
  node n2=G.new_node();node n3=G.new_node();
  node n4=G.new_node();node n5=G.new_node();
  node n6=G.new_node();

  G.new_edge(n5,n0);G.new_edge(n5,n1);
  G.new_edge(n5,n2);G.new_edge(n1,n3);
  G.new_edge(n4,n6);
 
  node_array<int> compnum(G);
  int c=COMPONENTS(G,compnum);
  
  std::cout << "G has " << c << " connected components" << std::endl;
	
  node v;
  forall_nodes(v,G) {
    std::cout << "compnum[";
    G.print_node(v);
    std::cout << "]=" << compnum[v] << std::endl;
  }
	//compnum[v]=0 for [0],[1],[2],[3],[5]
	//compnum[v]=1 for [4],[6]

  return 0;
}

See also:

Connected Components

Graphs

Parameterized Graphs

Node Arrays

Basic Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Basic Graph Algorithms