Connect every node in a network using the absolute minimum total wire length.
A Minimum Spanning Tree (MST) connects all vertices in a weighted graph together, without any cycles, and with the minimum possible total edge weight.
Kruskal's Algorithm builds the MST by sorting all edges from cheapest to most expensive. It walks through them, adding an edge if and only if it doesn't create a cycle. How does it know if there's a cycle instantly? It uses a Union-Find (DSU) structure!
def kruskal(n, edges):
dsu = DSU(n) # Union-Find
mst_weight = 0
mst_edges = []
# Sort edges by weight
edges.sort(key=lambda x: x[2])
for u, v, weight in edges:
# If they aren't already connected, add the edge
if dsu.find(u) != dsu.find(v):
dsu.union(u, v)
mst_weight += weight
mst_edges.append((u, v))
if len(mst_edges) == n - 1:
break
return mst_weight, mst_edges