Kruskal algorithm is a way to find a Minimum Spanning Tree(MST) from undirected edge-weighted graph.
Minimum Spanning Tree(MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.
https://en.wikipedia.org/wiki/Minimum_spanning_tree
It is one of the most representative algorithms of greedy algorithm in graph theory.
Algorithm Steps
- Sort all edges in ascending order of their weight.
- Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
- Repeat step#2 until there are (V-1) edges in the spanning tree.
One of the things to note from this algorithm is the way how you will detect the cycle from step #2. It is widely known to use Union-Find algorithm to find a cycle from a graph. To be specific, Union-Find algorithm can be used to determine whether the given nodes are connected and are under the same graph.
Union-Find Algorithm
Union-Find algorithm can be used to check whether an undirected graph contains cycle or no.
It uses an array that contains information of the parent nodes of each node and performs two useful operations on the graph.
Find : Determine which subset a particular element is in. In other words, get the parent node so that it can determine if two elements are in the same subset/connected.
Union : Join two subsets into a single subset.
Algorithm Steps
Let’s consider there are different nodes like below.
- Initialize parent array of each node to be pointing itself.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
2. Let’s say Node 1 and 2 got connected. Then we have to update the parent array, especially for Node 1 and Node 2.
When updating parents, we call it as ‘Union‘ operation, and usually set the value to be the smallest possible value.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 1 | 3 | 4 | 5 | 6 | 7 | 8 |
3. Now let’s suppose Node 3 was connected as below. Then we will have to perform ‘Union’ operation.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 1 | 2 | 4 | 5 | 6 | 7 | 8 |
However, from here, since Node 3 is not only connected with Node 2 but also with Node 1, we will have to update the parent array to include that information by updating Node 3 to have the same parent value as Node 2. We can use recursion from here to update the parent value.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 1 | 1 | 4 | 5 | 6 | 7 | 8 |
As Node 1, 2, 3 have the same parent, we can conclude those 3 nodes are connected and are under the same subset.
Code
// A utility function to find the parent of an element x
int find(int parent[], int x)
{
if (parent[x] == x)
return x;
parent[x] = find(parent, parent[x]);
return parent[x];
}
// A utility function to do union of two subsets
void union(int parent[], int x, int y)
{
int xParent = find(parent, x);
int yParent = find(parent, y);
// Usually set the lower value as the parent node
if(xParent < yParent)
parent[yParent] = xParent;
else
parent[xParent] = yParent;
} 
Will the Guru 
Leave a comment