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
Data Races
Thread safety unknown!