Arestas da árvore
Comprimento total
Arestas verificadas

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

Mais sobre árvores de extensão mínima

Árvore de extensão mínima

Quer ligar cada localidade por cabo, cada casa por canos de água ou cada computador de uma rede, gastando o mínimo de material possível. A resposta é uma árvore de extensão mínima: o conjunto de arestas que liga todos os nós com o menor comprimento total. Escolha o algoritmo de Kruskal ou de Prim e avance passo a passo para ver a árvore crescer, juntando de cada vez a aresta permitida mais curta. 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. Escolha o algoritmo: Kruskal experimenta as arestas da mais curta para a mais longa, Prim faz crescer uma só árvore a partir da origem; clique num nó para o tornar a origem de Prim. O número em cada aresta é o seu comprimento. Por baixo do grafo está a lista das arestas ainda por experimentar, ou os nós em espera com o comprimento da sua melhor aresta até à árvore. 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. Escolha o algoritmo de Kruskal ou de Prim. Para Prim, clique num nó para o tornar a origem.
  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 as arestas a entrar na árvore e o comprimento total a crescer. Novo grafo cria outro grafo para experimentar.

Algoritmo de Kruskal

Ordene todas as arestas da mais curta para a mais longa e experimente-as por essa ordem. Se uma aresta liga duas partes ainda não ligadas, entra na árvore. Se as suas duas pontas já estão ligadas através da árvore, fecharia um ciclo, por isso é ignorada. Termina quando a árvore tem uma aresta a menos do que o número de nós. Para saber depressa se dois nós já estão ligados, o algoritmo de Kruskal guarda as partes numa estrutura union-find.

Algoritmo de Prim

Comece com uma árvore de um só nó. Cada nó fora da árvore guarda a sua aresta mais curta até à árvore. Junte repetidamente o nó cuja aresta é a mais curta, com essa aresta, e verifique as suas arestas: uma delas pode dar a um vizinho um caminho mais curto até à árvore. O algoritmo de Prim parece-se com o algoritmo de Dijkstra, mas compara arestas isoladas, não distâncias inteiras desde a origem. Os dois algoritmos terminam sempre com o mesmo comprimento total.

Perguntas frequentes

O que é uma árvore de extensão mínima?

Num grafo conexo cujas arestas têm comprimentos, uma árvore de extensão é um conjunto de arestas que liga todos os nós sem nenhum ciclo; com n nós tem sempre n − 1 arestas. Uma árvore de extensão mínima é uma árvore de extensão cujo comprimento total é o menor possível.

Qual é a diferença entre o algoritmo de Kruskal e o de Prim?

O algoritmo de Kruskal percorre as arestas de todo o grafo da mais curta para a mais longa e junta partes separadas numa só árvore. O algoritmo de Prim faz crescer uma só árvore a partir de uma origem, juntando sempre a aresta mais curta que sai dela. Ambos são gananciosos e encontram uma árvore com o mesmo comprimento total; Kruskal adequa-se a grafos esparsos, Prim a grafos densos.

A árvore de extensão mínima é única?

Quando todos os comprimentos das arestas são diferentes, sim. Quando alguns são iguais, pode haver várias árvores com o mesmo total mínimo, e os algoritmos podem escolher árvores diferentes conforme a forma como desempatam.

Uma árvore de extensão mínima é o mesmo que caminhos mais curtos?

Não. A árvore de extensão mínima mantém pequeno o comprimento total de todas as arestas, mas o caminho entre dois nós na árvore pode ser muito mais longo do que o seu caminho mais curto. Para caminhos mais curtos, use o algoritmo de Dijkstra.

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