# Kruskal's Algorithm

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

` ````
public struct Edge
{
public int Source;
public int Destination;
public int Weight;
}
public struct Graph
{
public int VerticesCount;
public int EdgesCount;
public Edge[] edge;
}
public struct Subset
{
public int Parent;
public int Rank;
}
public static Graph CreateGraph(int verticesCount, int edgesCoun)
{
Graph graph = new Graph();
graph.VerticesCount = verticesCount;
graph.EdgesCount = edgesCoun;
graph.edge = new Edge[graph.EdgesCount];
return graph;
}
private static int Find(Subset[] subsets, int i)
{
if (subsets[i].Parent != i)
subsets[i].Parent = Find(subsets, subsets[i].Parent);
return subsets[i].Parent;
}
private static void Union(Subset[] subsets, int x, int y)
{
int xroot = Find(subsets, x);
int yroot = Find(subsets, y);
if (subsets[xroot].Rank < subsets[yroot].Rank)
subsets[xroot].Parent = yroot;
else if (subsets[xroot].Rank > subsets[yroot].Rank)
subsets[yroot].Parent = xroot;
else
{
subsets[yroot].Parent = xroot;
++subsets[xroot].Rank;
}
}
private static void Print(Edge[] result, int e)
{
for (int i = 0; i < e; ++i)
Console.WriteLine("{0} -- {1} == {2}", result[i].Source, result[i].Destination, result[i].Weight);
}
public static void Kruskal(Graph graph)
{
int verticesCount = graph.VerticesCount;
Edge[] result = new Edge[verticesCount];
int i = 0;
int e = 0;
Array.Sort(graph.edge, delegate (Edge a, Edge b)
{
return a.Weight.CompareTo(b.Weight);
});
Subset[] subsets = new Subset[verticesCount];
for (int v = 0; v < verticesCount; ++v)
{
subsets[v].Parent = v;
subsets[v].Rank = 0;
}
while (e < verticesCount - 1)
{
Edge nextEdge = graph.edge[i++];
int x = Find(subsets, nextEdge.Source);
int y = Find(subsets, nextEdge.Destination);
if (x != y)
{
result[e++] = nextEdge;
Union(subsets, x, y);
}
}
Print(result, e);
}
```

### Example

` ````
int verticesCount = 4;
int edgesCount = 5;
Graph graph = CreateGraph(verticesCount, edgesCount);
// Edge 0-1
graph.edge[0].Source = 0;
graph.edge[0].Destination = 1;
graph.edge[0].Weight = 10;
// Edge 0-2
graph.edge[1].Source = 0;
graph.edge[1].Destination = 2;
graph.edge[1].Weight = 6;
// Edge 0-3
graph.edge[2].Source = 0;
graph.edge[2].Destination = 3;
graph.edge[2].Weight = 5;
// Edge 1-3
graph.edge[3].Source = 1;
graph.edge[3].Destination = 3;
graph.edge[3].Weight = 15;
// Edge 2-3
graph.edge[4].Source = 2;
graph.edge[4].Destination = 3;
graph.edge[4].Weight = 4;
Kruskal(graph);
```

### Output

` ````
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
```