Kruskal’s Algorithm: Minimum Spanning Tree Algorithm Explained

Kruskal’s algorithm is an algorithm that is used to find the minimum spanning tree (MST) of a connected, undirected graph. It identifies the least spanning tree of an undirected edge-weighted graph. If the graph is connected, it finds the least spanning tree.

The algorithm’s essential steps include sorting and detecting cycles using a disjoint-set data structure. Its running time is dominated by the time spent sorting all of the graph edges by weight.

A minimum spanning tree of a linked weighted graph is a connected subgraph without cycles whose sum of edge weights is minimal.

A disconnected minimal spanning graph is made up of a minimum spanning tree for every connected component. Joseph Kruskal initially released this algorithm in 1956, and Loberman and Weinberger found it shortly after.

What is Kruskal Algorithm?

Kruskal’s algorithm is covered in the graph theory of discrete mathematical concepts. It determines the shortest path between two points in a connected weighted graph.

This algorithm transforms a given graph into a tree by treating each node as a separate tree. These trees can only be linked if the edge linking them has a low value and does not form a cycle in the MST structure.

As previously stated, the Kruskal technique is used to create the minimal spanning tree for a given graph.

But what exactly defines a minimal spanning tree? A minimum spanning tree is a subset of a graph that contains the same number of edges as the graph and edges equal to the number of vertices minus one.

It also has a low cost for the total of all edge weights in a spanning tree. Kruskal’s algorithm sorts all edges in ascending order of edge weights and adds nodes to the tree only if the selected edge does not form a cycle.

Furthermore, it selects the edge with the lowest cost first and the edge with the highest cost last.

As a result, you can argue that the Kruskal algorithm makes a locally optimal option to get the globally optimal answer. That is why it is known as the Greedy Algorithm.

Know from our experts what a minimum spanning tree is and how to build a minimum spanning tree from a given graph using Kruskal’s algorithm.

What is a Minimum Spanning Tree?

A minimal spanning tree (MST) is a subset of edges in a connected, edge-weighted graph that link all vertices without any cycles and with the lowest feasible total edge weight.

It is a method of determining the most cost-effective way to connect a set of vertices. A minimum-spanning tree is not always unique.

All edge weights in the MST must be distinct. If all of the edges in the graph have the same weight, every spanning tree is an MST.

The edges of the minimal spanning tree can be discovered using the algorithm, as well as the more complicated Kruskal or Prim’s algorithms.

Working of Kruskal’s Algorithm

Kruskal’s Algorithm is the recommended method for finding the shortest-spanning tree in a linked weighted graph. The main purpose of this technique is to find a subset of edges that may be used to visit each vertex of the graph.

It employs the greedy technique, which seeks an optimal explanation at each step rather than focusing on a global optimum.

You can watch the video where our instructor is teaching real-world MST problem. It’s easier to comprehend.

Here, we select the edges with the lowest weight and continue counting the edges till we reach our target. To run the Kruskal’s algorithm, we must follow the procedures listed below:

• First, we will sort all of the edges by weight (low to high).
• Now we’ll select the edge with the least weight and associate it with the spanning tree. If the edge being added results in a cycle, it should be denied.
• Continue adding edges until all vertices are added and a minimum spanning tree is produced.

Kruskal’s Algorithm Examples

Example 1: Consider a weighted graph with vertices A, B, C, D, and E, and the following edges with their respective weights:

1. AB with weight 2
2. AC with weight 3
3. AD with weight 1
4. BC with weight 4
5. BD with weight 2
6. BE with weight 3
7. CD with weight 5
8. CE with weight 4
9. DE with weight 6

To apply Kruskal’s Algorithm:

1. Sort all the edges in a non-decreasing order of their weights.
2. Initialize an empty set to store the minimum spanning tree (MST).
3. Iterate through each edge in the sorted order:some text
   • If adding the edge to the MST does not form a cycle, add it to the MST.
   • Otherwise, skip it.
4. Continue this process until all vertices are connected.

Applying Kruskal’s Algorithm:

1. Sort the edges in non-decreasing order of weights: AD, AB, BD, AC, BE, BC, CE, CD, DE
2. Begin with an empty MST.
3. Add the edges in the following order:some text
   • AD (weight 1)
   • AB (weight 2)
   • BD (weight 2)
   • AC (weight 3)
   • BE (weight 3)
   • CE (weight 4)
   • BC (weight 4)
   • CD (weight 5)
   • DE (weight 6)

The resulting minimum spanning tree consists of the edges: AD (weight 1), AB (weight 2), BD (weight 2), AC (weight 3), BE (weight 3), CE (weight 4), and CD (weight 5).

Finally, it constructs the Minimum Spanning Tree (MST) using Kruskal’s Algorithm and prints the edges of the MST.

