Arestas da árvore
Comprimento total
Arestas verificadas

  • Atual
  • Na árvore
  • Junto à árvore
  • Melhor aresta até agora

Mais sobre o algoritmo de Prim

Algoritmo de Prim

O algoritmo de Prim constrói uma árvore de extensão mínima, o conjunto de arestas mais barato que liga todos os nós, fazendo crescer uma só árvore a partir de uma origem. Em cada passo junta o nó que se alcança a partir da árvore pela aresta mais curta. Clique num nó para começar aí e avance passo a passo para ver os nós em espera, as suas melhores arestas e a árvore a crescer. Prima Reproduzir para ver a árvore crescer, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Clique num nó para o tornar a origem: a árvore cresce a partir dele. O número em cada aresta é o seu comprimento. Por baixo do grafo estão os nós em espera, cada um com o comprimento da sua melhor aresta até à árvore, que é desenhada tracejada. Novo grafo cria outro grafo; escolha quantos nós e arestas tem. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Clique num nó para o tornar a origem: a árvore cresce a partir dele.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto.
  3. Observe os nós em espera por baixo do grafo, cada um com a sua melhor aresta até à árvore. Novo grafo cria outro grafo para experimentar.

Como funciona o algoritmo de Prim

Comece com uma árvore de um só nó. Cada nó fora da árvore guarda a sua aresta mais curta até à árvore, se tiver uma. Escolha repetidamente o nó cuja aresta é a mais curta, junte-o à árvore com essa aresta e verifique as suas arestas: se uma for mais curta do que a melhor aresta de um vizinho até agora, passa a ser a melhor aresta desse vizinho. Quando todos os nós tiverem entrado, a árvore tem uma aresta a menos do que o número de nós, e o seu comprimento total é o menor possível.

Prim e Dijkstra

O algoritmo de Prim e o algoritmo de Dijkstra são quase iguais: ambos fazem crescer uma região a partir de uma origem e guardam os nós em espera numa fila de prioridade. A diferença é o número na fila. Dijkstra guarda a distância completa de cada nó desde a origem; Prim guarda só o comprimento da sua melhor aresta até à árvore. Assim, Dijkstra constrói uma árvore de caminhos mais curtos, e Prim uma árvore de comprimento total mínimo, e as duas árvores são muitas vezes diferentes.

Perguntas frequentes

O que é o algoritmo de Prim?

Um algoritmo ganancioso que constrói uma árvore de extensão mínima de um grafo ponderado fazendo crescer uma só árvore a partir de um nó de origem, juntando sempre a aresta mais curta que liga a árvore a um nó de fora.

O nó de origem importa?

Só para a ordem: a partir de qualquer origem, o algoritmo de Prim termina com uma árvore de extensão com o mesmo comprimento total mínimo. Quando algumas arestas têm o mesmo comprimento, a própria árvore pode ser diferente.

Quem inventou o algoritmo de Prim?

Vojtěch Jarník descreveu-o primeiro, em 1930. Robert Prim redescobriu-o em 1957 e Edsger Dijkstra em 1959, por isso também se chama algoritmo de Jarník ou algoritmo de Prim–Jarník.

Quão rápido é o algoritmo de Prim?

Com um heap binário, o trabalho cresce com E log V para V nós e E arestas. Com um simples array em vez de um heap demora cerca de V² passos, o que é melhor para grafos densos, onde quase todos os pares de nós estão ligados.

O meu grafo é enviado para algum lado?

Não. O grafo é criado e a árvore é construída no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor