# 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.

## 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.

### 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);
}
}
```