Introduction

    A Minimum Spanning Tree (MST) is a sub-set of edges from a graph G={V, E} which connects all the vertices together. A graph may have multiple spanning trees but a minimum spanning tree has least sum of weight in all possible spanning trees. If there are V vertices in MST then only V-1 edges can be present. Suppose an undirected graph given below:

Kruskal’s Algorithm: Kruskal’s algorithm works on greedy approach, it takes edges first which are smaller in weight.

1. Define an empty List A = [ ]
2. For each vertex V
   1. Make-Set(V)
3. Sort edges of graph order by weight
4. For each edge E (u, v)
   1. If Find-Set(u) != Find-Set(v)
      1. Append E (u, v) in A
      2. Union (u, v)
5. Return A

Above methods Make-Set, Find-Set and Union are part of set operations. You can read about disjoint set data structure, we will use the same set library.

The Algorithm will pick each edge starting from lowest weight, look below how algorithm works:

Above we can see edge (1, 3) and (0, 4) is not added in minimum spanning tree because if we include any one of these, tree will form cycles which can not be true in case of a tree. Or we can understand it by algorithm since vertex 1 and 3 belongs to same set so it won't be added in results and same is for 0 and 4.

Implementation

    Create a class “Edge”

public class Edge
{
    public int Vertex1 { get; set; }
    public int Vertex2 { get; set; }
    public int Weight { get; set; }
}

Add reference from Disjoint Sets project to current project and implement the algorithm:

static List<Edge> Kruskals_MST(List<Edge> edges, List<int> vertices)
{
    //empty result list
    List<Edge> result = new List<Edge>();

    //making set
    DisjointSet.Set set = new DisjointSet.Set(100);
    foreach (int vertex in vertices)
        set.MakeSet(vertex);

    //sorting the edges order by weight ascending
    var sortedEdge = edges.OrderBy(x => x.Weight).ToList();

    foreach (Edge edge in sortedEdge)
    {
        //adding edge to result if both vertices do not belong to same set
        //both vertices in same set means it can have cycles in tree
        if (set.FindSet(edge.Vertex1) != set.FindSet(edge.Vertex2))
        {
            result.Add(edge);
            set.Union(edge.Vertex1, edge.Vertex2);
        }
    }
    return result;
}

Let's call above method and print the results:

static void Main(string[] args)
{
    //all edges
    List<Edge> edges = new List<Edge>();
    edges.Add(new Edge() { Vertex1 = 1, Vertex2 = 3, Weight = 5 });
    edges.Add(new Edge() { Vertex1 = 2, Vertex2 = 4, Weight = 7 });
    edges.Add(new Edge() { Vertex1 = 2, Vertex2 = 1, Weight = 2 });
    edges.Add(new Edge() { Vertex1 = 3, Vertex2 = 2, Weight = 3 });
    edges.Add(new Edge() { Vertex1 = 0, Vertex2 = 3, Weight = 3 });
    edges.Add(new Edge() { Vertex1 = 4, Vertex2 = 0, Weight = 12 });

    //set of vertices
    List<int> vertices = new List<int>() { 0, 1, 2, 3, 4 };

    List<Edge> MinimumSpanningTree = Kruskals_MST(edges, vertices);

    //printing results
    int totalWeight = 0;
    foreach (Edge edge in MinimumSpanningTree)
    {
        totalWeight += edge.Weight;
        Console.WriteLine("Vertex {0} to Vertex {1} weight is: {2}", edge.Vertex1, edge.Vertex2, edge.Weight);
    }
    Console.WriteLine("Total Weight: {0}", totalWeight);
    Console.ReadLine();
}

Output

Vertex 2 to Vertex 1 weight is: 2

Vertex 3 to Vertex 2 weight is: 3

Vertex 0 to Vertex 3 weight is: 3

Vertex 2 to Vertex 4 weight is: 7

Total Weight: 15