Exemplo — Executando o algoritmo de Prim a partir do vértice A
Agora vamos executar o algoritmo de Prim em um grafo ponderado. A regra é sempre a mesma: olhar para as arestas que saem da árvore atual e escolher a menor possível.
Vamos começar no vértice A. No início, a árvore contém apenas esse vértice.
Passo 1 — Começando em A
A árvore começa apenas com o vértice A.
As arestas que saem de A são: A–C = 1 e A–B = 2.
A menor é A–C = 1, então adicionamos essa aresta e o vértice C.
Passo 2 — Expandindo {A, C}
Agora a árvore contém A e C.
Observamos todas as arestas que saem da árvore: A–B = 2, C–E = 4, C–D = 6 e C–F = 8.
A menor é A–B = 2, então adicionamos o vértice B.
Passo 3 — Expandindo {A, B, C}
As arestas candidatas agora são: B–D = 3, C–E = 4, C–D = 6 e C–F = 8.
A menor é B–D = 3. Então adicionamos o vértice D.
Note que o algoritmo de Prim não ordena todas as arestas globalmente. Ele considera apenas a fronteira da árvore atual.
Passo 4 — Adicionando E
A árvore contém agora A, B, C, D. As arestas possíveis incluem: C–E = 4, D–F = 5, D–E = 9 e C–F = 8.
A menor é C–E = 4, então adicionamos o vértice E.
Passo 5 — Adicionando F
Resta apenas o vértice F.
As arestas disponíveis são: D–F = 5 e C–F = 8.
A menor é D–F = 5, então adicionamos essa aresta e finalizamos a árvore.
Resultado Final
A árvore geradora mínima encontrada é:
A–C = 1, A–B = 2, B–D = 3, C–E = 4, D–F = 5.
O peso total é: 1 + 2 + 3 + 4 + 5 = 15.
O resultado é uma árvore porque conecta todos os vértices com exatamente n − 1 arestas e sem ciclos.
Intuição Principal da Parte 2
O algoritmo de Prim sempre constrói uma única estrutura conectada.
A cada passo, ele olha apenas para a fronteira da árvore e escolhe a menor aresta disponível.
Por isso ele difere de Kruskal: Prim expande uma árvore, enquanto Kruskal une componentes.