# fn()kruskalsAlgorithmComputes a minimum spanning tree on a graph.

Defined in ```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. An undirected graph. Types: Undirected Graph A source vertex. Types: VertexDescriptor 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!