Árvore geradora mínima: Kruskal e Prim lado a lado

Árvore geradora mínima

Uma árvore geradora de um grafo conexo é um subgrafo que liga todos os vértices usando exatamente n − 1 arestas e sem ciclos. A árvore geradora mínima é a de menor soma de pesos. Ela aparece sempre que se quer ligar tudo com o menor custo: cabos, estradas, redes.

Kruskal: ordenar as arestas

O Kruskal ordena todas as arestas pelo peso, do menor para o maior, e percorre a lista. Cada aresta é aceita se liga duas árvores diferentes, e rejeitada se fecharia um ciclo. Para saber isso rápido, usa-se a união-busca, que guarda a qual árvore cada vértice pertence.

Prim: crescer a partir de um vértice

O Prim começa em um vértice e, a cada passo, acrescenta a aresta mais barata que sai da árvore atual para um vértice ainda de fora. A fila de prioridade guarda as arestas candidatas. Se o grafo é desconexo, o Prim cobre só a componente da origem.

Lado a lado

As duas animações usam o mesmo grafo e as mesmas posições. Repare que o Kruskal salta entre partes distantes do grafo (ele segue o peso, não a vizinhança), enquanto o Prim cresce como uma mancha a partir da origem. Os dois chegam ao mesmo peso total: isso é um teorema, e o painel confere.

Propriedade do corte

Quando o grafo tem pesos distintos, a árvore mínima é única. Com pesos repetidos, pode haver mais de uma, mas todas têm o mesmo peso total.