Преглед на кодот на Примов алгоритам

Во компјутерските науки, '''Примовиот алгоритам''' е [[алчен алгоритам]] што ја наоѓа минималната патека на дрво во еден [[граф]]. Ова значи дека ќе најде подмножество на рабови од кој се формира едно стебло, кое го вклучува секое теме каде што вкупната тежина на сите на рабови на дрвото е минимална. Алгоритмот е развиен во [[1930]] година од страна на чешкиот математичар [[Војтеч Јарник]], подоцна независно од компјутерскиот научник [[Роберт Прим]] во [[1957]] година и откриени по [[Едсгер Дајкстра]] во [[1959]] година. Други алгоритми за решавање на овој проблем го вклучуваат и [[Курскалов алгоритам|Крускаловиот алгоритам]] и [[Алгоритам на Борувка|алгоритамот на Борувка]].

== Опис ==
=== Неформален ===
*Создава дрво кое содржи едно теме, избран произволно од графот
*Создава група која ги содржи сите рабови во графот
*Поврзува сè додека секој раб поврзува две темиња во дрво
*Отстранува од граф раб со минимална тежина кој поврзува теме од дрвото со теме кое не е во дрвото
*Го додава тој раб во дрвото

=== Технички ===
Алгоритамот на Прим има многу голема примена, како на пример во генерирање на овој лавиринт во кој се применува алгоритмот на Прим на случајно одбран граф.
Единственото дрво на празен граф (со празен сет на темиња) е повторно празен граф. Следниов опис претпоставува дека овој посебен случај се постапува одделно.
Алгоритмот постојано ја зголемува големината на дрвото, еден раб во еден момент, почнувајќи од дрво што се состои од едно теме, сè додека не ги спои сите темиња.
*Влез: Не-празен граф, поврзан со темиња V и рабови Е(тежините неможат да бидат негативни).
*Иницијализира: Vnew = {x}, каде x е произволен јазол (почетна точка) од V, Enew = {}
*Повторете сè додека Vnew = V
** Изберете раб (u, v) со минимална тежина, како што U е во Vnew и V не е (ако постојат повеќе рабовите со иста тежина, некој од нив може да се подигнат)
** Додај v за да Vnew, и (u, v) да Enew
* Излез: Vnew и Enew опише минимална опфаќа дрво

== Временска комплексност ==
{| class="wikitable"
! Minimum edge weight data structure !! Time complexity (total)
|-
| [[adjacency matrix]], searching || O(V<sup>2</sup>)
|-
| [[binary heap]] and [[adjacency list]] || O((V + E) log V) = O(E log V)
|-
| [[Fibonacci heap]] and [[adjacency list]] || O(E + V log V)
|}
Едноставна имплементација на користење на адјунгирана матрична графичка застапеност и потрага за низа на тежини за да го најдете најмалиот раб за да додадете е потребна О,  време за извршување. Користејќи едноставна бинарна хип податочна структура и адјунгирана список на застапеност, алгоритмот на Прим може да биде прикажан во времето О(E log V), каде Е е бројот на рабовите и V е бројот на темиња. Со користење на пософистициран Фибоначиев хип, ова може да се сведе на О (Е + V log V), кое  е асимптоматично побрзо кога графот е  доволно густ, E е Ω (V).

== Пример ==

{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
! | Слика
! | U
! width="100" | Раб(u,v)
! | V \ U
! | Опис
|-
|[[Image:Prim Algorithm 0.svg|200px]]
| {} ||   || {A,B,C,D,E,F,G}
|Ова е нашиот оригинален граф. Броевите во близина на рабовите ја означуваат неговата тежина.
|-
|[[Image:Prim Algorithm 1.svg|200px]]
| {D} || (D,A) = 5   '''V''' <BR>(D,B) = 9<BR>(D,E) = 15<BR>(D,F) = 6 || {A,B,C,E,F,G}
|Темето '''D''' е произволно избран како почетна точка. Вертиците '''A''', '''B''', '''E''' и '''F''' се поврзани со '''D''' преку еден раб. '''A''' е теме најблиску до '''D''' и ќе биди одбран како второ теме покрај работ '''AD'''.
|-
|[[Image:Prim Algorithm 2.svg|200px]]
| {A,D} || (D,B) = 9<BR>(D,E) = 15<BR>(D,F) = 6    '''V'''<BR>(A,B) = 7 || {B,C,E,F,G}
|Следното одбрано теме е темето најблиску до '''D''' или '''A'''. '''B''' е 9 подалеку од '''D''' и 7 подалеку од '''A''', '''E''' е 15, и '''F''' е 6. '''F''' е најмалку оддалечен, па го означуваме темето '''F''' и работ '''DF'''.
|-
|[[Image:Prim Algorithm 3.svg|200px]]
| {A,D,F} || (D,B) = 9<BR>(D,E) = 15<BR>(A,B) = 7  '''V'''<BR>(F,E) = 8<BR>(F,G) = 11 || {B,C,E,G}
|Алгоритамот продолжува како и погоре. Темето '''B''', кое е 7 оддалечено од '''A''', е означено.
|-
|[[Image:Prim Algorithm 4.svg|200px]]
| {A,B,D,F} || (B,C) = 8<BR>(B,E) = 7   '''V'''<BR>(D,B) = 9  циклус<BR>(D,E) = 15<BR>(F,E) = 8<BR>(F,G) = 11 || {C,E,G}
|Во овој случај, можеме да одбереме помеѓу '''C''', '''E''', и '''G'''. '''C''' е 8 оддалечено од '''B''', '''E''' е 7 оддалечено од '''B''', и '''G''' е 11 away fromоддалечено од '''F'''. '''E''' е најблиску, па го обележуваме темето '''E''' и работ '''BE'''.
|-
|[[Image:Prim Algorithm 5.svg|200px]]
| {A,B,D,E,F} || (B,C) = 8<BR>(D,B) = 9  циклус<BR>(D,E) = 15   циклус<BR>(E,C) = 5    '''V'''<BR>(E,G) = 9<BR>(F,E) = 8   циклус<BR>(F,G) = 11 || {C,G}
|Овде, единственте можни вертици се '''C''' и '''G'''. '''C''' е 5 оддалечено од '''E''', и '''G''' е 9 оддалечено од '''E'''. '''C''' е одбрано, па тоа е обележано по работ '''EC'''.
|-
|[[Image:Prim Algorithm 6.svg|200px]]
| {A,B,C,D,E,F} || (B,C) = 8 циклус<BR>(D,B) = 9  циклус<BR>(D,E) = 15   циклус<BR>(E,G) = 9   '''V'''<BR>(F,E) = 8  циклус<BR>(F,G) = 11 || {G}
|Темето '''G''' е единственото теме кое останува. ТОа е 11 оддалечено '''F''', и 9 оддалечено од '''E'''. '''E''' е поблиску, па го обележуваме '''G''' и работ '''EG'''.
|-
|[[Image:Prim Algorithm 7.svg|200px]]
| {A,B,C,D,E,F,G} || (B,C) = 8 циклус<BR>(D,B) = 9  циклус<BR>(D,E) = 15   циклус<BR>(F,E) = 8  циклус<BR>(F,G) = 11  циклус || {}
| Сега сите вертици се селектирани и [[минимално распространето дрво|минимално распространетото дрво]] е обоено зелено. Во овој случај тежината е 39.
|}

