Borůvkova MST

O(E log V)

Borůvkův algoritmus — nejstarší MST algoritmus — pracuje v kolech. Každý vrchol začíná jako vlastní komponenta. V každém kole každá komponenta současně vybere nejlevnější hranu, která z ní vede, a všechny tyto hrany se přidají naráz, čímž sloučí komponenty, které spojují. Protože každé kolo aspoň způlí počet komponent, je potřeba jen O(log V) kol, celkem O(E log V). Přidávání mnoha hran paralelně z něj dělá přirozeného kandidáta pro distribuovaný a paralelní výpočet MST, na rozdíl od striktně sekvenčních Prima a Kruskala. Tady jsou váhy hran vzdálenosti mezi uzly.

Klik do prázdna = vrchol · klik na 2 vrcholy = hrana · táhni = posuňStart: A
Vstupní graf
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Začni s každým vrcholem jako vlastní komponentou.
  2. Každé kolo najde každá komponenta svou nejlevnější odchozí hranu.
  3. Přidej všechny tyto hrany naráz a slouč komponenty, které spojují (přeskoč duplicity).
  4. Opakuj, dokud jedna komponenta nepokryje celý graf.

Pseudokód

1boruvka(graph):                     # O(E log V)2  each vertex starts as its own component3  while more than one component:4    for each component:5      find its cheapest outgoing edge6    add all those edges at once (skip duplicates)7    union the components they join