- Atual
- Na árvore
- Fecharia um ciclo
Algoritmo de Kruskal
O algoritmo de Kruskal constrói uma árvore de extensão mínima, o conjunto de arestas mais barato que liga todos os nós, da forma mais simples que se possa imaginar: pega nas arestas da mais curta para a mais longa e fica com cada uma, a não ser que feche um ciclo. Avance passo a passo para ver partes separadas crescer e juntar-se numa só árvore, e as arestas que são ignoradas. 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. O número em cada aresta é o seu comprimento. Por baixo do grafo estão as arestas ainda por experimentar, da mais curta para a mais longa; uma aresta cujas pontas já estão ligadas fecharia um ciclo e é desenhada tracejada a vermelho. 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
- 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. As arestas ainda por experimentar aparecem por baixo do grafo, da mais curta para a mais longa.
- Repare nas arestas tracejadas a vermelho: fechariam um ciclo. Novo grafo cria outro grafo para experimentar.
Como funciona o algoritmo de Kruskal
Ordene todas as arestas da mais curta para a mais longa. No início, cada nó é uma parte sozinho. Experimente as arestas por ordem: se uma aresta liga duas partes diferentes, entra na árvore e as duas partes passam a ser uma; se as suas duas pontas já estão na mesma parte, fecharia um ciclo, por isso é ignorada. Termina quando tudo é uma só parte, o que acontece ao fim de uma aresta a menos do que o número de nós, muitas vezes muito antes de a última aresta ser experimentada.
Union-find
Para cada aresta, o algoritmo de Kruskal tem de perguntar se as suas duas pontas já estão ligadas. Uma estrutura union-find responde depressa: cada parte tem um nó representante, find segue as ligações até ele, e union liga um representante ao outro. Com dois truques simples, a compressão de caminhos e a união por tamanho, cada pergunta demora um tempo quase constante, por isso ordenar as arestas é a parte mais lenta, com um trabalho que cresce com E log E.
Perguntas frequentes
O que é o algoritmo de Kruskal?
Um algoritmo ganancioso que constrói uma árvore de extensão mínima ordenando todas as arestas da mais curta para a mais longa e juntando cada aresta que não fecha um ciclo com as arestas já escolhidas.
Como é que o algoritmo de Kruskal deteta um ciclo?
Uma aresta fecha um ciclo exatamente quando as suas duas pontas já estão ligadas por arestas escolhidas. Uma estrutura union-find regista que nós estão ligados e responde a essa pergunta quase instantaneamente.
Porque é que o algoritmo de Kruskal funciona?
Por causa da propriedade do ciclo: a aresta mais longa de qualquer ciclo nunca é necessária para uma árvore de extensão mínima. Cada aresta que Kruskal ignora é a mais longa do ciclo que fecharia, porque todas as arestas antes dela eram mais curtas ou iguais.
Quando devo usar Kruskal em vez de Prim?
O algoritmo de Kruskal é simples e rápido em grafos esparsos, e trabalha diretamente sobre uma simples lista de arestas. O algoritmo de Prim adequa-se a grafos densos e a grafos guardados como listas de adjacência. Ambos encontram uma árvore com o mesmo comprimento total.
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