Kruskal's Algorithm

Introduction to Kruskal’s Algorithm

Suppose that there are some villages in a town, you being the Mayor of the town want to visit all the villages but you have very little time for it.

So you will be interested in visiting the villages in such a way that the total distance covered by you during the visit is minimum possible. Isn't it.?

If you try to formulate the above problem in terms of graph theory, by considering villages as the vertices, roads connecting them as the edges, and the distance of each road as the weight of the corresponding edge.

Kurskal's algorithm will help you in this case because it is used to find the minimum spanning tree (MST) of any given connected, weighted, undirected graph. Before discussing any further details of Kruskal's algorithm let's see what is meant by a Minimum spanning tree of a graph.

A spanning tree is a subgraph of a connected, undirected graph such that it is a tree and it includes all the vertices. So a minimum spanning tree would correspond to a spanning tree with the minimum weight. Where the weight of a spanning tree is the sum of the weight of the edges present in it.

For Example:

The below-given image shows a graph $G$ with 6 vertices and 9 edges

This graph can have multiple spanning tree some of which are shown below with their respective weights.

But they can not be considered as minimum spanning trees as there exists at least one spanning tree with an even smaller sum of edge weights. The MST of the graph is -

The MST of the given graph has a weight of 17, which means that we can't form any other spanning tree of graph $G$ whose weight is less than 17.

Kruskal's Algorithm Implementation

The main idea of Kruskal's algorithm to find the MST of a graph $G$ with $V$ vertices and $E$ edges is

• to sort all the edges in ascending order according to their weights.
• Then select the first $V-1$ edges such that they do not form any cycle within them.

Algorithm of Kruskal's

For any graph, $G=(V,E)$, finding an MST using Kruskal's algorithm involves the following steps -

• Sort all the edges of the graph in ascending order of their weights.
• Check the edge with minimum weight, if including it in the answer forms a cycle discard it, otherwise include it in the answer.
• Repeat the above step until we have chosen $V-1$ edges.

Example of Kruskal's Algorithm

Let's say we want to find the MST of the underlying connected, weighted, undirected graph with $6$ vertices and $9$ edges-

Now as per the algorithm discussed above, to find the MST of this graph -

1. We will write all the edges sorted in ascending order according to their respective weights
2. Then we will select the first $V-1=5$ edges which do not form cycles.

• Step 1 - Sort the edges in ascending order. Here is the list after sorting.

  No.	$u$	$v$	Weight
  1	4	5	2
  2	4	6	2
  3	3	4	3
  4	2	3	3
  5	3	5	4
  6	5	6	5
  7	2	5	6
  8	1	2	7
  9	1	3	8

• Step 2 - Choose 5 edges from starting which do not form a cycle.

  • Checking edge $4\Longleftrightarrow 5$ - This is the first edge so it can't form any cycle hence including this in result -

    

  • Checking for edge $3\Longleftrightarrow 4$ - Including this edge in the result does not form any cycle.

  • Checking for edge $2\Longleftrightarrow 3$ - Again including this edge in the result does not form any cycle.

  • Checking for edge $3\Longleftrightarrow 5$ - Including this edge in the result forms a cycle $3 \rightarrow 4 \rightarrow 5 \rightarrow 3$, hence not including this in the result.

  • Checking for edge $5\Longleftrightarrow 6$ - Including this edge in the result forms a cycle $4 \rightarrow 5 \rightarrow 6 \rightarrow 4$, hence not including this in the result.

  • Checking for edge $2\Longleftrightarrow 5$ - Including this edge in the result forms a cycle $2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2$, hence not including this in the result.

  • Checking for edge $1\Longleftrightarrow 2$ - Including this edge in the result does not form any cycle. By including this, we have included 5 edges so now the result will correspond to the minimum spanning tree.

After including all $5$ edges, the MST will look like this -

So the weight of MST can be calculated as $7+3+3+2+2=17$.

Pseudocode of Kruskals Algorithm

Code Example of C/C++, Python

To efficiently check whether including an edge forms a cycle or not, we will use an already discussed concept $i.e.$ Disjoint-Sets. We will proceed as per the pseudocode and algorithm discussed above, $i.e.$ firstly sorting the list of edges and then including $V-1$ edges that do not form cycles. Find function of DSU will be used before including any edge in the MST to check if both the endpoints (nodes) of the edge belong to the same set or not. If they do not belong to the same set, we will include that edge in the MST as including the edge is not forming any cycle. Now we will use the union function of DSU to merge the two disjoint sets. Before going into the code, let's see its blueprint -

Variables -

• $V$ - A global variable that will denote the number of vertices present in the graph.
• $E$ - Again a global variable denoting the count of edges present in the graph.
• $edges$ - A list of edges that will be sorted and then used in the Kruskal algorithm.

Method -

• $MST\_Kruskal$ - A function that is responsible to find the MST of a given graph implemented as discussed in the algorithm and pseudocode.

Java Implementation of Kruskal's Algorithm

Complexity Analysis

• Time Complexity -
  • Sorting of $E$ edges costs us $O(E*log(E))$ time.
  • For each edge, we are using the Union-Find algorithm which costs us $O(E*\alpha(V))$ time.
  • As discussed in DSU, for practical values of $V$, $i.e.$ $V\leq 10^{80}$ we can write $O(E*\alpha(V))$ as $O(E)$ because $O(\alpha(V))$ $\simeq$ $O(1)$.
  Hence, the overall time complexity is $O(E*log(E)+E)$ $\simeq$ $O(E*log(E))$
• Space Complexity - We are using a List/Vector to store the $E$ edges of the given graph so the space complexity is $O(E)$.

Applications of Kruskal's Algorithm

MST's which can be found using the Kruskal algorithm has the following applications -

• In-network designing, finding MST tells you the minimum amount of wire needed to connect all the nodes (servers).
• Approximation of NP-Hard problems, like we can use MST to solve the traveling salesman problem.
• It is used in autoconfig protocol for ethernet bridging, which helps to avoid cycles in a network.
• All other graph theory problems where we need to visit all the vertices with minimum cost.