Pergunta final — Por que aprender Kruskal se o Prim também encontra MST?
O Kruskal não é o único algoritmo que encontra uma árvore geradora mínima. Outro algoritmo clássico para o mesmo problema é o algoritmo de Prim.
Ambos produzem uma MST, mas constroem a solução de maneiras diferentes. Entender essa diferença é uma das ideias mais importantes em algoritmos gulosos em grafos.
O Kruskal pensa globalmente: ele olha para todas as arestas e escolhe repetidamente a mais barata que seja segura.
O Prim pensa localmente: ele começa em um vértice e expande a árvore usando sempre a aresta mais barata que sai dela.
Kruskal em uma frase
Kruskal ordena todas as arestas por peso e as adiciona uma a uma, desde que não formem ciclos.
Ele é especialmente natural quando o grafo é visto como uma lista de arestas ponderadas.
Prim em uma frase
O Prim começa em um vértice e expande a árvore escolhendo sempre a aresta mais barata que conecta a árvore a um novo vértice.
Em vez de ordenar todas as arestas, o Prim normalmente usa uma fila de prioridade para escolher a melhor aresta disponível.
Diferença conceitual chave
A diferença mais importante não é a estrutura de dados, mas o ponto de vista.
Kruskal vê o grafo como um conjunto de arestas e tenta montar uma árvore a partir das mais baratas.
Prim vê a MST como uma árvore que cresce a partir de um vértice inicial.
Comparação lado a lado
• Ordena todas as arestas
• Adiciona a aresta segura mais barata
• Usa Union-Find para evitar ciclos
• Natural para listas de arestas
• Começa em um vértice
• Adiciona a aresta mais barata da fronteira
• Usa fila de prioridade
• Natural para listas de adjacência
Quando cada um é mais natural?
Kruskal costuma ser mais simples quando o grafo já está representado como uma lista de arestas.
Prim é mais natural quando usamos listas de adjacência e queremos crescer a solução a partir de um ponto inicial.
Na prática, a escolha depende bastante da forma como o grafo está representado.
O que lembrar para provas ou entrevistas?
• Encontra uma árvore geradora mínima
• É um algoritmo guloso
• Ordena arestas por peso
• Rejeita arestas que formam ciclo
• Usa Union-Find para detectar ciclos
Se pedirem comparação com Prim, explique: ambos resolvem MST, mas um conecta componentes e o outro expande uma árvore.
Complexidade
Ambos são eficientes e dependem da implementação.
Intuição final da série
O Kruskal funciona porque uma MST não precisa de escolhas “inteligentes” complexas — precisa de arestas baratas que mantenham a estrutura válida.
Ele aplica uma regra simples repetidamente: escolher a aresta mais barata que não quebra a estrutura.
Conclusão da série
1. O que é MST
2. Como Kruskal funciona
3. Como Union-Find detecta ciclos
4. Comparação com Prim
Agora você tem tanto a intuição quanto a lógica por trás de um dos algoritmos mais importantes da teoria dos grafos.