From Wikipedia, the free encyclopedia
Примов алгоритам је алгоритам у теорији графова која налази минимално разапињуће стабло за повезани тежински граф. То значи да налази подскуп грана које формирају стабло које укључује све чворове, такав да је укупна тежина стабла минимизована. Алгоритам је 1930. године изумео Војтјех Јарник, а касније независно од њега информатичар Роберт Прим 1957, и поново Едсхер Дајкстра 1959. године. Стога се некад назива ДЈП алгоритмом или Јарниковим алгоритмом.
Алгоритам постепено повећава величину стабла почевши од једног чвора, док не повеже све чворове.
Структура података грана минималне тежине | Временска комплексност (укупно) |
---|---|
матрица суседства, претрага | |
бинарни хип (као у псеудокоду приказаном испод) и листа повезаности | |
Фибоначијев хип и листа повезаности |
Једноставна имплементација представљањем графа матрицом суседства и претраживањем низа тежина како би се пронашла грана најмање тежине захтева време . Коришћење једноставног бинарног хипа и листе повезаности, може се показати да је Примовом алгоритму потребно време од где је број грана, а је број чворова. Коришћењем софистициранијег Фибоначијевог хипа, ово се може спустити на , што је знатно брже када је граф довољно густ да је .
Слика | Опис | Несуседни чворови | Суседни чворови | Скуп решења |
---|---|---|---|---|
Ово је почетни тежински граф. Он није стабло, јер по дефиницији стабло нема циклова, а овај дијаграм садржи циклове. Бројеви поред грана означавају њихове тежине. Ниједна грана није обележена, а чвор је произвољно изабран за почетну тачку. | ||||
Други изабрани чвор је чвор најближи чвору : удаљеност је 5, удаљеност је 9, удаљеност је 15, а удаљеност је 6. Од ових бројева, 5 је најмањи, тако да обележавамо чвор и грану . | ||||
Затим бирамо чвор који је најближи било чвору било чвору . удаљеност од је 9, и 7 од , удаљеност је 15, а је 6. 6 је најмањи број, па бирамо чвор и грану . | ||||
Алгоритам настава на исти начин. Обележавамо чвор , чија удаљеност од је 7. | ||||
У овом случају можемо да бирамо између , , и . Удаљеност од је 8, од је 7, а од је 11. је најближе, па бирамо чвор и грану . | ||||
Сада су доступни само чворови и . Удаљеност од је 5, а удаљеност од је 9. Бирамо , као и грану . | ||||
Чвор је једини преостали чвор. Његова удаљеност од је 11, а од је 9. је ближе, па обележавамо грану . Сада су обележени сви чворови, и минимално разапињуће стабло је означено зеленом. У овом случају, минимална тежина је 39. |
Нека је повезан, тежински граф. У свакој итерацији Примовог алгоритма, мора се наћи грана која спаја чвор у подграфу са чвором ван подграфа. Како је повезан, увек ће постојати путања до сваког чвора. Излаз Примовог алгоритма, је стабло, јер су грана и чвор додати повезани. Нека је 1 минимално разапињуће стабло од . Ако је 1= онда је минимално разапињуће стабло. У супротном, нека је прва грана додата током конструкције која није у 1, а је скуп чворова повезаних гранама додатим пре . Тада је једна страна гране у а друга није. Како је 1 разапињуће стабло од , постоји путања у 1 која спаја две крајње тачке. Док се пролази ова путања, мора се проћи грана која спаја чвор у са неким који није у . Сада, у итерацији када се додаје , смо такође могли да додамо, и додали бисмо је уместо да је њена тежина била мања од . Како није додата, закључујемо да
Нека је 2 граф добијен уклањањем и додавањем у 1. Лако је показати да је 2 повезан, има исти број грана као 1, и његова укупна тежина није већа од 1, стога је такође минимално разапињуће стабло од и садржи и све гране додате пре њега током консрукције . Понављањем ових корака ће се коначно добити минимално разапињуће стабло од које је идентично . Ово показује да је минимално разапињуће стабло.
Неки од других алгоритама који решавају овај проблем су Крускалов алгоритам и Борувкин алгоритам.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.