Un arbore minim de acoperire (MST) conectează toate vârfurile unui graf ponderat și conectat cu greutatea totală minimă a muchiilor și fără cicluri. Kruskal și Prim sunt cei doi algoritmi clasici lacomi.
Sortează toate muchiile după greutate; adaugă muchia cea mai ieftină care nu formează un ciclu.
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
Pornește de la orice vârf; adaugă în mod repetat muchia cea mai ieftină care iese din arborele curent.
| Kruskal | Prim | |
|---|---|---|
| Abordare | sortează muchii + union-find | dezvoltă de la un nod + heap |
| Timp | O(E log E) | O(E log V) |
| Cel mai bun pentru | grafuri rare | grafuri dense |
Foloseşte MST pentru proiectarea rețelelor — instalare cabluri, conducte de apă, clustering. Ambii sunt lacomi și demonstrabil optimi aici. Kruskal are nevoie de union-find pentru a evita ciclurile eficient.
MST minimizează costul conectării tuturor — direct aplicabil infrastructurii și amplasamentului rețelei.
Este un caz curat în care lacomia este demonstrabil optimă, întărind raționamentul alegerii lacomi.
Kruskal prezintă și union-find, o structură cu o încrengătură algoritmică largă.