Introduction

Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree.

What is a Minimum Spanning Tree?

A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that includes every vertex, where the sum of the weights of all the edges in the tree is minimized. For a disconnected graph, a minimum spanning forest is composed of a minimum spanning tree for each connected component.

About Joseph Kruskal

This algorithm first appeared in Proceedings of the American Mathematical Society, pp. 48–50 in 1956, and was written by Joseph Kruskal. Joseph Bernard Kruskal, Jr. (/ˈkrʌskəl/; January 29, 1928 – September 19, 2010) was an American mathematician, statistician, computer scientist and psychometrician.

Alternative

Other algorithms for this problem include Prim's algorithm.

Why Kruskal's Algorithm?

Applications

Real-life example

In the below example we can solve any of the applications mentioned, from cable tv to connecting road and railways across the island.

Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union — Here is a map of Venice.

Kruskal's algorithm,minimum spanning tree algorithm, Kruskal’s algorithm,Disjoint set union, Minimum spanning tree, Kruskal’s algorithm real world application, Disjoint set application, Minimum spanning tree real life application, Kruskal’s algorithm explained, Minimum spanning tree vs travelling salesman problem, Difference between kruskal’s algorithm and traveling salesman problem, Implementation of Disjoint set union — Connect the nodes representing the islands

We get the below output after applying Kruskal or MSP.

Approach

The following code is implemented with a disjoint-set data structure. Here, we represent our forest F as a set of edges, and use the disjoint-set data structure to efficiently determine whether two vertices are part of the same tree.

algorithm Kruskal(G) is
    F:= ∅
    for each v ∈ G.V do
        MAKE-SET(v)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
           F:= F ∪ {(u, v)}
           UNION(FIND-SET(u), FIND-SET(v))
    return F

Pseudo Code

Example based on the Union Find operation

Demo

A demo for Kruskal's algorithm on a complete graph with weights.

Problems

Friendless Dr. Sheldon Cooper

This problem statement is an example of how we use the Kruskal's algorithm. I feel that the editorial of this problem can be improved. Please read the original problem from the references and then get back to this section.

// Number of test cases
1
// a - number of places he needs to go,  b - number of cab drivers
// a denotes the edges, the places he needs to go
// b denotes the vertices a driver in the city
3 3
// we are given the schedule of all the cabs for places
// for a places, edges are provided from the source to destination
1 2
2 3
1 3

Explanation of the input cases

Approach

We can think of the approach similar to the Kruskal's algorithm where we create Edge List, in this scenario, we can ignore the weights. We try to skip the edges which are connected and maintain a union find for the vertices.

Code

The running code can be found at the inline link https://rextester.com/OAO68569

/*
// Sample code to perform I/O:

name = Console.ReadLine();                  // Reading input from STDIN
Console.WriteLine("Hi, {0}.", name);        // Writing output to STDOUT

// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
*/

// Write your code here
private class Edge {
    public int Src { get; set; }
    public int Dest { get; set; }
}
private class UnionFind {
    private readonly int[] m_parent;
    private readonly int[] m_size;
    public UnionFind(int numVertices) {
        m_parent = new int[numVertices + 1];
        for (var i = 0; i <= numVertices; i++) {
            m_parent[i] = i;
        }
        m_size = new int[numVertices + 1];
    }
    private int FindParent(int node) {
        while (node != m_parent[node]) {
            m_parent[node] = m_parent[m_parent[node]];
            node = m_parent[node];
        }
        return node;
    }
    public bool IsConnected(int u, int v) {
        var uParent = FindParent(u);
        var vParent = FindParent(v);
        return uParent == vParent;
    }
    public void Union (int u, int v) {
        var uParent = FindParent(u);
        var vParent = FindParent(v);
        if (uParent == vParent) {
            return;
        }
        if (m_size[u] < m_size[v]) {
            m_parent[u] = v;
            m_size[v] += m_size[u];
        } else {
            m_parent[v] = u;
            m_size[u] += m_size[v];
        }
    }
}
public static void Main(string[] args) {
    var t = int.Parse(Console.ReadLine());
    while (t-- > 0) {
        var arrAb = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        // number of places he needs to go
        var a = arrAb[0];
        // number of cab drivers
        var b = arrAb[0];
        var edges = new Edge[a];
        for (var i = 0; i < a; i++) {
            var edgeInput = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            edges[i] = new Edge() {Src = edgeInput[0], Dest = edgeInput[1]};
        }
        // Find the minimum number of edges to connect - Minimum spanning tree
        var ans = 0;
        // No need to sort because weights are not holding any value
        var uf = new UnionFind(b);
        for (var i = 0; i < a; i++) {
            var e = edges[i];
            if (!uf.IsConnected(e.Src, e.Dest)) {
                ans++;
                uf.Union(e.Src, e.Dest);
            }
        }
        Console.WriteLine(ans);
    }
}