Кіріспе
Минималды жайылған ағаштарды табу әдісі
Борувка алгоритмі – графтардағы минималды жайылған ағашты немесе байланысқан емес графтардағы минималды жайылған орманды табуға арналған ашкөз алгоритм. Ол алғаш рет 1926 жылы Отакар Борувка Моравия үшін тиімді электр желісін құру әдісі ретінде жарияланған. Алгоритмді 1938 жылы Шоке, 1951 жылы Флорек, Лукасевич, Перкал, Штайнхаус және Зубржицки, ал 1965 жылы Жорж Солин қайтадан ашты. Бұл алгоритм көбінесе Соллин алгоритмі деп аталады, әсіресе параллель есептеулер әдебиетінде. Алгоритм графтың әрбір төбесіне келіп тірелетін ең төмен салмақты жиекті табудан басталады және барлық жиектерді орманға қосады. Содан кейін, ол осыған ұқсас процесті қайталайды, соған дейін құрылған әрбір ағаштан басқа ағашқа ең төмен салмақты жиекті табуға дейін, және барлық жиектерді орманға қосады. Бұл процестің әрбір қайталануы графтың әрбір байланысқан компонентіндегі ағаштар санын бұрынғы санының жартысына дейін азайтады, сондықтан логарифмдік қайталанулардан кейін процесс аяқталады. Ол аяқталғанда, оның қосылған жиектері жиынтығы минималды жайылған орманды құрайды.
or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia. The algorithm was rediscovered by Choquet in 1938; again by Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki in 1951; and again by Georges Sollin in 1965. This algorithm is frequently called Sollin's algorithm, especially in the parallel computing literature. The algorithm begins by finding the minimum weight edge incident to each vertex of the graph, and adding all of those edges to the forest. Then, it repeats a similar process of finding the minimum weight edge from each tree constructed so far to a different tree, and adding all of those edges to the forest. Each repetition of this process reduces the number of trees, within each connected component of the graph, to at most half of this former value,
so after logarithmically many repetitions the process finishes. When it does, the set of edges it has added forms the minimum spanning forest.
Күрделілігі
Борувка алгоритмі аяқталуына дейін [[Big O нотациясы]] итерациясы сыртқы циклді қажет етеді, демек, оның орындалу уақыты [[Big O нотациясы]]-на тең, мұнда E – жиектер саны, ал V – G графындағы төбелер саны (E ≥ V деп есептесек). Жазық графтарда және жалпы алғанда, граф кіші операциялары бойынша жабық графтар отбасында алгоритмнің әр кезеңінен кейін әрбір компоненттер жұбы арасындағы ең арзан жиекті жою арқылы сызықтық уақытта орындалуы мүмкін.
Мысал
Сурет компоненттері Аңдау {A}{B}{C}{D}{E}{F}{G}Бұл біздің бастапқы салмақталған графигіміз. Қабырғаларының жанындағы сандар олардың салмағын көрсетеді. Бастапқыда әрбір төбе өзі жеке компонент болып табылады (көк шеңберлер). {A,B,D,F}{C,E,G} Сыртқы циклдің бірінші итерациясында әр компоненттен ең төмен салмақты қабырғалар қосылады. Кейбір қабырғалар екі рет таңдалады (AD, CE). Екі компонент қалды. {A,B,C,D,E,F,G} Екінші және соңғы итерацияда қалған екі компоненттен ең төмен салмақты қабырғалар қосылады. Бұл жағдайда олар бір қабырғаға сәйкес келеді. Бір компонент қалды және жұмыс аяқталды. BD қабырғасы қарастырылмайды, өйткені оның екі ұшы да бір компонентте орналасқан.
Басқа алгоритмдер
Бұл мәселеге арналған басқа алгоритмдерге Прим алгоритмі және Крускал алгоритмі жатады. Прим алгоритмін Борувка алгоритмімен біріктіру арқылы жылдам параллель алгоритмдерді алуға болады. Каргер, Клейн және Тарян еңбектеріндегі Борувка алгоритміне негізделген, жылдам рандомизацияланған ең кішкентай қамтитын ағаш алгоритмі күтілетін O(E) уақытында жұмыс істейді. Бернард Шазельдің ең жақсы танымал (детерминистік) ең кішкентай қамтитын ағаш алгоритмі де ішінара Борувкаға негізделген және O(E α(E,V)) уақытында жұмыс істейді, мұнда α – кері Акерманн функциясы. Бұл рандомизацияланған және детерминистік алгоритмдер Борувка алгоритмінің қадамдарын біріктіреді, қосылуы керек компоненттердің санын азайтады, сондай-ақ компоненттер жұбы арасындағы қабырғалар санын азайтатын басқа типтегі қадамдармен үйлеседі.