Kruskal's Algorithm

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Kruskal's Algorithm

Table of Contents

Contents are not accessible

Kruskal’s algorithm is a popular method for finding the Minimum Spanning Tree (MST) of a connected, undirected graph. It uses a greedy approach to build the MST by selecting edges in increasing order of their weights.

The key feature of Kruskal’s algorithm is its use of the Union-Find data structure to efficiently manage and detect cycles, ensuring the resulting tree has the smallest possible total edge weight.

Overall, Kruskal’s algorithm guarantees an optimal solution for finding the MST by always choosing the smallest edge that does not create a cycle, thus ensuring the minimum total weight of the spanning tree. This makes it widely used in network design, clustering, and other applications where optimal connectivity is required.

Step-by-Step Algorithm

Sort all edges in non-decreasing order of their weight.
Initialize an empty result array to store the resultant MST.
Create V subsets with single elements.
Iterate through all sorted edges:
- Pick the smallest edge.
- Check if it forms a cycle with the spanning tree formed so far using the Union-Find data structure.
- If it does not form a cycle, include it in the result.
- Perform the union of the subsets.
Repeat step 4 until there are (V-1) edges in the result.
Print the result, which contains the edges of the constructed MST.

Algorithm Walkthrough

Consider the example used in the code with the following edges and weights:

Edges: (0-1, 0-2, 0-3, 1-3, 2-3)
Weights: 10, 6, 5, 15, 4
Vertices: 4 (0, 1, 2, 3)

Sort the edges by weight:

Sorted edges: (2-3, 4), (0-3, 5), (0-2, 6), (0-1, 10), (1-3, 15)

Initialize subsets for each vertex:
```
Subsets: [0, 1, 2, 3]
```
Iterate through sorted edges and build MST:
- Edge (2-3, 4):
  - Find sets of vertices 2 and 3: they belong to different sets.
  - Include edge (2-3) in the result.
  - Perform union of sets containing 2 and 3.
```
Result: [(2-3, 4)]
Subsets: [0, 1, 2, 2]
```
- Edge (0-3, 5):
  - Find sets of vertices 0 and 3: they belong to different sets.
  - Include edge (0-3) in the result.
  - Perform union of sets containing 0 and 3.
```
Result: [(2-3, 4), (0-3, 5)]
Subsets: [2, 1, 2, 2]
```
- Edge (0-2, 6):
  - Find sets of vertices 0 and 2: they belong to the same set (cycle detected).
  - Skip this edge.
```
Result: [(2-3, 4), (0-3, 5)]
Subsets: [2, 1, 2, 2]
```
- Edge (0-1, 10):
  - Find sets of vertices 0 and 1: they belong to different sets.
  - Include edge (0-1) in the result.
  - Perform union of sets containing 0 and 1.
```
Result: [(2-3, 4), (0-3, 5), (0-1, 10)]
Subsets: [2, 2, 2, 2]
```
- Edge (1-3, 15):
  - All vertices are already connected, so this edge is skipped.
Final MST:
```
Edges: (2-3, 4), (0-3, 5), (0-1, 10)
```

Code

Python3

. . . .

Complexity Analysis

Time Complexity

Sorting of edges: The time complexity for sorting the edges is $O(E \log E)$ , where (E) is the number of edges.
Find and Union operations: These operations are performed in almost constant time, $O(\log V)$ , due to the use of the Union-Find data structure with path compression and union by rank. Since we perform these operations (E) times, the total complexity is $O(E \log V)$ .

Therefore, the overall time complexity of Kruskal's algorithm is $O(E \log E + E \log V)$ . Since $E \log E$ dominates $E \log V$ , the time complexity can be simplified to $O(E \log E)$ .

Space Complexity

Edge list: The space required to store all edges is $O(E)$ .
Subset array: The space required to store the subset information is $O(V)$ .

Thus, the overall space complexity is $O(E + V)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible