Boruvka algoritam

Boruvka algoritam je algoritam za nalaženje minimalnog razapinjućeg stabla u grafu, gde su sve grane grafa različite težine.

Prvi put je objavljen 1926. godine od strane Otkar Boruvka kao metoda izgradnje efikasne električne mreže za Moravsku. Algoritam je ponovo otkrio Choquet 1938. godine, posle njega Florek, Łukasiewicz, Perkal, Steinhaus, i Zubrzycki 1951. godine, zatim Solin 1965. godine. Solim je bio jedini kompjuterski naučnik u zemlji gde se pričalo na engleskom jeziku pa se algoritam često zove i Sollinov algoritam, posebno u paralelnoj kompjuterskoj literaturi.

Algoritam počinje prvo ispitivanje svakog čvora i dodavanjem najjeftinije grane od temena do drugog temena u grafu, bez obzira na već dodate grane, i nastavlja spajanja ovih grupacija na sličan način sve dok drvo ne obuhvati sve čvorove.

Pseudo kod

Imenovanje svakog čvora ili skup povezanih čvorova "komponenta", pseudo kod za algoritam Boruvka je:

 Ulaz: Povezan graf G čije grane imaju različite težine.
 1 Počinje sa T kao skup čvorova, svaki posmatrati kao jednu komponentu.
 2 Dok T ima više od jedne komponente:
 3   Za svaku komponentu C od T:
 4     Počinje sa praznim skupom grana S
 5     Za svaki čvor v u C:
 6       Pronađi granu najmanje težine od V do čvora izvan C, i dodajte ga u S
 7    Dodaj granu najmanje težine u S od T
 8 T je minimalno razapinjuće stablo od G.

Kao i u Kruškalovom algoritmu, praćenje komponente T može se efikasno uraditi koristeći pogodnu strukturu podataka. U grafovima gde grane imaju identične vrednosti, grane sa jednakim vrednostima možemo odraditi na osnovu leksikografskog poređenja od svojih krajnjih tačaka.

Složenost

Boruvka algoritam može da se pokaže u O(log V) iteracija spoljašnje petlje dok ne prestane, i zato radi u vremenu O(E log V), gde je E broj grana, a V broj čvorova u grafu G. U planarne grafove, i uopšte u pordicama grafova zatvoren ispod grafikona manjih operacija, može biti napravljen da radi u linearnom vremenu, uklanjanjem svih najjeftinijih grana između svakog para komponenti posle svake faze algoritma.

Primer 1

Slika	komponente	Opis
	-Шаблон:A {B} {C} {D} {E} {F} {G}}-	Ovo je naš originalni težinski graf. Broj pored grana ukazuje na njihovu težinu. Inicijalno, svaki čvor je komponenta za sebe (plavi krugovi).
	{A,B,D,F} {C,E,G}	U prvoj iteraciji spoljašnje petlje, minimalna vrednost grane svake komponente se dodaje. Neke grane su selektovane dva puta (AD, CE). Dve komponente ostaju.
	{A,B,C,D,E,F,G}	U drugoj i poslednjoj iteraciji, minimalna težina grana od svake od dve preostale komponente se dodaje. Uočimo da je to ista grana. Jedna komponenta ostaje i mi smo završili. Grana BD se ne smatra jer su oba čvora (B i D) u istoj komponenti.

Primer 2

Ostali algoritmi

Ostali algoritmi za ovaj problem uključuju Primov algoritam i Kruskalov algoritam. Brzi paralelni algoritmi se mogu dobiti kombinovanjem Primovog algoritma sa Boruvkinim algoritmom. Brže pseudo slučajno generisano razapinjuće stablo zasnovano je na delovima Boruvkinovog algoritma zbog Kargera, Kleina, i Tarjana, radi u očekivanom O(E) vremenu. Najpoznatiji (deterministički) minimalno razapinjuće stablo algoritam od Bernar Chazelle je takođe delimično zasnovan na Boruvkinim algoritmom iradi u O(E α(E,V)) vremenu, gde je α inverzna Ackermann funkcija. Ove randomizovane i deterministički zasnovane algoritme kombinuju korake Boruvka algoritma, smanjenje broja komponenti koji ostaju da budu povezani, sa koracima od različitog tipa koji smanjuje broj grana između parova komponenti.