Algoritmo di Borůvka

Da Wikipedia, l'enciclopedia libera.

L'algoritmo di Borůvka è un algoritmo per la ricerca di minimo albero ricoprente di un grafo in cui il peso di ciascuna coppia di archi sia distinto. Se due archi hanno peso uguale, è sufficiente modificare anche minimamente il peso di uno dei due archi per rendere valido l'algoritmo.

L'algoritmo venne pubblicato nel 1926 da Otakar Borůvka come metodo di costruzione di un efficiente rete elettrica per la Moravia (Repubblica Ceca). L'algoritmo fu riscoperto da Choquet nel 1938; successivamente da Florek, Łukasiewicz, Perkal, Steinhaus, e Zubrzycki nel 1951; e ancora da Sollin probabilmente all'inizio degli anni 60'. Dato che Sollin fu l'unico informatico occidentale in tale lista, questo algoritmo è spesso chiamato algoritmo di Sollin, specialmente nella letteratura del computing parallelo.

L'algoritmo comincia esaminando ciascun vertice e aggiungendo l'arco di costo minore da quel vertice ad un altro nel grafo, senza tenere conto di archi già aggiunti, e continua unendo questi raggruppamenti in modo simile finché un albero ricoprente tutti i vertici si completa. Lo pseudocodice per l'algoritmo è:

• Inizia con un grafo connesso G contente archi di peso diverso, e un insieme di archi vuoto, T
• Finché i vertici di G connessi da T sono disgiunti:
  • Inizia con un insieme vuoto di archi E
  • Per ciascun componente:
    • Inizia con un insieme di archi vuoto S
    • Per ciascun vertice nel componente:
      • Aggiungi l'arco di costo minore dal vertice nel componente verso un altro vertice in un componente disgiunto a S
    • Aggiungi l'arco di costo minore da S a E
  • Aggiungi l'insieme di archi risultante da E a T.
• L'insieme di archi risultanti T è il minimum spanning tree di G

L'algoritmo di Borůvka si dimostra avere una complessità computazionale O(E log V), dove E è il numero di archi, e V è il numero di vertici in G.

Altri algoritmi utili alla causa sono algoritmo di Prim (attualmente scoperto da Vojtěch Jarník) e Algoritmo di Kruskal. Algoritmi più veloci si ottengono combinando l'algoritmo di Prim e quello di Borůvka. Una versione randomizzata più veloce realizzata da Karger, Klein, e Tarjan lavora in tempi asintotici lineari nel numero di archi. Il più conosciuto algoritmo di calcolo del minimo albero ricoprente realizzato da Bernard Chazelle si basa su Borůvka e lavora in tempo O(E α(V)), dove α è l'inverso della Funzione di Ackermann.