Ett minimalt spännträd (MST) förbinder alla hörn i en viktad, sammanhängande graf med den minimala totala kantvikten och utan cykler. Kruskal och Prim är två klassiska giriga algoritmer.
Sortera alla kanter efter vikt; lägg till den billigaste kanten som inte bildar en cykel.
def kruskal(n, edges): # edges: (weight, u, v)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
mst, total = [], 0
for w, u, v in sorted(edges): # cheapest first
ru, rv = find(u), find(v)
if ru != rv: # no cycle -> take it
parent[ru] = rv
mst.append((u, v, w)); total += w
return mst, total
Börja från valfritt hörn; upprepa genom att lägga till den billigaste kanten som lämnar det aktuella trädet.
| Kruskal | Prim | |
|---|---|---|
| Tillvägagångssätt | sortera kanter + union-find | växa från en nod + heap |
| Tid | O(E log E) | O(E log V) |
| Bäst för | glesa grafer | täta grafer |
Använd MST för nätverksdesign — att lägga kablar, vattenledningar, klustring. Båda är giriga och bevisligen optimala här. Kruskal behöver union-find för att effektivt undvika cykler.
MST minimerar kostnaden för att koppla ihop allt — direkt tillämpligt på infrastruktur och nätverkslayout.
Det är ett rent fall där girighet är bevisligt optimal, vilket förstärker greedy-choice-resonemang.
Kruskal visar också union-find, en struktur med bred algoritmisk räckvidd.
Ett bibliotek med IT-intervjufrågor och detaljerade svar — från Junior till Senior.
Donera