A pergunta principal
O algoritmo de Prim toma uma decisão local a cada passo: ele escolhe a aresta de menor peso que conecta a árvore atual a um vértice fora dela.
Mas por que isso é seguro? Por que escolher a aresta mais barata agora ainda leva a uma árvore geradora mínima no final?
A resposta vem de uma das ideias mais importantes por trás dos algoritmos de árvore geradora mínima: a propriedade do corte.
O que é um corte?
Um corte divide os vértices do grafo em dois grupos.
No algoritmo de Prim, um lado do corte é o conjunto de vértices já dentro da árvore. O outro lado contém os vértices que ainda estão fora.
Qualquer aresta que conecta esses dois grupos é chamada de aresta de corte.
Intuição visual — a fronteira
Pense na árvore atual de Prim como uma ilha. As arestas de corte são pontes que ligam essa ilha ao resto do grafo.
Prim sempre escolhe a ponte mais barata para expandir a ilha.
A propriedade do corte
A propriedade do corte afirma que, ao dividir o grafo em dois grupos, a aresta de menor peso que cruza esse corte é segura para fazer parte de uma árvore geradora mínima.
O algoritmo de Prim utiliza essa propriedade em cada passo. A árvore atual define um lado do corte, e os vértices restantes definem o outro lado.
Portanto, ao escolher a menor aresta que cruza esse corte, Prim faz sempre uma escolha gulosa segura.
Por que não forma ciclo?
O algoritmo de Prim só adiciona arestas que conectam a árvore atual a um vértice que ainda não está nela.
Como esse vértice ainda não fazia parte da árvore, não existe caminho anterior ligando ele à árvore.
Portanto, adicionar essa aresta não pode formar ciclo.
Por que conecta todos os vértices?
A cada passo, o algoritmo adiciona exatamente um novo vértice à árvore.
Começando de um único vértice, Prim continua expandindo até não restar nenhum vértice fora.
Em um grafo conexo, sempre existirá uma aresta ligando a árvore ao restante do grafo até que todos sejam incluídos.
Por que o resultado é mínimo?
Em cada passo, Prim adiciona uma aresta segura, de acordo com a propriedade do corte.
Isso significa que cada aresta escolhida pode fazer parte de alguma árvore geradora mínima.
Repetindo essas escolhas seguras, o algoritmo constrói uma árvore final que é mínima.
Intuição principal da Parte 3
O algoritmo de Prim funciona porque cada escolha gulosa é garantida pela propriedade do corte.
Ele não escolhe qualquer aresta barata — escolhe a mais barata que cruza a fronteira da árvore.
Por isso, ele consegue crescer localmente e ainda garantir um resultado global ótimo.