Algoritmo de Prim
Última atualização
O algoritmo de Prim constrói uma árvore geradora mínima (MST) - o conjunto de arestas mais barato que conecta todos os nós sem ciclos - fazendo crescer uma única árvore para fora a partir de um nó inicial. A cada passo ele observa todas as arestas que cruzam da árvore para um nó fora dela e adiciona a mais barata. Pressione reproduzir acima para ver a árvore se expandir, sempre pegando a aresta de menor peso que alcança um novo nó.
Como sempre escolhe a aresta de cruzamento mínima, cada adição é segura (garantida como parte de alguma MST). Com uma fila de prioridade baseada em heap binário indexada pela aresta mais barata até cada nó externo, Prim é executado em O(E log V). Contrasta com Kruskal, que ordena todas as arestas globalmente em vez de fazer crescer uma única árvore conexa.
Complexidade de tempo e espaço
| Implementação | Complexidade | Notas |
|---|---|---|
| Heap binário | O(E log V) | Fila de prioridade de arestas de cruzamento |
| Matriz de adjacência | O(V²) | Mais simples; boa para grafos densos |
| Espaço | O(V + E) | Pertencimento à árvore + fila de prioridade |
| Melhor para | Grafos densos | Cresce a partir de um único nó inicial |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Inicie a árvore com qualquer nó único. |
| 2 | Observe todas as arestas que cruzam da árvore para um nó fora dela. |
| 3 | Escolha a aresta de cruzamento com o menor peso. |
| 4 | Adicione essa aresta e seu novo nó à árvore. |
| 5 | Repita até que todos os nós estejam na árvore. |
Exemplo resolvido
Construindo a MST de um grafo de 4 nós com arestas A-B=1, A-C=3, B-C=2, B-D=4, C-D=5, começando de A:
| Passo | Árvore | Arestas de cruzamento | Aresta escolhida |
|---|---|---|---|
| 1 | {A} | A-B=1, A-C=3 | A-B (peso 1) |
| 2 | {A, B} | A-C=3, B-C=2, B-D=4 | B-C (peso 2) |
| 3 | {A, B, C} | B-D=4, C-D=5 | B-D (peso 4) |
| 4 | {A, B, C, D} | nenhuma - todos os nós na árvore | concluído: peso da MST 1+2+4 = 7 |
Quando usar o algoritmo de Prim
| Use quando | Evite quando |
|---|---|
| Você precisa de uma árvore geradora mínima de um grafo conexo, não direcionado e ponderado. | O grafo é direcionado ou você precisa de caminhos mais curtos - use Dijkstra ou Bellman-Ford. |
O grafo é denso (E próximo de V²); a forma matricial O(V²) é simples e rápida. | O grafo é esparso e as arestas já estão ordenadas ou são fáceis de ordenar - Kruskal costuma ser mais simples. |
| Você quer que a árvore cresça de uma região para fora (por exemplo, layout incremental de rede). | O grafo está desconectado - Prim abrange apenas um componente; você precisa de uma floresta geradora mínima. |
| Você já tem uma estrutura de adjacência e uma fila de prioridade disponíveis. | Você precisa detectar ciclos em um conjunto global de arestas - union-find (Kruskal) se encaixa melhor. |
Código de Prim's Algorithm
Uma implementação limpa e executável de Prim's Algorithm em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Prim's Algorithm em Python
Python
1import heapq2
3
4def prim(graph, start):5 visited = {start}6 heap = [(w, start, v) for v, w in graph[start]]7 heapq.heapify(heap)8 mst, total = [], 09 while heap and len(visited) < len(graph):10 w, u, v = heapq.heappop(heap)11 if v in visited:12 continue13 visited.add(v)14 mst.append((u, v, w))15 total += w16 # Offer the new node's edges to the frontier17 for neighbor, weight in graph[v]:18 if neighbor not in visited:19 heapq.heappush(heap, (weight, v, neighbor))20 return mst, total21
22
23graph = {24 "A": [("B", 4), ("C", 1)],25 "B": [("A", 4), ("C", 3), ("D", 2)],26 "C": [("A", 1), ("B", 3), ("D", 5)],27 "D": [("B", 2), ("C", 5), ("E", 7)],28 "E": [("D", 7)],29}30
31mst, total = prim(graph, "A")32for u, v, w in mst:33 print(f"{u} - {v} (weight {w})")34print("Total MST weight:", total)Código de Prim's Algorithm em JavaScript
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { A: 4, C: 1, D: 5 },4 C: { A: 2, B: 1, D: 8, E: 10 },5 D: { B: 5, C: 8, E: 2 },6 E: { C: 10, D: 2 },7};8
9function prim(start) {10 const inTree = new Set([start]);11 const mst = [];12 let total = 0;13 while (inTree.size < Object.keys(graph).length) {14 // JS has no built-in heap: scan all crossing edges for the cheapest15 let best = null;16 for (const u of inTree) {17 for (const [v, w] of Object.entries(graph[u])) {18 if (!inTree.has(v) && (best === null || w < best[2])) {19 best = [u, v, w];20 }21 }22 }23 const [u, v, w] = best;24 inTree.add(v);25 mst.push(`${u}-${v} (${w})`);26 total += w;27 }28 return { mst, total };29}30
31const { mst, total } = prim("A");32console.log("MST edges:", mst.join(", "));33console.log("Total weight:", total);Código de Prim's Algorithm em Java
Java
1import java.util.ArrayList;2import java.util.List;3import java.util.PriorityQueue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 List<List<int[]>> adj = new ArrayList<>();9 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10 int[][] edges = {11 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},12 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}13 };14 for (int[] e : edges) {15 adj.get(e[0]).add(new int[]{e[1], e[2]});16 adj.get(e[1]).add(new int[]{e[0], e[2]});17 }18
19 boolean[] inMst = new boolean[n];20 // Always grow the tree along the cheapest crossing edge21 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);22 pq.add(new int[]{0, 0}); // {node, edge weight}23 int total = 0, taken = 0;24 while (!pq.isEmpty() && taken < n) {25 int[] cur = pq.poll();26 if (inMst[cur[0]]) continue;27 inMst[cur[0]] = true;28 total += cur[1];29 taken++;30 for (int[] edge : adj.get(cur[0])) {31 if (!inMst[edge[0]]) pq.add(edge);32 }33 }34 System.out.println("MST nodes reached: " + taken);35 System.out.println("MST total weight: " + total);36 }37}Código de Prim's Algorithm em C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Undirected weighted graph: adj[u] = {(neighbor, weight), ...}7 std::vector<std::vector<std::pair<int, int>>> adj = {8 {{1, 2}, {3, 6}}, // 09 {{0, 2}, {2, 3}, {3, 8}, {4, 5}}, // 110 {{1, 3}, {4, 7}}, // 211 {{0, 6}, {1, 8}}, // 312 {{1, 5}, {2, 7}}, // 413 };14 int n = static_cast<int>(adj.size());15 std::vector<bool> inMST(n, false);16 using State = std::pair<int, int>; // (edge weight, node)17 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;18 pq.push({0, 0});19 int total = 0, picked = 0;20 // Always grow the tree along the cheapest crossing edge21 while (!pq.empty() && picked < n) {22 auto [w, u] = pq.top();23 pq.pop();24 if (inMST[u]) continue;25 inMST[u] = true;26 total += w;27 ++picked;28 std::cout << "Add node " << u << " (edge weight " << w << ")\n";29 for (auto [v, weight] : adj[u]) {30 if (!inMST[v]) pq.push({weight, v});31 }32 }33 std::cout << "MST total weight: " << total << "\n";34 return 0;35}Código de Prim's Algorithm em C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Undirected weighted graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 2, 0, 6, 0},11 {2, 0, 3, 8, 5},12 {0, 3, 0, 0, 7},13 {6, 8, 0, 0, 0},14 {0, 5, 7, 0, 0},15 };16 int key[N], parent[N];17 bool inMST[N] = {false};18 for (int v = 0; v < N; v++) {19 key[v] = INF;20 parent[v] = -1;21 }22 key[0] = 0;23 int total = 0;24 // O(V^2) scan for the cheapest crossing edge (no heap needed here)25 for (int iter = 0; iter < N; iter++) {26 int u = -1;27 for (int v = 0; v < N; v++) {28 if (!inMST[v] && (u == -1 || key[v] < key[u])) u = v;29 }30 inMST[u] = true;31 total += key[u];32 if (parent[u] != -1) {33 printf("Add edge %d - %d (weight %d)\n", parent[u], u, key[u]);34 }35 for (int v = 0; v < N; v++) {36 if (w[u][v] > 0 && !inMST[v] && w[u][v] < key[v]) {37 key[v] = w[u][v];38 parent[v] = u;39 }40 }41 }42 printf("MST total weight: %d\n", total);43 return 0;44}Perguntas frequentes sobre o algoritmo de Prim
Qual é a complexidade de tempo do algoritmo de Prim?
Com uma fila de prioridade baseada em heap binário, Prim é executado em
O(E log V). Uma versão mais simples com matriz de adjacência que busca a aresta de cruzamento mínima a cada passo é O(V²), que pode ser mais rápida em grafos densos. Ambas usam espaço O(V + E).Qual é a diferença entre os algoritmos de Prim e Kruskal?
Ambos encontram uma árvore geradora mínima de forma gulosa. Prim faz crescer uma única árvore conexa a partir de um nó inicial, adicionando repetidamente a aresta mais barata que sai da árvore (usando uma fila de prioridade). Kruskal considera todas as arestas ordenadas por peso e adiciona a mais barata que não forma ciclo (usando union-find). Prim costuma ser preferido em grafos densos, Kruskal em esparsos.
O algoritmo de Prim sempre encontra a MST ótima?
Sim. A cada passo, a aresta mais barata que cruza a árvore atual é segura para adicionar - ela pertence a alguma árvore geradora mínima (a propriedade do corte). Adicionar repetidamente arestas seguras produz uma verdadeira árvore geradora mínima, desde que o grafo seja conexo.
Quando devo usar o algoritmo de Prim em vez do de Kruskal?
Recorra ao Prim quando o grafo é denso, porque sua forma matricial
O(V²) evita ordenar todas as E arestas e faz crescer uma única árvore a partir de um nó inicial. Kruskal se destaca em grafos esparsos onde ordenar a lista de arestas é barato e union-find mantém as verificações de ciclo rápidas. Ambos produzem uma MST correta, então a escolha depende principalmente da densidade de arestas e de quais estruturas de dados você já tem.O nó inicial afeta a MST resultante?
Não - o peso total da MST é o mesmo independentemente de qual nó você começa, porque o peso da árvore geradora mínima de um grafo conexo é único. As arestas específicas só podem diferir quando várias arestas compartilham o mesmo peso e existem múltiplas MSTs. Caso contrário, Prim alcança exatamente a mesma árvore independentemente do nó inicial.
O algoritmo de Prim consegue lidar com grafos desconectados?
Não diretamente. Prim faz crescer uma única árvore, então abrange apenas o componente conexo que contém o nó inicial e deixa o resto intocado. Para cobrir cada componente, você executaria Prim repetidamente a partir de um nó não visitado, produzindo uma floresta geradora mínima em vez de uma única árvore.
Recursos relacionados
Mais visualizações
