Algoritmo de Kruskal
Ordene as arestas, escolha a mais curta, nunca feche um ciclo. O algoritmo de Kruskal é talvez o algoritmo ganancioso mais simples que existe, e mesmo assim encontra sempre a forma mais barata de ligar todos os nós de um grafo.
A ideia
Uma árvore de extensão mínima liga todos os nós de um grafo ponderado com o menor comprimento total de arestas possível. O algoritmo de Kruskal não faz crescer uma só árvore a partir de uma origem. Olha para o grafo inteiro de uma vez, começa com cada nó como uma parte sozinho e vai juntando partes com a aresta mais curta disponível até restar só uma.
Passo a passo
Ordene as arestas da mais curta para a mais longa. Experimente-as por essa ordem. Se as duas pontas de uma aresta estão em partes diferentes, junte-a à árvore: as duas partes passam a ser uma. Se as duas pontas já estão na mesma parte, a aresta fecharia um ciclo, por isso é ignorada. Com n nós, a árvore fica completa ao fim de n − 1 arestas, e as restantes arestas nunca precisam de ser vistas.
Um exemplo
Tome as arestas A–B de comprimento 1, B–C 2, A–C 3, C–D 4 e B–D 5. Kruskal junta A–B, depois B–C, que liga C à parte A–B. A seguir vem A–C, mas A e C já estão na mesma parte, por isso fecharia o ciclo A–B–C e é ignorada. C–D liga D, e agora os quatro nós formam uma árvore com três arestas, de comprimento total 7. B–D, a aresta mais longa, nem sequer é experimentada.
Union-find
A única pergunta difícil que o algoritmo de Kruskal faz é: estes dois nós já estão na mesma parte? Uma estrutura union-find responde-lhe. Cada parte é uma pequena árvore de ligações que apontam para um representante. Find segue as ligações até ao representante; union põe um representante por baixo do outro. A compressão de caminhos, que faz cada nó visitado apontar diretamente para o representante, e a união por tamanho mantêm as ligações tão curtas que cada pergunta demora um tempo quase constante.
História e velocidade
Joseph Kruskal publicou o algoritmo em 1956, num artigo curto nos Proceedings of the American Mathematical Society. Ordenar as arestas é a parte mais lenta, por isso o trabalho cresce com E log E para E arestas. Se as arestas já estiverem ordenadas, ou se os seus comprimentos forem números inteiros pequenos, é quase linear.
Experimente
Abra a aplicação e prima Avançar. As arestas ainda por experimentar aparecem por baixo do grafo, da mais curta para a mais longa. Cada aresta que liga duas partes fica verde; cada aresta que fecharia um ciclo é desenhada tracejada a vermelho. Veja várias partes pequenas crescer em zonas diferentes do grafo e juntar-se, e repare que as últimas arestas muitas vezes nunca são experimentadas.
Perguntas frequentes
Porque é que o algoritmo de Kruskal ordena as arestas?
Para que cada aresta que junta seja a mais curta que ainda liga duas partes. Essa escolha gananciosa é sempre segura por causa da propriedade do corte, e cada aresta ignorada é a mais longa do ciclo que fecharia, por isso nunca é necessária.
O que é uma estrutura de conjuntos disjuntos?
Outro nome para union-find: uma estrutura que guarda uma coleção de conjuntos separados, aqui as partes da floresta em crescimento, e sabe dizer depressa a que conjunto pertence um elemento e juntar dois conjuntos.
O algoritmo de Kruskal funciona num grafo não conexo?
Sim. Simplesmente termina com uma árvore para cada parte conexa do grafo, uma floresta de extensão mínima, porque nenhuma aresta pode ligar partes que não estão ligadas.
O algoritmo de Kruskal é usado para mais alguma coisa?
Pará-lo mais cedo, antes de as últimas partes se juntarem, agrupa os nós em clusters: é o clustering de ligação simples. Executá-lo numa grelha com comprimentos de aresta aleatórios gera um labirinto.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar o algoritmo de Kruskal