Education Journalist | Study Abroad Lead
Kruskal’s algorithm is named after Joseph Kruskal, who published it in 1956. The main idea of the algorithm is to sort the edges of the graph by their weight and then add them one by one to the Minimum Spanning Tree (MST), as long as they do not create a cycle. The algorithm can be implemented using a disjoint-set data structure, which allows us to efficiently check and merge the connected components of the graph.
The algorithm can be described as follows:
- Initialize an empty set S to store the edges of the MST.
- Sort all the edges of the graph by their weight in non-decreasing order.
- For each edge e in the sorted order:
- If adding e to S does not form a cycle, then add e to S.
- Otherwise, ignore it.
- Return S as the MST of the graph.
| Table of Content |
Keyterms: Algorithm, Minimum Spanning Tree, Graph, Disjoint-set, Spanning tree, Edge weight
Spanning Tree
[Click Here for Sample Questions]
A spanning tree of a graph is a subgraph that contains all the vertices and is a tree, meaning it has no cycles. A graph can have many spanning trees, but not all of them are equally good. Some spanning trees may have a smaller total weight than others, where the weight of a spanning tree is the sum of the weights of its edges.
A spanning tree has the following properties:
- It has the same number of vertices as the original graph, but fewer edges. In fact, it has exactly n - 1 edges, where n is the number of vertices.
- It is connected, meaning there is a path between any two vertices in the spanning tree.
- It is acyclic, meaning it has no cycles. This follows from the fact that it is a tree.
Read More:
Minimum Spanning Tree
[Click Here for Sample Questions]
A minimum spanning tree (MST) of a graph is a spanning tree that has the smallest possible weight among all the spanning trees of the same graph. A graph can have more than one MST, but they all have the same weight.
An MST has the following properties:
- It is a spanning tree, so it inherits all the properties of a spanning tree.
- It has the minimum weight among all the spanning trees of the graph.
- This means that if we add or remove any edge from the MST, the weight of the resulting spanning tree will be greater or equal to the weight of the MST.
- It satisfies the cut property, which states that for any cut of the graph (a partition of the vertices into two disjoint sets), the edge with the minimum weight that crosses the cut belongs to the MST.
- This property can be used to prove the correctness of some algorithms for finding MSTs.
- It satisfies the cycle property, which states that for any cycle in the graph, the edge with the maximum weight in the cycle does not belong to the MST.
- This property can be used to reduce the number of edges to consider in some algorithms for finding MSTs.
Example of Kruskal Algorithm
[Click Here for Sample Questions]
Use the graph with 9 vertices and 14 edges, each labelled with its weight.
Sort the edges by their weight in non-decreasing order. The sorted order is:
| Edge | Weight |
|---|---|
| 7-6 | 1 |
| 8-2 | 2 |
| 6-5 | 2 |
| 0-1 | 4 |
| 2-5 | 4 |
| 8-6 | 6 |
| 2-3 | 7 |
| 7-8 | 7 |
| 0-7 | 8 |
| 1-2 | 8 |
| 3-4 | 9 |
| 5-4 | 10 |
| 1-7 | 11 |
| 3-5 | 14 |
Then initialize an empty set S to store the edges of the MST. Use a disjoint-set data structure to keep track of the connected components of the graph. Initially, each vertex is in its own component.
Start with the edge 7-6, which has the lowest weight. Add it to S and merge the components containing 7 and 6.
- The edge 8-2 has the next lowest weight. We add it to S and merge the components containing 8 and 2.
- Then consider the edge 6-5, which has the same weight as 8-2. Add it to S and merge the components containing 6 and 5.
- Then consider the edge 0-1, which has the next lowest weight. Add it to S and merge the components containing 0 and 1.
- Then consider the edge 2-5, which has the same weight as 0-1. Cannot add it to S, because it would create a cycle with the edges 8-2 and 6-5. Therefore, ignore it.
- Then consider the edge 8-6, which has the next lowest weight. Cannot add it to S, because it would create a cycle with the edges 7-6 and 8-2. Therefore, ignore it.
- Then consider the edge 2-3, which has the next lowest weight. Add it to S and merge the components containing 2 and 3.
- Then consider the edge 7-8, which has the same weight as 2-3. Cannot add it to S, because it would create a cycle with the edges 7-6, 8-2, and 2-5. Therefore, ignore it.
- Then consider the edge 0-7, which has the next lowest weight. Add it to S and merge the components containing 0 and 7.
- Then consider the edge 1-2, which has the same weight as 0-7. Cannot add it to S, because it would create a cycle with the edges 0-1, 8-2, and 2-5. Therefore, ignore it.
- Then consider the edge 3-4, which has the next lowest weight. Add it to S and merge the components containing 3 and 4.
- Then consider the edge 5-4, which has the next lowest weight. Cannot add it to S, because it would create a cycle with the edges 6-5, 2-5, and 3-4. Therefore, we ignore it.
- We then consider the edge 1-7, which has the next lowest weight. We cannot add it to S, because it would create a cycle with the edges 0-1, 0-7, and 7-6. Therefore, we ignore it.
- We then consider the edge 3-5, which has the highest weight. We cannot add it to S, because it would create a cycle with the edges 2-3, 2-5, and 6-5. Therefore, we ignore it.
- At this point, we have added 8 edges to S, which is equal to the number of vertices minus 1. Therefore, we have found the MST of the graph and we can stop the algorithm. The MST is shown in red below, and its total weight is 1 + 2 + 2 + 4 + 7 + 8 + 9 = 33
Working of Kruskal’s Algorithm
[Click Here for Sample Questions]
Here is the step-by-step working of Kruskal’s Algorithm:
- The algorithm takes as input a connected, weighted, un-directed graph G with n vertices and m edges.
- The graph G can be represented by an adjacency list or an adjacency matrix, where each edge has a weight associated with it.
- The weight of an edge represents the cost or distance of connecting the two vertices that it joins.
- The algorithm outputs a minimum spanning tree (MST) of G, which is a subset of the edges of G that connects all the vertices together, without any cycles, and with the minimum possible total edge weight.
- The MST can be represented by a set of edges or a tree data structure, where each node has a parent pointer.
- The algorithm first sorts the edges of G by their weights in ascending order.
- This can be done using any sorting algorithm, such as merge sort, quick sort, or heap sort.
- The sorting takes O(m log m) time, where m is the number of edges. Alternatively, the algorithm can use a priority queue to store the edges and extract them in sorted order.
- This takes O(m log m) time to build the priority queue and O(m log m) time to extract the edges.
- The algorithm then initializes the MST as an empty set and the disjoint-set as a set of singleton sets, one for each vertex.
- The disjoint-set is a data structure that supports two operations: Find and Union.
- Find(x) returns the representative of the set that contains x, and Union(x, y) merges the sets that contain x and y, by making the representative of one set the parent of the representative of the other set.
- The disjoint set can be implemented using an array of integers, where each element stores the parent of the corresponding vertex.
- The initialization takes O(n) time, where n is the number of vertices.
- The algorithm then iterates over the sorted edges and for each edge (u, v), it checks if Find(u) is not equal to Find(v).
- This means that u and v belong to different sets or different trees in the forest.
- If this is the case, the algorithm adds (u, v) to the MST and calls Union(u, v) to merge the sets that contain u and v.
- This ensures that the MST remains acyclic and connected.
- If Find(u) is equal to Find(v), this means that u and v belong to the same set, or the same tree in the forest.
- If this is the case, the algorithm ignores (u, v), since adding it to the MST would create a cycle.
- The iteration takes O(m log n) time, using path compression and union by rank heuristics to optimize the disjoint-set operations.
- The algorithm stops when there is only one set left in the disjoint-set, or when it has added n-1 edges to the MST, where n is the number of vertices.
- The final MST is the set of edges that the algorithm has added.
Algorithm
[Click Here for Sample Questions]
To implement Kruskal’s algorithm, we need a data structure that can efficiently support the following operations:
- Find the tree that contains a given vertex
- Merge two trees into one
One such data structure is the disjoint-set data structure, also known as union-find. It represents each tree as a set of vertices, where one vertex is chosen as the representative or the parent of the set. It supports two main operations:
- Find(x): returns the representative of the set that contains x
- Union(x, y): merges the sets that contain x and y, by making the representative of one set the parent of the representative of the other set
Using this data structure, we can implement Kruskal’s algorithm as follows:
- Sort the edges by their weights in ascending order
- Initialize the MST as an empty set and the disjoint set as a set of singleton sets, one for each vertex
- For each edge (u, v) in the sorted order:
If Find(u) is not equal to Find(v):
- Add (u, v) to the MST
- Union(u, v)
- Return the MST
Pseudocode
The pseudocode for Kruskal’s algorithm is:
KRUSKAL(G): A = empty set DS = new DisjointSet(G.V) for each edge (u, v) in G.E, in ascending order by weight: if DS.Find(u) != DS.Find(v): A = A union {(u,v)} DS.Union(u,v) return A
Applications of Kruskal’s Algorithm
[Click Here for Sample Questions]
A few applications of Kruskal’s Algorithm are listed below:
- Network design: Kruskal’s algorithm can be used to find the minimum cost way to lay cables or wires to connect a set of nodes, such as computers, routers, or cities.
- Clustering: Kruskal’s algorithm can be used to cluster a set of points into groups based on their distances.
- Image segmentation: Kruskal’s algorithm can be used to segment an image into regions based on their pixel values.
Kruskal’s Algorithm vs Prim’s Algorithm
[Click Here for Sample Questions]
Difference between Kruskal’s Algorithm and Prim’s Algorithm:
| Kruskal’s algorithm | Prim’s algorithm |
|---|---|
| Sorts the edges by their weights and adds them one by one | Starts from an arbitrary vertex and adds the smallest weight edge that connects it to the MST |
| Uses a disjoint-set data structure to maintain a forest of disjoint trees | Uses a priority queue to maintain a set of candidate edges |
| Requires O(V + E) space | Requires O(V2) space, using an adjacency matrix representation of the graph |
| More suitable for sparse graphs, where E is much smaller than V2 | More suitable for dense graphs, where E is close to V2 |
Things to Remember
- Kruskal’s algorithm is named after Joseph Kruskal, who published it in 1956.
- The main idea of the algorithm is to sort the edges of the graph by their weight and then add them one by one to the Minimum Spanning Tree (MST), as long as they do not create a cycle.
- The algorithm can be implemented using a disjoint-set data structure, which allows us to efficiently check and merge the connected components of the graph.
- A spanning tree of a graph is a subgraph that contains all the vertices and is a tree, meaning it has no cycles.
- A minimum spanning tree (MST) of a graph is a spanning tree that has the smallest possible weight among all the spanning trees of the same graph.
- The algorithm takes as input a connected, weighted, un-directed graph G with n vertices and m edges.
Also Read:
Sample Questions
Ques. What is the main idea of Kruskal's algorithm? (3 marks)
Ans. The main idea of Kruskal's algorithm is to sort all the edges of the graph in the non-decreasing order of their weights and then pick the edges one by one in that order, adding them to the MST if they do not create a cycle. The algorithm stops when the MST has $$n-1$$ edges, where n is the number of vertices in the graph.Kruskal's algorithm selects the edges to add to the MST by using a greedy strategy, which means that it always chooses the edge with the lowest weight that does not create a cycle.
Ques. How does Kruskal's algorithm check if adding an edge to the MST creates a cycle or not? (3 marks)
Ans. Kruskal's algorithm checks if adding an edge to the MST creates a cycle or not by using a data structure called disjoint-set or union-find, which maintains a collection of disjoint sets and supports two operations: find and union. The find operation returns the representative element of the set that contains a given element. The union operation merges two sets that contain given elements into one set. Initially, each vertex of the graph is in its own set. Whenever we add an edge (u,v) to the MST, we perform a union operation on the sets that contain u and v. If u and v belong to the same set, then adding the edge (u, v) will create a cycle.
Ques. How does Kruskal's algorithm handle graphs with multiple MSTs? (3 marks)
Ans. Kruskal's algorithm handles graphs with multiple MSTs by choosing one of them arbitrarily, depending on the order of the edges in the sorted list. The cost of the MST produced by Kruskal's algorithm is always the same as the cost of any other MST of the graph.
Kruskal's algorithm handles graphs with negative edge weights by treating them as normal weights and applying the same greedy strategy. The algorithm does not change its behavior or output for negative edge weights, as long as the graph is connected and undirected.
Ques. Compare and contrast Kruskal's algorithm and Prim's algorithm. (5 marks)
Ans. Kruskal's algorithm and Prim's algorithm are two popular algorithms for finding the MST of a graph. Both of them are greedy algorithms, but they differ in how they choose the edges to add to the MST. Kruskal's algorithm picks the edges in the increasing order of their weights, regardless of where they are in the graph. Prim's algorithm starts from a vertex and picks the edge with the minimum weight that connects the current tree to a new vertex.
Some of the advantages and disadvantages of each algorithm are:
- Kruskal's algorithm is simpler and easier to implement than Prim's algorithm. It does not require a priority queue or a visited array to store the vertices.
- Kruskal's algorithm can handle disconnected graphs, while Prim's algorithm requires the graph to be connected. Kruskal's algorithm can find the minimum spanning forest of a disconnected graph, which is the union of the MSTs of each connected component.
- Prim's algorithm is faster for dense graphs, while Kruskal's algorithm is faster for sparse graphs. Prim's algorithm takes O(m + n \log n) time using a binary heap, while Kruskal's algorithm takes O(m \log m) time using a disjoint-set. For dense graphs, where m is close to n2, Prim's algorithm is more efficient. For sparse graphs, where m is close to n, Kruskal's algorithm is more efficient.
Ques. What are some of the applications of Kruskal's algorithm? (3 marks)
Ans. Some of the applications of Kruskal's algorithm are:
- Kruskal's algorithm can be used to find the optimal way to connect different locations, such as cities, airports, or computers, with the minimum cost or distance.
- Kruskal's algorithm can be used to find the minimum cost-spanning tree of a graph that represents a circuit board, where the vertices are components and the edges are wires.
- Kruskal's algorithm can be used to find the maximum bottleneck path in a graph, which is the path that has the maximum capacity among all the paths between two vertices. This can be done by reversing the order of the edge weights and applying Kruskal's algorithm.
Ques. What is the space complexity of Kruskal's algorithm? (3 marks)
Ans. The space complexity of Kruskal's algorithm is O(n + m), where n is the number of vertices and m is the number of edges in the graph. This is because we need to store the sorted list of edges, the set of edges in the MST, and the disjoint-set data structure. The sorted list of edges requires O(m) space, the set of edges in the MST requires O(n) space, and the disjoint-set data structure requires O(n) space.
Ques. What is a minimum spanning tree of a graph? How is it different from a spanning tree? (2 marks)
Ans. A minimum spanning tree (MST) of a graph G is a spanning tree T that has the minimum possible sum of weights of its edges. The weight of a spanning tree is the sum of the weights of its edges. An MST is different from a spanning tree in that it minimizes the total weight of the edges, while a spanning tree does not have any such constraint.
Ques. What is a spanning tree of a graph? (5 marks)
Ans. A spanning tree of a graph G is a subgraph T that satisfies the following properties:
- T contains all the vertices of G.
- T is a tree, meaning that there is no cycle in the subgraph.
- T is a subgraph of G, meaning that every edge in T belongs to G.
- Write a Python function that implements Kruskal's algorithm using the disjoint-set data structure. The function should take a graph as an input and return the MST as an output. You can use the following template for the disjoint-set class.
```python
# A class to represent a disjoint-set data structure
class DisjointSet:
# A constructor to initialize the parent and rank arrays
def __init__(self, n):
# n is the number of vertices in the graph
# parent[i] stores the parent of vertex i
# rank[i] stores the rank of the set that contains vertex i
self.parent = [i for i in range(n)]
self.rank = [0 for i in range(n)]
# A function to find the representative of the set that contains x
def find(self, x):
# If x is not the root, recursively find the parent of x
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
# Return the parent of x
return self.parent[x]
# A function to merge the sets that contain x and y
def union(self, x, y):
# Find the representatives of x and y
xroot = self.find(x)
yroot = self.find(y)
# If x and y belong to the same set, do nothing
if xroot == yroot:
return
# If the rank of x's set is smaller than y's set, make y's set the parent of x's set
if self.rank[xroot] < self.rank[yroot]:
self.parent[xroot] = yroot
# If the rank of y's set is smaller than x's set, make x's set the parent of y's set
elif self.rank[xroot] > self.rank[yroot]:
self.parent[yroot] = xroot
# If the ranks are equal, make x's set the parent of y's set and increment the rank of x's set
else:
self.parent[yroot] = xroot
self.rank[xroot] += 1
Ans. The Python function that implements Kruskal’s algorithm using the disjoint-set data structure is:
# A function to implement Kruskal's algorithmdef kruskal(graph):
# graph is a list of edges with weights, such as [(0, 1, 2), (1, 2, 3), ...]
# n is the number of vertices in the graph
n = max(max(u, v) for u, v, w in graph) + 1
# Sort the edges by weights in non-decreasing order
graph.sort(key=lambda x: x[2])
# Initialize an empty list to store the edges of the MST
MST = []
# Initialize a disjoint-set data structure with n sets, one for each vertex
ds = DisjointSet(n)
# Loop through the edges in the sorted order
for u, v, w in graph:
# If the MST has n-1 edges, stop the loop
if len(MST) == n-1:
break
# Get the representatives of the sets that contain u and v
uroot = ds.find(u)
vroot = ds.find(v)
# If u and v belong to different sets, then adding (u, v, w) will not create a cycle
if uroot != vroot:
# Add (u, v, w) to the MST
MST.append((u, v, w))
# Merge the sets that contain u and v
ds.union(uroot, vroot)
# Return the MST as the output
return MST
For Latest Updates on Upcoming Board Exams, Click Here: https://t.me/class_10_12_board_updates
Check-Out:
Comments