Примов алгоритам
Примов алгоритам је алгоритам у теорији графова која налази минимално разапињуће стабло за повезани тежински граф. То значи да налази подскуп грана које формирају стабло које укључује све чворове, такав да је укупна тежина стабла минимизована. Алгоритам је 1930. године изумео Војтјех Јарник, а касније независно од њега информатичар Роберт Прим 1957, и поново Едсхер Дајкстра 1959. године. Стога се некад назива ДЈП алгоритмом или Јарниковим алгоритмом.
Опис
[уреди | уреди извор]Алгоритам постепено повећава величину стабла почевши од једног чвора, док не повеже све чворове.
- Улаз: Повезан тежински граф G(V, E)
- Иницијализација: V' = {x}, где је x произвољан чвор из V, E'= {}
- понављање док не постане V'=V:
- Изабери грану (u, v) из E са минималном тежином, такву да је u из V' а v није из V' (ако има више грана исте тежине, изабрати произвољну)
- Додај v у V', и (u, v) у E'
- Излаз: G(V', E') је минимално разапињуће стабло
Временска комплексност
[уреди | уреди извор]| Структура података грана минималне тежине | Временска комплексност (укупно) |
|---|---|
| матрица суседства, претрага | V² |
| бинарни хип (као у псеудокоду приказаном испод) и листа повезаности | O((V + E) log(V)) = E log(V) |
| Фибоначијев хип и листа повезаности | E + V log(V) |
Једноставна имплементација представљањем графа матрицом суседства и претраживањем низа тежина како би се пронашла грана најмање тежине захтева време O(V²). Коришћење једноставног бинарног хипа и листе повезаности, може се показати да је Примовом алгоритму потребно време од O(Elog V) где је E број грана, а V је број чворова. Коришћењем софистициранијег Фибоначијевог хипа, ово се може спустити на O(E + Vlog V), што је знатно брже када је граф довољно густ да је E (Vlog V).
Пример
[уреди | уреди извор]| Слика | Опис | Несуседни чворови | Суседни чворови | Скуп решења |
|---|---|---|---|---|
|
Ово је почетни тежински граф. Он није стабло, јер по дефиницији стабло нема циклова, а овај дијаграм садржи циклове. Бројеви поред грана означавају њихове тежине. Ниједна грана није обележена, а чвор D је произвољно изабран за почетну тачку. | C, G | A, B, E, F | D |
|
Други изабрани чвор је чвор најближи чвору D: удаљеност A је 5, удаљеност B је 9, удаљеност E је 15, а удаљеност F је 6. Од ових бројева, 5 је најмањи, тако да обележавамо чвор A и грану DA. | C, G | B, E, F | A, D |
|
Затим бирамо чвор који је најближи било чвору D било чвору A. удаљеност B од D је 9, и 7 од A, удаљеност E је 15, а F је 6. 6 је најмањи број, па бирамо чвор F и грану DF. | C | B, E, G | A, D, F |
|
Алгоритам настава на исти начин. Обележавамо чвор B, чија удаљеност од A је 7. | null | C, E, G | A, D, F, B |
|
У овом случају можемо да бирамо између C, E, и G. Удаљеност C од B је 8, E од B је 7, а G од F је 11. E је најближе, па бирамо чвор E и грану EB. | null | C, G | A, D, F, B, E |
|
Сада су доступни само чворови C и G. Удаљеност C од E је 5, а удаљеност G од E је 9. Бирамо C, као и грану EC. | null | G | A, D, F, B, E, C |
|
Чвор G је једини преостали чвор. Његова удаљеност од F је 11, а од E је 9. E је ближе, па обележавамо грану EG. Сада су обележени сви чворови, и минимално разапињуће стабло је означено зеленом. У овом случају, минимална тежина је 39. | null | null | A, D, F, B, E, C, G |
Доказ коректности
[уреди | уреди извор]Нека је P повезан, тежински граф. У свакој итерацији Примовог алгоритма, мора се наћи грана која спаја чвор у подграфу са чвором ван подграфа. Како је P повезан, увек ће постојати путања до сваког чвора. Излаз Примовог алгоритма, Y је стабло, јер су грана и чвор додати Y повезани. Нека је Y1 минимално разапињуће стабло од P. Ако је Y1=Y онда је Y минимално разапињуће стабло. У супротном, нека је e прва грана додата током конструкције Y која није у Y1, а V је скуп чворова повезаних гранама додатим пре e. Тада је једна страна гране e у V а друга није. Како је Y1 разапињуће стабло од P, постоји путања у Y1 која спаја две крајње тачке. Док се пролази ова путања, мора се проћи грана f која спаја чвор у V са неким који није у V. Сада, у итерацији када се e додаје Y, f смо такође могли да додамо, и додали бисмо је уместо e да је њена тежина била мања од e. Како f није додата, закључујемо да
- w(f) ≥ w(e). (w(f) је тежина од f)
Нека је Y2 граф добијен уклањањем f и додавањем e у Y1. Лако је показати да је Y2 повезан, има исти број грана као Y1, и његова укупна тежина није већа од Y1, стога је такође минимално разапињуће стабло од P и садржи e и све гране додате пре њега током консрукције V. Понављањем ових корака ће се коначно добити минимално разапињуће стабло од P које је идентично Y. Ово показује да је Y минимално разапињуће стабло.
Неки од других алгоритама који решавају овај проблем су Крускалов алгоритам и Борувкин алгоритам.
Литература
[уреди | уреди извор]- V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63. (in Czech)
- R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
- D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. 2001. ISBN 978-0-262-03293-3.. Section 23.2: The algorithms of Kruskal and Prim, pp.567-574.
