Un albero di copertura minimo (MST) collega tutti i vertici di un grafo ponderato e connesso con il peso totale dei lati minimo e senza cicli. Kruskal e Prim sono i due algoritmi greedy classici.
Ordina tutti i lati per peso; aggiungi il lato più economico che non forma un ciclo.
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
Inizia da un qualsiasi vertice; aggiungi ripetutamente il lato più economico che esce dall'albero corrente.
| Kruskal | Prim | |
|---|---|---|
| Approccio | ordina lati + union-find | cresci da un nodo + heap |
| Tempo | O(E log E) | O(E log V) |
| Migliore per | grafi sparsi | grafi densi |
Usa MST per il progetto di reti — posa di cavi, tubi dell'acqua, clustering. Entrambi sono greedy e provabilmente ottimali qui. Kruskal necessita union-find per evitare cicli in modo efficiente.
MST minimizza il costo di collegare tutto — direttamente applicabile alle infrastrutture e al layout di rete.
È un caso pulito dove greedy è provabilmente ottimale, rafforzando il ragionamento della scelta greedy.
Kruskal inoltre mostra union-find, una struttura con ampia portata algoritmica.