Минимално разапињуће дрво¶

Примов алгоритам¶

Примов алгоритам конструише минимално разапињуће дрво тако што креће од произвољног чвора и у сваком кораку дрво које се конструише проширује тачно једним новим чвором и граном која тај чвор спаја са раније конструисаним дрветом. Претпоставимо да је конструисано поддрво траженог минималног разапињућег дрвета и размотримо скуп грана \(E_k\) које спајају чворове тог поддрвета са чворовима графа који су ван њега. Ако је полазни граф повезан и ако поддрво не садржи све чворове графа, тада је тај скуп грана увек непразан. Једна од тих грана сигурно мора бити укључена у крајњи резултат. Наиме, све гране ван тог скупа или повезују чворове унутар већ конструисаног поддрвета или повезују чворове који нису у њему, па је у циљу постизања повезаности јасно да је потребно одабрати бар једну грану из скупа \(E_k\), која спаја ове две за сада раздвојене компоненте. Примов алгоритам дрво проширује најкраћом граном \(e\) скупа \(E_k\) (ако има више грана исте дужине, могуће је узети било коју), јер је она сигурно део неког најмањег повезујућег дрвета. Ако би неко минимално повезујуће дрво садржало неку дужу грану \(e'\) скупа \(E_k\), тада би се њеним избацивањем оно раздвојило на два повезана поддрвета. Грана \(e\) повезује та два поддрвета и њеним убацивањем би се добило поново повезујуће стабло, које би било строго краће од минималног, што је, јасно, немогуће. Дакле, свако минимално повезујуће стабло мора да укључи бар једну грану скупа \(E_k\), а то не може бити ниједна грана која је дужа од најкраће гране тог скупа.

Наредна анимација илуструје примену Примовог алгоритма. Дрво које је у сваком кораку изграђено обележено је плавом бојом (и његови чворови и његове гране). Гране скупа \(E_k\) су обојене зеленом бојом. Црвене гране повезују чворове дрвета и оне неће бити додане у дрво (њих је могуће елиминисати из сваког даљег разматрања). Танке, црне гране су оне које још нису размотрене.

Ова анимација је направљена помоћу веб-апликације која је бесплатно доступна на сајту Математичког факултета Универзитета у Београду (http://www.matf.bg.ac.rs/~filip/algoritmi/prim.html). Употреби ову апликацију да провериш колико добро разумеш како функционише овај алгоритам.

И наредна анимација открива како Примов алгоритам функционише.

Анимација рада Примовог алгоритма, преузета са сајта https://en.wikipedia.org/wiki/Prim%27s_algorithm#/media/File:PrimAlgDemo.gif¶

Наредни C# код представља једну могућу имплементацију Примовог алгоритма. Примећујемо да је имплементација добијена модификовањем имплементације Дајкстриног алгоритма – једина разлика је то што у низу rastojanja не памтимо растојања сваког чвора од почетног, већ растојања сваког чвора од тренутног стабла.

Сложеност унутрашње петље која тражи чвор који није у стаблу а најближи му је је \(O(|V|)\). Пошто се спољна петља извршава \(O(|V|)\) пута, сложеност централног дела алгоритма је \(O(|V|^2)\) (сложеност учитавања графа је \(O(|V| + |E|)\)).

Слично као код Дајкстриног алгоритма, ефикаснија имплементација се може добити ако се гране скупа \(E_k\) чувају у реду са приоритетом (он омогућава да се гране ефикасно додају у скуп, да се ефикасно пронађе најкраћа међу њима и да се она ефикасно избаци из скупа). Сложеност такве имплементације је \(O((|E| + |V|) \log |V|)\).

Краскелов алгоритам¶

За разлику од Примовог алгоритма који минимално разапињуће дрво гради све време одржавајући неко његово поддрво, Краскелов алгоритам одржава његов подрграф који не мора бити дрво већ шума. Док Примов алгоритам бира најмању међу гранама које спајају дрво са остатком чворова, Краскелов алгоритам истовремено разматра све гране и међу њима бира најкраћу неодабрану грану која са до тада одабраним гранама не затвара циклус. Гране се на самом почетку сортирају по дужини (од најкраће до најдуже), обилазе се редом и за сваку се проверава да ли затвара циклус. Ако не, додаје се у шуму, а ако да, просто се прексаче. Алгоритам се завршава када се сви чворови повежу тј. када се дода \(n-1\) грана (где је \(n\) број чворова графа).

Докажимо коректност овог алгоритма.

Јасно је да алгоритам производи повезујуће дрво (пошто се експлицитно проверава да ниједна додата грана не чини циклус, а алгоритам се зауставља када се сви чворови повежу).

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

То важи у почетку (јер је почетна шума празна, нема одбачених грана, па било које минимално повезујуће дрво задовољава услов).

Претпоставимо да то важи у неком кораку тј. нека постоји неко такво дрво \(T\) и докажимо да важи и у следећем. Ако се у следећем кораку одбацује нека грана, она сигурно није део дрвета \(T\) (јер затвара циклус са гранама шуме, које су део дрвета \(T\), па би зато затварала циклус и у дрвету \(T\)). Претпоставимо зато да се у следећем кораку додаје нека грана \(e\). Ако је она део дрвета \(T\) услов је задовољен (дрво \(T\) садржи и проширену шуму). Ако грана \(e\) није део дрвета \(T\), тада она затвара неки циклус у дрвету \(T\). Тај циклус мора да садржи неку грану која није део шуме. Заиста, ако су све гране циклуса поред гране \(e\) део шуме, она би затварала циклус и у шуми, а то смо проверили да није случај. Нека је \(e'\) нека грана тог циклуса, различита од \(e\), која не припада шуми. Заменом те гране граном \(e\) поново се добија разапињуће дрво. Грана \(e'\) припада дрвету \(T\) па није одбачена, а пошто није део шуме, алгоритам је није размотрио. Пошто алгоритам разматра гране у неопадајућем поретку дужина, грана \(e'\) није краћа од гране \(e\), па је дрво добијено заменом гране \(e'\) граном \(e\) такође минимално.

Наредна анимација приказује рад алгоритма на једном примеру.

Ова анимација је направљена помоћу веб-апликације која је бесплатно доступна на сајту Математичког факултета Универзитета у Београду (http://www.matf.bg.ac.rs/~filip/algoritmi/kraskel.html). Употреби ову апликацију да провериш колико добро разумеш како функционише овај алгоритам.

И наредна анимација открива како Краскелов алгоритам функционише.

Анимација рада Примовог алгоритма, преузета са сајта https://en.wikipedia.org/wiki/Kruskal%27s_algorithm#/media/File:KruskalDemo.gif¶

Главно питање за имплементацију је како детектовати да ли додавање гране затвара циклус. У анимацији смо видели да је чворовима сваке компоненте повезаности у односу на до тада додате гране (сваког дрвета у шуми и сваког изолованог чвора) могуће доделити боје. Грана затвара циклус ако и само ако спаја чворове исте боје.

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

Скренимо пажњу на један технички детаљ. Спајање група (тј. промена боја) помоћу наредног кода не би радило како треба (пробај да одговориш зашто).

Сложеност спајања компоненти се може поправити коришћењем посебне структуре за представљање дисјунктних скупова (енгл. dijsoint-set, union-find). Опис ове структуре података превазилази овај курс, али заинтересоване ученике упућујемо да на интернету истраже како се она користи. Сложеност алгоритма у том случају може бити \(O(|E| \log{|V|})\).