Como executar Prim ou Kruskal 01 Construa um grafo ponderado. Experimente a predefinição Grade (rows 4, cols 5 — 20 nós, 31 arestas unitárias), um grafo Random conectado ou o Complete K₆. 02 Escolha Prim e defina a Source , ou mude para Kruskal, que não precisa de fonte. 03 Leia a tabela. Primeiro o peso total, depois arestas escolhidas, componentes e é-floresta; abaixo fica uma linha por aresta escolhida com seu peso. 04 Confira com o outro algoritmo — os dois devem concordar no peso total para o mesmo grafo. 05 Avance a execução com Play / Prev / Next; o Prim destaca a fronteira crescente, o Kruskal as arestas aceitas e rejeitadas.
Exemplos resolvidos Valores como exibidos pelo painel:
Grafo · algoritmo
Leitura
Grade 4 × 5, Prim de 1-1
peso total 19 ; arestas escolhidas 19 / 31 ; componentes 1 ; é floresta No
Grade 4 × 5, Kruskal
peso total 19 ; arestas escolhidas 19 / 31
Random conectado (n 6, p 0.3, seed 20260730, peso máx. 9), Prim de A
peso total 16 ; escolhidas A–B(3), A–C(4), C–E(2), A–D(6), D–F(1) ; arestas escolhidas 5 / 7
O mesmo grafo, Kruskal
peso total 16 ; as mesmas cinco arestas em ordem de peso: D–F(1), C–E(2), A–B(3), A–C(4), A–D(6)
Complete K₆, Prim
peso total 5 ; arestas escolhidas 5 / 15 ; arestas A–B(1), A–F(1), A–E(1), A–D(1), A–C(1)
A MST da grade são 19 arestas unitárias para 20 nós — o mínimo teórico — e os dois algoritmos a alcançam. No grafo aleatório, uma aresta basta para conferir a resposta à mão: D–F pesa 1 , a mais leve do grafo, então toda MST deve contê-la, e as duas execuções contêm.
Por que as duas listas diferem Prim e Kruskal escolhem arestas em ordens diferentes e, em empates, podem escolher árvores válidas diferentes. O Kruskal ordena todas as arestas globalmente, então sua tabela começa pela aresta mais leve em qualquer lugar; o Prim olha apenas a fronteira de uma árvore em crescimento, então sua tabela começa pelo que sai primeiro da raiz. No grafo aleatório, os dois produzem o mesmo conjunto — a árvore geradora mínima ali é única —, mas a lista do K₆ (todos os pesos 1) é apenas uma entre muitas árvores perfeitas: compare peso total e número de arestas, não listas de arestas, quando os pesos se repetem.
Limites
Um grafo desconectado dá uma floresta. A linha é-floresta vira Sim e o número de componentes fica acima de 1; a resposta é então uma floresta geradora mínima, uma árvore por componente, não uma única árvore.
Somente arestas não direcionadas. O Prim trata um grafo direcionado como não direcionado e avisa; a fusão de componentes do Kruskal também é uma ideia não direcionada. Nenhum dos dois resolve a arborescência mínima direcionada.
A armadilha do desempate No Complete K₆ cada aresta pesa 1 , então toda árvore geradora pesa 5 ; o Prim responde por acaso com uma estrela em torno de A: A–B, A–F, A–E, A–D, A–C . Leia essa lista como uma árvore mínima, não como a árvore mínima. A mesma cautela vale para grades de pesos iguais: a resposta da grade 19 é estável, mas quais 19 arestas unitárias aparecem pode diferir entre Prim e Kruskal enquanto ambos continuam corretos.
Onde é útil Conferir uma alegação de fiação mais barata No grafo aleatório, as duas arestas mais pesadas, E–F(8) e B–D(7) , ficam ambas excluídas enquanto A–D(6) é aceita. Confira uma rede proposta do mesmo jeito: se ela paga E–F(8) e deixa de fora a mais barata D–F(1), não é mínima.
Ensinar a propriedade do corte A grade torna o raciocínio de corte visível: cada aresta unitária cruza algum corte com peso 1, e os dois algoritmos aceitam 19 das 31 sem um único ciclo. Mude para o grafo Random conectado e rode os dois; a reprodução passo a passo mostra o Kruskal pulando E–F(8) porque suas pontas já estão unidas.
Privacidade A edição do grafo e as duas execuções de MST rodam localmente no seu navegador; nada é enviado.
Referências
Wikipédia, Prim's algorithm , en.wikipedia.org (访问日期:2026-10-07)— crescimento da fronteira a partir de uma raiz.
Wikipédia, Kruskal's algorithm , en.wikipedia.org (访问日期:2026-10-07)— ordem por peso com union-find.
Wikipédia, Minimum spanning tree , en.wikipedia.org (访问日期:2026-10-07)— propriedades de corte e ciclo, unicidade com pesos distintos.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4.ª ed., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— algoritmos de MST e a propriedade do corte.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07