DSA Kruskal's
Kruskal's Algorithm
In an undirected network, Kruskal’s approach determines the Minimum Spanning Tree (MST), also known as the Minimum Spanning Forest.
==== EXAMPLE MUKAVU ====
The set of edges that connects all vertices—or as many as possible—with the least amount of total edge weight is known as the MST (or MSTs) discovered by Kruskal’s algorithm.
Beginning with the edges that have the lowest edge weights, Kruskal’s algorithm adds edges to the Minimum Spanning Forest, or MST.
The MST does not include edges that might start a cycle. The animation above shows these as the red blinking lines.
The animation above is designed to halt when the Minimum Spanning Forest (MST) is finished, preventing you from having to wait for the longest edges to be verified. Kruskal’s algorithm checks every edge in the graph.
When a graph has many Minimum Spanning Trees, it is referred to as a Minimum Spanning Forest. When a graph is disconnected, something occurs. Use the checkbox in the animation above to give it a try.
In contrast to Prim’s approach, Kruskal’s algorithm can be applied to non-connected networks of this kind, meaning it can identify several Minimum Spanning Forests, or MSTs.
Union-Find cycle detection within Kruskal’s method will be used to determine whether an edge will result in a cycle.
How it works:
1.The graph’s edges are sorted from lowest to highest edge weight.
2.Beginning with the edge that has the least weight on each edge:
a.Will the present MST cycle as a result of this edge?
In that case, include the edge as an MST edge.
Manual Run Through
Before we try to program Kruskal’s method, let’s run through it manually on the graph below to make sure we grasp all of the intricate, step-by-step procedures.
The MST is expanded by adding the first three edges. The following three edges don’t form any cycles and have the lowest edge weights:
- C–E, two weights
- D–E, three weights
- A-B, four weights
Edge C-D (highlighted in red) cannot be added after that since doing so would create a cycle.
Kruskal’s approach attempts to add the following four edges to the MST:
- E-G, weighing six
- C-G, weight seven (omitted)
- D–F, weighing seven
- B–C, weighing eight
It is not possible to add Edge C-G (highlighted in red) to the MST since doing so would start a cycle.
As you can see, at this stage the MST has already been generated, but Kruskal’s algorithm will keep running until every edge is examined to see whether it may be included in the MST.
The edges with the highest edge weights are the final three that Kruskal’s algorithm attempts to add to the MST:
- Weight 9 (not added) for A–C
- Weight 10 (not added) for A–G
- Weight 11 (not added) for F-G
These edges cannot be added because adding them would result in a cycle in the MST.
Now, Kruskal’s algorithm is complete.
To observe Kruskal’s algorithm perform the previously completed manual steps, run the simulation below.
==== EXAMPLE MUKAVU ====
Note: The animation at the top of this page ends immediately after the final edge is added to the Minimum Spanning Forest, or MST, even though Kruskal’s algorithm checks every edge in the graph. This way, we avoid having to look at every red edge that can’t be added.
This is feasible since there is only one MST for a linked graph, and the search can end when the MST’s edge count is one fewer than the graph’s vertex count (V−1.Our animation features two MSTs for the unconnected graph, and the method terminates when the MSTs reach a size of V−2.overall edges.
Implementation of Kruskal's Algorithm
We develop a Graph class in order for Kruskal’s approach to find a Minimum Spanning Tree (MST), or a Minimum Spanning Forest. Afterwards, we will construct the graph from the example above and apply Kruskal’s algorithm to it using the methods in this Graph class.
class Graph:
def __init__(self, size):
self.size = size
self.edges = [] # For storing edges as (weight, u, v)
self.vertex_data = [''] * size # Store vertex names
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.edges.append((weight, u, v)) # Add edge with weight
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
Lines 8 and 12: Determine whether the input parameters, vertex, v, and u, are within the acceptable range of index values.
These two find and union methods are also defined inside the Graph class in order to perform Union-Find cycle identification in Kruskal’s algorithm:
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
Lines 15–18: The find method recursively locates a vertex’s root by using the parent array. The parent array contains an index (reference) to the parent of each vertex. When the find method encounters a vertex in the parent array that points to itself, it finds the root vertex. See how the parent array and the find method are utilized by the kruskals_algorithm method by continuing to read.
Lines 20–29: The union function unites (unions) two trees when an edge is added to the MST by using the parent array. For each root vertex, the rank array contains a rough approximation of the tree height. A lower rank root becomes a child of the root vertex of the other tree when two trees merge.
The Graph class has a function that implements Kruskal’s algorithm as follows:
def kruskals_algorithm(self):
result = [] # MST
i = 0 # edge counter
self.edges = sorted(self.edges, key=lambda item: item[2])
parent, rank = [], []
for node in range(self.size):
parent.append(node)
rank.append(0)
while i < len(self.edges):
u, v, weight = self.edges[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
result.append((u, v, weight))
self.union(parent, rank, x, y)
print("Edge \tWeight")
for u, v, weight in result:
print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")
Line 35: Before Kruskal’s algorithm tries to add the edges to the MST, the edges need to be sorted.
Line 40-41: First, the parent and rank arrays are set up. Initially, each vertex has no height (0 values in the rank array) and is its own root (every element in the parent array points to itself).
Lines 44–45: Select the shortest edge and increase i so that the subsequent iteration selects the right edge.
Lines 47–51: The trees are merged if there is no cycle for the new edge and the vertices u and v at either end of the current edge have different roots, x and y. The current edge is added to the result array in order to combine the trees, and the union method is then used to ensure that the trees are merged appropriately and that the merged tree contains just one root vertex.
We will now construct the graph from the “Manual Run Through” and apply Kruskal’s algorithm on it:
Example
Python:
class Graph:
def __init__(self, size):
self.size = size
self.edges = [] # For storing edges as (weight, u, v)
self.vertex_data = [''] * size # Store vertex names
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.edges.append((u, v, weight)) # Add edge with weight
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskals_algorithm(self):
result = [] # MST
i = 0 # edge counter
self.edges = sorted(self.edges, key=lambda item: item[2])
parent, rank = [], []
for node in range(self.size):
parent.append(node)
rank.append(0)
while i < len(self.edges):
u, v, weight = self.edges[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
result.append((u, v, weight))
self.union(parent, rank, x, y)
print("Edge \tWeight")
for u, v, weight in result:
print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(0, 1, 4) #A-B, 4
g.add_edge(0, 6, 10) #A-G, 10
g.add_edge(0, 2, 9) #A-C, 9
g.add_edge(1, 2, 8) #B-C, 8
g.add_edge(2, 3, 5) #C-D, 5
g.add_edge(2, 4, 2) #C-E, 2
g.add_edge(2, 6, 7) #C-G, 7
g.add_edge(3, 4, 3) #D-E, 3
g.add_edge(3, 5, 7) #D-F, 7
g.add_edge(4, 6, 6) #E-G, 6
g.add_edge(5, 6, 11) #F-G, 11
print("Kruskal's Algorithm MST:")
g.kruskals_algorithm()
Time Complexity for Kruskal's Algorithm
See this article for a broad description of time complexity.
Along with E Given the quantity of edges in our graph, Kruskal’s algorithm’s time complexity is
O(E⋅logE)
We get this time complexity because the edges must be sorted before Kruskal’s can start adding edges to the MST. Using a fast algorithm like Quick Sort or Merge Sort gives us a time complexity of O(E⋅logE) for this sorting alone.
Following sorting, each edge is examined individually to determine if it will form a cycle; if not, it is added to the MST.
It is still possible to think of this as a single operation even though it is laborious to use the union technique to add an edge to the MST and the find method to determine whether a cycle will be produced. Because it takes around constant time, we can view this as a single operation. This indicates that this operation does not add to the overall time complexity because the time it takes to complete it grows very little as the graph does.
Kruskal’s approach is particularly quick for sparse networks, where the ratio between the number of edges and the total number of edges determines the time complexity, because it only depends on the number of edges E. E and how many vertices there are Vis comparatively minimal.
