🚟 Kruskal

Minimum Spanning Tree Problem §

Find the spanning tree of weighted-graph (connects all vertices) that has minimum cumulative weight.

Theory §

We greedily add the smallest unused edge to our MST if it doesn’t form a cycle. forms a cycle iff and are in the same connected component.

Implementation §

def kruskal(adj):
	edges = []
	for u in adj:
		for v, w in adj[u]:
			edges.append((u, v, w))
	edges.sort(key=lambda x: x[-1])
	uf = UnionFind(len(adj))
	ret = 0
	for u, v, w in edges:
		if uf.find(u) != uf.find(v):
			uf.join(u, v)
			ret += w
	return ret

Runtime §

Sorting the edges takes , but since , this is equivalent to . Each 🗼 Union-Find operation takes asymptotic , so iterating over edges takes .

Therefore, our runtime is dominated by the sorting, taking .