- Atual
- Na árvore
- Junto à árvore
- Melhor aresta até agora
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
- Clique num nó para o tornar a origem: a árvore cresce a partir dele.
- 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.
- 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