== Доказ за точност ==
Нека P е сврзан, тежински граф. На секоја итерација на Примовиот алгоритам, работ мора да биде поврзан со теме во подграф со теме надвор од подрафот. Штом P  поврзан, секогаш има пат до секое теме. Резултатот Y од Примовиот алгоритам е дрво бидејќу секој раб и теме додадени на дрвото Y се поврзани. Нека Y1 е минимално распространето дрво од графот P. Ако Y1 = Y тогаш Y е минимално распространето дрво. Инаку, нека е првиот раб додаден во конструкцијата кој не е во дрвото Y1, и V нека биде множесто од вертици кои се сврзани со рабови додадени пред работ Е. Тогаш еден крај на работ е во множестовото V, а другиот не е. Бидејќи Y1 не е распространето дрво на графот P,има пат во дрвото Y1 кој поврзува два краја. Додека некој се движи по патот, мора да сретне раб f кој поврзува теме во множеството V со теме коешто не е во множеството V. Сега, на итерацијата кога раот е додаден во дрвото Y,работ ‘f’, исто така може да се додаде и би бил додаден наместо работ e доколку тежи помалку од ‘е’ (знаеме дека сме имале можност да во земеме ‘f’ пред ‘e’ бидејќи ‘f’ е сврзан со  V и го посетивме секое теме на V пред темето со кое го поврзуваме ‘e’). Затоа што работ ‘f’ не е додаден, заклучуваме дека:

<math>w(f) \ge w(e).</math>

Нека дрвото Y2 е граф создаден со одземање на рабовите ‘f’ и додавање на работ ‘e’ во дрвото Y1. Лесно е да се покаже дека дрвото Y2 е сврзано, го има истиот број на рабови како дрвото Y1 и вкупната тежина на сите рабови не е поголем од тој на Y1, што значи дека исто така е и минимално распространето дрво на графот P и ги содржи рабовите ‘e’ и сите рабови додадени во текот на конструкцијата на множеството V. Повторувајќи ги претходните стапки ќе стигнеме до минималното распространето дрво на графот P што е идентично на дрвото Y. Овај Y покажува дека е минимално распространето дрво.

== Поврзано ==
* [[BFS]];
* [[DFS]];
* [[Dijkstra]].

== Наводи ==
{{наводи}}
* 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.&nbsp;57–63. (in Czech)
* R. C. Prim: ''Shortest connection networks and some generalizations''. In: ''Bell System Technical Journal'', 36 (1957), pp.&nbsp;1389–1401
* [[David Cheriton|D. Cheriton]] and [[Robert Tarjan|R. E. Tarjan]]: ''Finding minimum spanning trees''. In: ''[[SIAM Journal on Computing]]'', 5 (Dec. 1976), pp.&nbsp;724–741
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Third Edition. MIT Press, 2009. ISBN 0-262-03384-4. Section 23.2: The algorithms of Kruskal and Prim, pp.&nbsp;631&ndash;638.

== Надворешни врски ==
* [http://students.ceid.upatras.gr/~papagel/project/prim.htm Animated example of Prim's algorithm]
* [http://www.mincel.com/java/prim.html Prim's Algorithm (Java Applet)] {{Семарх|url=https://web.archive.org/web/20060712152157/http://www.mincel.com/java/prim.html |date=2006-07-12 }}
* [http://people.csail.mit.edu/rivest/programs.html Minimum spanning tree demonstration Python program by Ronald L. Rivest] {{Семарх|url=https://web.archive.org/web/20110809152732/http://people.csail.mit.edu/rivest/programs.html |date=2011-08-09 }}
* [http://code.google.com/p/annas/ Open Source Java Graph package with implementation of Prim's Algorithm]
* [http://code.google.com/p/ngenerics/ Open Source C# class library with implementation of Prim's Algorithm]

[[Категорија:Алгоритми]]