Uma árvore geradora mínima (MST) conecta todos os vértices de um grafo ponderado e conexo com o peso total de arestas mínimo e sem ciclos. Kruskal e Prim são os dois algoritmos gulosos clássicos.
Ordene todas as arestas por peso; adicione a aresta mais barata que não forme um 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
Comece em qualquer vértice; adicione repetidamente a aresta mais barata que sai da árvore atual.
| Kruskal | Prim | |
|---|---|---|
| Abordagem | ordene arestas + union-find | desenvolva a partir de um nó + heap |
| Tempo | O(E log E) | O(E log V) |
| Melhor para | grafos esparsos | grafos densos |
Use MST para design de rede — instalação de cabos, tubulações de água, clustering. Ambos são gulosos e comprovadamente ótimos aqui. Kruskal precisa de union-find para evitar ciclos eficientemente.
MST minimiza o custo de conectar tudo — aplicável diretamente à infraestrutura e layout de rede.
É um caso limpo em que guloso é comprovadamente ótimo, reforçando o raciocínio de escolha gulosa.
Kruskal também apresenta union-find, uma estrutura com amplo alcance algorítmico.