fn() connectedComponentsDecomposes an undirected graph into its connected components.
Decomposes an undirected graph into its connected components.
Defined in | <seqan/graph_algorithms.h> |
---|---|
Signature |
TSize connectedComponents(components, g);
|
Parameters
components
|
A property map. Each vertex is mapped to a component id. If two vertices share the same id they are in the same component. |
---|---|
g
|
An undirected graph. Types: Undirected Graph |
Return Values
TSize |
The number of components. |
---|
Detailed Description
Examples
A simple example on how to use this function.
// Build Input. Graph<Undirected<> > graph; for (unsigned i = 0; i < 5; ++i) addVertex(graph); addEdge(graph, 0, 1); addEdge(graph, 0, 3); addEdge(graph, 2, 4); String<unsigned> components; unsigned numComponents = 0; // Call Algorithm. numComponents = connectedComponents(g, components); // Print Result. std::cout << "Number of components: " << numComponents << std::endl; std::cout << std::endl << "Vertex -> Component" << std::endl; for (unsigned i = 0; i < length(components); ++i) std::cout << i << " -> " << components[i] << std::endl;
The output now is:
Number of components: 2 Vertex -> Component 0 -> 0 1 -> 0 2 -> 1 3 -> 0 4 -> 1