Árvores de extensão mínima
Em 1926, pediram a Otakar Borůvka que planeasse a rede elétrica do sul da Morávia da forma mais barata possível. A sua pergunta, como ligar todos os lugares com o menor comprimento total de linha, é o problema da árvore de extensão mínima, e tem algumas das respostas mais simples e elegantes de toda a informática.
O problema
Pegue num grafo conexo cujas arestas têm comprimentos, ou custos. Uma árvore de extensão é um conjunto de arestas que liga todos os nós e não contém nenhum ciclo; com n nós tem sempre exatamente n − 1 arestas, porque cada aresta liga mais um nó. De todas as árvores de extensão, uma árvore de extensão mínima tem o menor comprimento total. Um grafo pode ter um número enorme de árvores de extensão, mas não é preciso experimentá-las todas.
Porque é que a estratégia gananciosa funciona
Divida os nós em dois grupos como quiser. A aresta mais curta que passa de um grupo para o outro pertence sempre a alguma árvore de extensão mínima: se uma árvore usasse em vez dela uma aresta mais longa entre os grupos, trocá-la pela mais curta ligaria os mesmos nós por menos. É a propriedade do corte. O reverso da medalha é a propriedade do ciclo: a aresta mais longa de qualquer ciclo nunca é necessária. Os dois algoritmos abaixo limitam-se a aplicar estas regras vezes sem conta.
Um exemplo
Pegue nas arestas A–B de comprimento 1, B–C 2, A–C 3, C–D 4 e B–D 5. O algoritmo de Kruskal escolhe A–B, depois B–C, depois ignora A–C, porque A e C já estão ligados e fecharia um ciclo, e depois escolhe C–D. A árvore tem três arestas para quatro nós, por isso está pronta, com comprimento total 7, e B–D nem sequer é vista. O algoritmo de Prim a partir de A junta primeiro B por A–B; a aresta B–C (2) de B ganha a A–C (3) como caminho até C, por isso C entra por B–C; a aresta C–D (4) de C ganha a B–D (5), por isso D entra por C–D. A mesma árvore, o mesmo 7.
Kruskal, Prim e Borůvka
O algoritmo de Kruskal, publicado por Joseph Kruskal em 1956, ordena as arestas e usa uma estrutura union-find para ignorar arestas dentro de uma mesma parte, por isso o seu trabalho cresce com E log E. O algoritmo de Prim foi descrito primeiro por Vojtěch Jarník em 1930 e redescoberto por Robert Prim em 1957 e por Edsger Dijkstra em 1959; com um heap binário o seu trabalho cresce com E log V, e com um simples array com V², o que é bom para grafos densos. O algoritmo de Borůvka, de 1926, deixa cada parte escolher ao mesmo tempo a sua aresta de saída mais curta, o que se adequa a computadores paralelos.
Aplicações
As árvores de extensão mínima servem para projetar redes baratas de cabos, canos e estradas. Agrupam dados em clusters: retire as arestas mais longas da árvore e as partes que ficam são os clusters. Dão depressa um percurso para o problema do caixeiro-viajante que é no máximo duas vezes mais longo do que o melhor quando as distâncias respeitam a desigualdade triangular. E o algoritmo de Kruskal ou de Prim numa grelha com comprimentos de aresta aleatórios é uma forma clássica de gerar um labirinto.
Experimente
Abra a aplicação, escolha Kruskal ou Prim e prima Avançar. Com Kruskal, as arestas ainda por experimentar aparecem por baixo do grafo, da mais curta para a mais longa; as arestas que fechariam um ciclo são desenhadas tracejadas a vermelho. Com Prim, aparecem os nós em espera com o comprimento da sua melhor aresta, que é desenhada tracejada. Execute os dois no mesmo grafo e compare: a ordem é diferente, mas o comprimento total é sempre o mesmo.
Perguntas frequentes
Quantas arestas tem uma árvore de extensão?
Exatamente uma a menos do que o número de nós. Com menos arestas não seria possível ligar todos os nós, e uma a mais criaria sempre um ciclo.
Qual é mais rápido, Kruskal ou Prim?
O algoritmo de Kruskal, que ordena as arestas, é normalmente mais simples e rápido em grafos esparsos, com poucas arestas. O algoritmo de Prim com um heap sai-se bem em grafos densos, e com um simples array precisa de cerca de V² passos, seja qual for o número de arestas.
O que é union-find?
Uma estrutura de dados que regista que nós estão na mesma parte. Responde a «estes dois estão ligados?» e junta duas partes quase instantaneamente, exatamente aquilo de que o algoritmo de Kruskal precisa para cada aresta.
Uma árvore de extensão mínima funciona para grafos dirigidos?
Não tal como está. Para grafos com arestas de sentido único, o problema correspondente é a arborescência de extensão mínima, resolvido pelo algoritmo de Chu–Liu/Edmonds.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Construir uma árvore de extensão mínima