fn() kruskalsAlgorithmComputes a minimum spanning tree on a graph.
Computes a minimum spanning tree on a graph.
Defined in | <seqan/graph_algorithms.h> |
---|---|
Signature |
void kruskalsAlgorithm(edges, g, source, weight);
|
Parameters
edges
|
A String of vertex descriptors that represent edges. Each consecutive pair is an edge with the two end points. |
---|---|
g
|
An undirected graph. Types: Undirected Graph |
source
|
A source vertex. Types: VertexDescriptor |
weight
|
Edge weights. |
Detailed Description
Example
#include <iostream> #include <seqan/graph_algorithms.h> using namespace seqan; int main() { typedef Graph<Undirected<> > TGraph; typedef VertexDescriptor<TGraph>::Type TVertexDescriptor; typedef Size<TGraph>::Type TSize; // Create graph with 14 undirected edges {0,1}, {0,6}, ... TSize numEdges = 14; TVertexDescriptor edges[] = {0, 1, 0, 6, 1, 2, 1, 6, 2, 3, 2, 4, 2, 8, 3, 5, 3, 8, 4, 6, 4, 7, 5, 8, 6, 7, 7, 8}; TGraph g; addEdges(g, edges, numEdges); // Print graph. std::cout << g << std::endl; // Fill external property map for each edge weight and vertex names. unsigned int weights[] = {4, 8, 8, 11, 7, 2, 4, 9, 14, 7, 6, 10, 1, 2}; char names[] = {'a', 'b', 'c', 'd', 'i', 'e', 'h', 'g', 'f'}; String<int> weightMap; assignEdgeMap(weightMap, g, weights); String<char> nameMap; assignVertexMap(nameMap, g, names); // Run Kruskal's algorithm. String<TVertexDescriptor> treeEdges; kruskalsAlgorithm(treeEdges, g, 0, weightMap); // Print the result to stdout. std::cout << "Minimum Spanning Tree (Kruskal's algorithm): \n" << "Tree Edges: "; typedef Iterator<String<TVertexDescriptor> >::Type TStrIterator; TStrIterator it = begin(treeEdges); TStrIterator itEnd = end(treeEdges); while (it != itEnd) { std::cout << "(" << getProperty(nameMap, getValue(it)) << ","; goNext(it); std::cout << getProperty(nameMap, getValue(it)) << "), "; goNext(it); } std::cout << "\n"; return 0; }
Adjacency list: 0 -> 6,1, 1 -> 6,2,0, 2 -> 8,4,3,1, 3 -> 8,5,2, 4 -> 7,6,2, 5 -> 8,3, 6 -> 7,4,1,0, 7 -> 8,6,4, 8 -> 7,5,3,2, Edge list: Source: 0,Target: 6 (Id: 1) Source: 0,Target: 1 (Id: 0) Source: 1,Target: 6 (Id: 3) Source: 1,Target: 2 (Id: 2) Source: 2,Target: 8 (Id: 6) Source: 2,Target: 4 (Id: 5) Source: 2,Target: 3 (Id: 4) Source: 3,Target: 8 (Id: 8) Source: 3,Target: 5 (Id: 7) Source: 4,Target: 7 (Id: 10) Source: 4,Target: 6 (Id: 9) Source: 5,Target: 8 (Id: 11) Source: 6,Target: 7 (Id: 12) Source: 7,Target: 8 (Id: 13) Minimum Spanning Tree (Kruskal's algorithm): Tree Edges: (h,g), (c,i), (g,f), (a,b), (c,f), (c,d), (a,h), (d,e),
Data Races
Thread safety unknown!