Борувка алгоритам

Борувка алгоритам је алгоритам за налажење минималног разапињућег стабла у графу, где су све гране графа различите тежине.

Први пут је објављен 1926. године од стране Откар Борувка као метода изградње ефикасне електричне мреже за Моравску. Алгоритам је поново открио Цхоqует 1938. године, после њега Флорек, Łukasiewicz, Перкал, Стеинхаус, и Zubrzycki 1951. године, затим Солин 1965. године. Солим је био једини компјутерски научник у земљи где се причало на енглеском језику па се алгоритам често зове и Соллинов алгоритам, посебно у паралелној компјутерској литератури.

Алгоритам почиње прво испитивање сваког чвора и додавањем најјефтиније гране од темена до другог темена у графу, без обзира на већ додате гране, и наставља спајања ових групација на сличан начин све док дрво не обухвати све чворове.

Псеудо код

Именовање сваког чвора или скуп повезаних чворова "компонента", псеудо код за алгоритам Борувка је:

 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.

Као и у Крушкаловом алгоритму, праћење компоненте Т може се ефикасно урадити користећи погодну структуру података. У графовима где гране имају идентичне вредности, гране са једнаким вредностима можемо одрадити на основу лексикографског поређења од својих крајњих тачака.

Сложеност

Борувка алгоритам може да се покаже у O(log V) итерација спољашње петље док не престане, и зато ради у времену O(E log V), где је E број грана, а V број чворова у графу G. У планарне графове, и уопште у пордицама графова затворен испод графикона мањих операција, може бити направљен да ради у линеарном времену, уклањањем свих најјефтинијих грана између сваког пара компоненти после сваке фазе алгоритма.

Пример 1

Слика	компоненте	Опис
	-Шаблон:А {Б} {C} {D} {Е} {Ф} {Г}}-	Ово је наш оригинални тежински граф. Број поред грана указује на њихову тежину. Иницијално, сваки чвор је компонента за себе (плави кругови).
	{А,Б,D,Ф} {C,Е,Г}	У првој итерацији спољашње петље, минимална вредност гране сваке компоненте се додаје. Неке гране су селектоване два пута (AD, CE). Две компоненте остају.
	{А,Б,C,D,Е,Ф,Г}	У другој и последњој итерацији, минимална тежина грана од сваке од две преостале компоненте се додаје. Уочимо да је то иста грана. Једна компонента остаје и ми смо завршили. Грана BD се не сматра јер су оба чвора (B i D) у истој компоненти.

Пример 2

Остали алгоритми

Остали алгоритми за овај проблем укључују Примов алгоритам и Крускалов алгоритам. Брзи паралелни алгоритми се могу добити комбиновањем Примовог алгоритма са Борувкиним алгоритмом. Брже псеудо случајно генерисано разапињуће стабло засновано је на деловима Борувкиновог алгоритма због Каргера, Клеина, и Тарјана, ради у очекиваном O(E) времену. Најпознатији (детерминистички) минимално разапињуће стабло алгоритам од Бернар Цхазелле је такође делимично заснован на Борувкиним алгоритмом иради у O(E α(E,V)) времену, где је α инверзна Ацкерманн функција. Ове рандомизоване и детерминистички засноване алгоритме комбинују кораке Борувка алгоритма, смањење броја компоненти који остају да буду повезани, са корацима од различитог типа који смањује број грана између парова компоненти.