Problema — Expandindo uma Rede com Custo Mínimo
Suponha que queremos conectar várias cidades usando cabos, estradas ou tubulações. Cada conexão possível tem um custo, e o objetivo é conectar todas as cidades gastando o mínimo possível.
Em teoria dos grafos, isso se torna um problema de encontrar uma árvore geradora mínima: um conjunto de arestas que conecta todos os vértices, não possui ciclos e tem o menor peso total possível.
O que é o algoritmo de Prim?
O algoritmo de Prim é um método guloso para encontrar uma árvore geradora mínima em um grafo ponderado. Em vez de ordenar todas as arestas globalmente, ele começa em um vértice e expande uma única árvore.
Em cada passo, o algoritmo observa todas as arestas que saem da árvore atual e seleciona aquela com o menor peso. A aresta escolhida deve conectar a árvore a um novo vértice fora da árvore.
Esse processo continua até que todos os vértices estejam conectados. Se o grafo tem n vértices, a árvore geradora final terá exatamente n − 1 arestas.
A intuição central é simples: sempre expandir a árvore atual usando a aresta mais barata possível.
Como ele mantém uma única estrutura conectada crescendo desde o início, Prim costuma ser um dos algoritmos mais intuitivos para árvores geradoras mínimas.
Por que essa ideia é importante?
Árvores geradoras mínimas são úteis sempre que queremos construir uma estrutura conectada com custo mínimo: redes de comunicação, sistemas viários, redes elétricas, planejamento de transporte e projetos de infraestrutura.
O algoritmo de Prim também é importante do ponto de vista pedagógico porque mostra como uma escolha local baseada na fronteira atual pode produzir uma árvore globalmente ótima.
Na prática, Prim é especialmente natural quando pensamos em uma rede como algo que cresce para fora a partir de um ponto inicial escolhido.
Intuição principal da Parte 1
O objetivo não é apenas conectar o grafo — é conectá-lo com o menor custo possível.
Prim faz isso perguntando repetidamente: qual é a menor aresta que pode expandir minha árvore atual agora?
Diferente de Kruskal, que examina as arestas em ordem global, Prim sempre trabalha a partir da fronteira da árvore já construída.
Na próxima parte, estudaremos o algoritmo passo a passo, começando de um vértice inicial e acompanhando cada aresta aceita.