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.


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


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

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);
}
}
References


Kruskal’s algorithm (Minimum spanning tree) with real-life examples