Creating Minimum Spanning Tree Using Kruskal Algorithm

To create a minimum spanning tree (MST) using Kruskal’s algorithm, follow these steps:

1. Sort Edges: Sort all the edges in the graph in a non-decreasing order of their weights.
2. Initialize MST: Create an empty set to store the minimum spanning tree.
3. Iterate Over Edges: Iterate through each edge in the sorted order.some text
   • If adding the edge to the MST does not create a cycle, add it to the MST.
   • Otherwise, skip it.
4. Repeat: Continue this process until all vertices are connected.

Let’s illustrate this process with an example:

Consider the following graph:

4 3

 A ——- B ——- C

 | \ | |

 1| \2 |6 |5

 | \ | |

 D ——- E ——- F

 7 4

1. Sort Edges:some text
   • AD (1), AB (4), AE (2), BC (3), BE (6), EF (5), DE (7)
2. Initialize MST: Start with an empty set.
3. Iterate Over Edges:a. Add AD (1) to the MST.b. Add AB (4) to the MST.c. Add AE (2) to the MST.d. Add BC (3) to the MST.e. Add EF (5) to the MST.
4. Resulting MST:

4 3

 A ——- B ——- C

 | | |

 1| 6| |5

 | | |

 D ——- E ——- F

 7 4

The resulting MST connects all vertices with the minimum total weight.

Implementation of Kruskal’s Algorithm

Implementation of Kruskal’s Algorithm involves creating a minimum spanning tree (MST) for a given connected, undirected graph. The algorithm efficiently finds the subset of edges that connects all the vertices in the graph while minimizing the total edge weight.

Here’s a detailed explanation of how Kruskal’s Algorithm is implemented:

1. Sort Edges: Initially, all the edges in the graph are sorted in a non-decreasing order of their weights. This step ensures that we consider edges with the lowest weights first.
2. Initialize MST and Disjoint Set: Create an empty set to store the MST. Also, initialize a disjoint set data structure to keep track of disjoint sets of vertices.
3. Iterate Over Edges: Iterate through each edge in the sorted order. For each edge:some text
   • Check if adding the edge to the MST would create a cycle. This is done by checking if the vertices of the edge belong to the same disjoint set.
   • If adding the edge does not create a cycle, add it to the MST and merge the disjoint sets of its vertices.
4. Repeat: Continue this process until all vertices are connected or all edges are considered.
5. Output MST: The resulting set of edges forms the minimum spanning tree of the graph.

1. Sort Edges: The edges are sorted based on their weights: AD (1), AB (4), AE (2), BC (3), BE (6), EF (5), DE (7).
2. Initialize MST and Disjoint Set: We start with an empty MST and initialize disjoint sets for each vertex.
3. Iterate Over Edges:some text
   • Add AD (1) to the MST and merge sets containing vertices A and D.
   • Add AB (4) to the MST and merge sets containing vertices A and B.
   • Add AE (2) to the MST and merge sets containing vertices A and E.
   • Add BC (3) to the MST and merge sets containing vertices B and C.
   • Add EF (5) to the MST and merge sets containing vertices E and F.

The resulting MST connects all vertices with the minimum total weight. This implementation efficiently finds the minimum spanning tree of a graph, making it a widely used algorithm in various applications, such as network design and clustering.

Question on the Kruskal algorithm is asked to various tech professionals in the computer science field. In machine learning, it is asked for clustering algorithms and data structures for optimization in large datasets.

FAQ: Kruskal’s Algorithm

1. What is Kruskal’s Algorithm?
Kruskal’s Algorithm is an algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. It aims to connect all the vertices of the graph with the minimum total edge weight.

2. How does Kruskal’s Algorithm work?
Kruskal’s Algorithm works by iteratively selecting edges from the graph in increasing order of their weights and adding them to the MST if they do not create a cycle. It continues this process until all vertices are connected or all edges are considered.

3. When should Kruskal’s Algorithm be used?
Kruskal’s Algorithm is suitable for finding the MST of a graph when the edges have distinct weights and the graph is sparse (i.e., it has relatively few edges compared to the number of vertices).

4. What is the time complexity of Kruskal’s Algorithm?
The time complexity of Kruskal’s Algorithm is O(E log E), where E is the number of edges in the graph. This complexity arises mainly from the sorting of edges based on their weights.

5. How does Kruskal’s Algorithm handle disconnected graphs?
Kruskal’s Algorithm assumes that the input graph is connected. If the graph is disconnected, the algorithm will produce a minimum spanning tree that consists of MSTs for each connected component of the graph.

Related Articles: 

• Linear Regression in Machine Learning
• Machine Learning vs Data Science
• FAANG interview tips for Software Engineers
• Long Short Term Memory Explained with Examples