алгоритъм за търсене минимум обхваща дърво

Минималната обхваща дърво (МР), свързан претеглена графика е свързан подграф на това, състояща се от всички дървесни върховете на източника и някои от неговите ребра, и сумата от теглата на краищата възможния минимум. Ако първоначалният графиката е изключен, процедурата, описана по-долу може да се прилага последователно към всяка от своя свързан компонент, като по този начин получаване на минималните обхващащи дърветата за тези компоненти.
МР за свързания графиката може да се намери от груба сила. Тъй като множество от ребра МР е подмножество на множеството от ребрата на източника, можете просто да се опитаме всички възможни подмножества и да намерите сред тях МР. Лесно е да се види, че това е изключително много време процес. Множеството от ребра N разполага с 2 N подгрупи. За всяка от тези подгрупи, ние ще трябва да се уверите, че той е свързан подграф комплекти, обхващащи всички върховете на оригинала, и не съдържа цикли, а след това се изчисли теглото. Процесът може да се ускори, след като установи, първият обхваща дървото. Не подмножество на краищата, общото тегло е по-голяма от тази, вече са намерили най-добрия обхващаща дървото, не можем да отидем, така че не е необходимо да се провери свързаност, ациклични и покритието на всички върхове. Въпреки това, дори и с този подобрен метод, сложността на груба сила е О поръчка (2 N).

Дейкстра-Prim
В края на 1950-те и Едгар Дейкстра Забележка изработване и публикуването на резултатите, независимо, ние предложихме следния алгоритъм за построяване MOD.
Ние използваме, за да търсят така наречените "алчни" алгоритъма на МР. Алчен акт, като се използва всеки път, когато само част от оригиналните данни и като най-доброто решение, въз основа на тази част. В нашия случай ние ще обсъдим на всеки етап от множество перки, които позволяват свързване към вече изградени част от която обхваща дървото, и изберете от тях на ръба с най-ниско тегло. Повтарянето на тази процедура, ние се получи обхваща дърво с най-ниско тегло.
Ние разделяме върховете в три класа: върховете включени в изградената от страна на върховете на дърветата, граничещи построен част, и не считат за върха. Нека започнем с произволен връх и да го включа в обхващащи дърво. В резултат на строителството ще бъде неизкоренени дървета, избор на вход връх не влияе на крайния резултат (разбира се, ако Министерството на отбраната само). Всички върхове, свързани с това, въвеждат в в джантата. След това краищата на цикъла за търсене с най-ниско тегло, свързващ вече изградени част от която обхваща дървото с граница; този край с нов връх се добавя към дървото и актуализира границата. След като всички възли в падането на дървото, работата ще бъде завършена.
Тук е алгоритъм: Фигура 1 съгласно алгоритъма, описан като пример. В началото на процеса, който избере произволно възел А. Както казахме, различен избор от първоначалния резултат от връх ще бъде същото, както ако МР е уникален. Оригиналният графиката е показано на фиг. 1 (а) и, както вече бе споменато, ние започне изграждането от горния MOD А. Всички върхове директно свързани към А, образуват оригинален джантата. Може да се види, че в края на малко тегло свързва възли А и В, следователно, към вече изработена част на мод добавя връх Б с AB ръб. Когато се добави към върха на дърво B (фиг. 1) (с), ние трябва да се определи дали не трябва да се добавят до границата на новите върхове. В резултат на това, ние откриваме, че тя трябва да се направи с върховете Е и Ж., тъй като тези два върха са свързани само с върха Б вече е построена част от дървото, ние добавяме към списъка на запечатване ребра, разгледани на следващата стъпка. Тук е необходимо да се провери дали краищата водещи от връх А до С, D и F, най-краткия между краищата свързващи тези възли с дърво или има по-удобни ръбове, произтичащи от колона В. В началния връх В не е свързан директно към всеки C, или с F, така че за тях нищо не се е променило. Но край BD АД къси ребра, и следователно трябва да го замени. Flyweight пет ръбове развиват в джантата, е предимство BE, така че дървото е необходимо да се добавят към горната и Е (фиг. 1 (г)). EG перка тегло по-малко тегло BG ребра, така че той замества последния. От четирите краища водещи в ръба, най-малкото тегло има климатик, така се добавя към дървото. Като прибавим към обхващащи дърво ръбовете и върховете C AC (фиг. 1 (г)) за не променя списъка на ръбове.
След това изберете реброто AF и го добавете към дървото с горната част на F. В допълнение, ние променяме списъка с връзки, както и FD перки тежат по-малко от теглото на BD ребра и ребро FG тегло по-малко тегло EG ребра. Получената ресни (фиг. 1 (д)) FD ребро има най-малкото тегло сред останалите и се добавя, както следва.
Сега трябва да се добави към дървото само един блок (фиг. 1 (г)). След този процес е завършен, и вграден MOD корени на връх А (фиг. 1 (з)).

алгоритъм Kruskal на
Prima Дейкстра алгоритъм започва с изграждане MOD специфичен връх и постепенно се разширява дървото изградени; За разлика от алгоритъма Kruskal фокусира върху ръбовете.
В този алгоритъм, започваме с празен дърво и го добавете към ребрата, за увеличаване на теглото, докато не получи набор от ръбове, която съчетава всички върхове. Ако ребрата се изчерпят преди всички върхове са свързани помежду си, това означава, че оригиналният брой е бил откачен и се свържете резултатът е обединение MOD всички свои свързани компоненти.
Работим с една и съща графика (вж. Фиг. 2 (а)), и че описанието на алгоритъм на Dijkstra -Prima. Нека започнем с краищата на най-малко тегло, което означава, КВ ребра. В първоначалното положение е показано на фиг. 2 (Ь).
Следното се добавя към теглото на реброто 2, свързваща точките А и В (фигура 2 (с).), а след това - на теглото на ръб три, и ние имаме ситуация с ориз. 2 (д).
Към получения графиката са добавени последователно ребра тегла 4 и 5 (Фигури 2 (г) и (д)). Само остава несвързан връх Г. Следваща трябва да имаме предвид теглото на перките 6.
Две от четирите краища на тегло 6 трябва да се изхвърли, тъй като допълнение им ще доведе до цикъл в вече изработена част на МР. CF ребра присъединяване ще създаде контур, съдържащ пик А, и ръбовете свързващи BD - цикъл, съдържащ пикове А и Е. Останалите две възможности са еднакво подходящи, и избиране на една от тях, ние получи MOD с фиг. 2 (г), или МР с ориз. 2 (Н).

Тук е общ алгоритъм, който изпълнява тази процедура (броят на ръбове в графиката е обозначен с Е и броя на пиковете - чрез N): Основната линия се изпълнява, докато стойността на променливата edgeCount не съвпада с броя на ръбовете в графиката, или докато променливата includedCount не показват че сме добавили достатъчно ребра, за да образуват обхващаща дърво. Имайте предвид, че обхваща дърво в графика с N върха трябва да има N - 1 край.
Във вътрешността на линия, за първи път се намери родителите на върха свързани с ребро, добавя още един. Ако тези върхове принадлежат към различни дялове на корените, добавяйки ръбове между тях няма да доведе до цикъл и два дяла се слеят в един общ корен. Практики FindRoot и на Съюза, са описани подробно в статията "дял на снимачната площадка."
Сложността на този алгоритъм е същото като сложността на алгоритъм за сортиране използва, тъй като броят на операциите в рамките на цикъла, докато линейно с броя на ръбове. Поради това, сложността на алгоритъма за търсене на Kruskal MOD е O (E дневник E).