Introduction
Kruskal’s algorithm is used to find the minimum/maximum spanning tree. A minimum spanning tree is a spanning tree whose weight is as small as possible.
Implementation
def kruskal(N, edges):
weights = 0
uf = DSU()
# edges = (u, v, weight)
edges.sort(key = lambda x : x[2])
# To find minimum spanning tree
for a, b, w in edges:
if not uf.same(a, b):
uf.union(a, b)
weights += w
return weights
Complexity
-
Time complexity: or
- Sorting edges:
- Union-Find operations: , where is the inverse Ackermann function
- Since grows extremely slowly and is effectively constant, this becomes
- Overall complexity is dominated by the sorting step
-
Space complexity:
- Edge list:
- Union-Find data structure: