Exploring Time Complexity of Kruskal’s Algorithm in Python
This article is a complementary resource to the DSA with Python course.
This article is a complementary resource to the DSA with Python course.
Exploring Time Complexity of Kruskal’s Algorithm in Python
Kruskal's algorithm finds the Minimum Spanning Tree (MST) of a connected, undirected and weighted graph.
In this article, we will analyze the time complexity of a Python implementation of Kruskal's algorithm.
Kruskal's algorithm works by:
To check for cycles quickly, the implementation uses a Union-Find (disjoint set) data structure. Two vertices that already share a root are in the same tree, so an edge between them would form a cycle.
class UnionFind:
def __init__(self, vertices_count):
self.parent = list(range(vertices_count))
self.rank = [0] * vertices_count
def find(self, vertex):
# Path compression: point every vertex on the way straight at the root
if self.parent[vertex] != vertex:
self.parent[vertex] = self.find(self.parent[vertex])
return self.parent[vertex]
def unite(self, root_u, root_v):
# Union by rank: attach the shorter tree under the taller one
if self.rank[root_u] < self.rank[root_v]:
root_u, root_v = root_v, root_u
self.parent[root_v] = root_u
if self.rank[root_u] == self.rank[root_v]:
self.rank[root_u] += 1
def kruskal_mst(edges, vertices_count):
# Sort edges based on their weights
edges = sorted(edges, key=lambda edge: edge[2])
# Create Union-Find instance
uf = UnionFind(vertices_count)
mst = [] # Output list to store MST
# Iterate over all the edges
for u, v, weight in edges:
# Find the root of each vertex
root_u = uf.find(u)
root_v = uf.find(v)
# If the roots are not the same,
# unite them and add the edge to MST
if root_u != root_v:
mst.append((u, v, weight))
uf.unite(root_u, root_v)
return mst
Here, each edge is a tuple (u, v, weight), and the vertices are numbered from 0 to vertices_count - 1.
The time complexity of this algorithm can be broken down into the following parts:
1. Sorting the Edges
The algorithm sorts the edges in non-decreasing order of their weights using Python's built-in sorted() function.
The time complexity of this operation is O(E logE), where E is the number of edges in the graph.
2. Union-Find Operations
For every edge, the algorithm calls find() twice and unite() at most once.
Union by rank keeps every tree at most logV levels tall, where V is the number of vertices. So each operation takes at most O(logV) time, and all of them together take at most O(E logV).
Note: Path compression makes the trees even flatter. With both techniques, each operation takes nearly constant time on average, so this part is usually much faster than the bound above.
3. Iterating over the Edges
The loop visits every edge once to decide whether it joins the MST. Apart from the Union-Find calls, the work per edge is constant, so this takes O(E) time.
The overall time complexity of Kruskal's algorithm is the sum of the three parts:
O(E logE) + O(E logV) + O(E)
A simple graph has at most V2 edges, so logE is at most 2logV. That makes O(E logV) no larger than O(E logE), and sorting dominates. Therefore, the algorithm's overall complexity is O(E logE).
1. Dense Graph
In a dense graph, the number of edges E is close to the square of the number of vertices V.
Therefore, the overall time complexity is <katex>O(V^{2} logV)</katex>.
Note: The time complexity should actually be <katex>O(V^{2} logV^{2})</katex>. Using the logarithmic property, it becomes <katex>O(V^{2} * 2logV)</katex>. We simply neglect the constant 2 to obtain <katex>O(V^{2} logV)</katex>.
2. Sparse Graph
In a sparse graph, the number of edges E is close to the number of vertices V.
Therefore, the overall time complexity is O(V logV).