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

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.

Графовски алгоритми
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 godine od strane Otkar Boruvka kao metoda izgradnje efikasne električne mreže za Moravsku . Algoritam je ponovo otkrio Choquet godine , posle njega Florek , -{ Łukasiewicz }- , Perkal , Steinhaus , i -{ Zubrzycki }- godine , zatim Solin 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 . Počinje sa T kao skup čvorova , svaki posmatrati kao jednu komponentu . Dok T ima više od jedne komponente : Za svaku komponentu C od T : Počinje sa praznim skupom grana S Za svaki čvor v u C : Pronađi granu najmanje težine od V do čvora izvan C , i dodajte ga u S Dodaj granu najmanje težine u S od T 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 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 . Графовски алгоритми