Árvore de cobertura mínima

Uma primeira tentativa

Pode ser muito simples fazer um algoritmo que irá descobrir uma árvore de espaçamento mínimo:

 função MST(G,W)     : T = {     } enquanto que T não forma uma árvore de envergadura:          encontrar a borda mínima ponderada em E que é segura para T T = T união {(u,v)     } retorno T

Neste caso, "seguro" significa que a inclusão da borda não forma um ciclo no gráfico. Um ciclo significa começar em um vértice, viajar para vários outros vértices e terminar no ponto de partida novamente sem usar a mesma borda duas vezes.

História

O cientista tcheco Otakar Borůvka desenvolveu o primeiro algoritmo conhecido para encontrar uma árvore de espaçamento mínimo, em 1926. Ele queria resolver o problema de encontrar uma cobertura eficiente da Moravia com eletricidade. Hoje, este algoritmo é conhecido como o algoritmo do Borůvka. Dois outros algoritmos são comumente usados hoje em dia. Um deles foi desenvolvido por Vojtěch Jarník em 1930, e colocado em prática por Robert Clay Prim em 1957. Edsger Wybe Dijkstra redescobriu-o em 1959, e chamou-o de algoritmo do Prim. O outro algoritmo é chamado de algoritmo de Kruskal, e foi puxado por Joseph Kruskal em 1956. Todos os três algoritmos são gananciosos, e funcionam em tempo polinomial.

O algoritmo de árvore de cobertura mínima mais rápido até o momento foi desenvolvido por Bernard Chazelle. O algoritmo é baseado na pilha macia, uma fila de prioridade aproximada. Seu tempo de execução é O(m α(m,n)), onde m é o número de bordas, n é o número de vértices e α é o clássico inverso funcional da função Ackermann. A função α cresce extremamente lentamente, de modo que para todos os fins práticos ela pode ser considerada uma constante não superior a 4; assim, o algoritmo de Chazelle leva um tempo muito próximo do linear.

Qual é o algoritmo mais rápido possível para este problema? Essa é uma das perguntas mais antigas em aberto na ciência da computação. Existe claramente um limite inferior linear, uma vez que devemos ao menos examinar todos os pesos. Se os pesos de borda são inteiros com um comprimento de bit delimitado, então os algoritmos determinísticos são conhecidos com tempo de execução linear. Para pesos gerais, existem algoritmos randomizados cujo tempo de execução esperado é linear.

O problema também pode ser abordado de forma distribuída. Se cada nó for considerado um computador e nenhum nó souber de nada, exceto de seus próprios links conectados, ainda será possível calcular a árvore de abrangência mínima distribuída.