Prim algoritmusa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. június 15-én felülvizsgált verziótól ; az ellenőrzések 11 szerkesztést igényelnek .

A Prim algoritmusa egy súlyozott összekapcsolt irányítatlan gráf minimális feszítőfájának megalkotására szolgáló algoritmus . Az algoritmust először 1930-ban a cseh matematikus , Wojciech Jarnik fedezte fel , később Robert Prim 1957-ben, és ettől függetlenül E. Dijkstra 1959-ben.

Leírás

Az algoritmus bemenete egy összefüggő irányítatlan gráf. Minden élhez be van állítva a költsége.

Először egy tetszőleges csúcsot veszünk fel, és találunk egy élt, amely erre a csúcsra esik, és amelynek a legkisebb költsége van. A talált él és az általa összekapcsolt két csúcs egy fát alkot. Ezután a gráf azon éleit veszik figyelembe, amelyeknek az egyik vége egy már a fához tartozó csúcs, a másik pedig nem; ezek közül az élek közül a legkisebb költségű szél kerül kiválasztásra. Az egyes lépéseknél kiválasztott él hozzáadódik a fához. A fa addig nő, amíg az eredeti gráf összes csúcsa el nem fogy.

Az algoritmus eredménye egy minimális költségen átívelő fa.

Példa

A kiválasztott U csúcsok halmaza	Edge (u, v)	A ki nem választott csúcsok halmaza V \ U	Leírás
{}		{A,B,C,D,E,F,G}	Az eredeti súlyozott grafikon. Az élek melletti számok a súlyukat mutatják, amely a csúcsok közötti távolságnak tekinthető.
{D}	(D,A) = 5 V (D,B) = 9 (D,E) = 15 (D,F) = 6	{A,B,C,E,F,G}	A D csúcsot tetszőlegesen választottuk kiindulópontnak . Az A , B , E és F csúcsok mindegyike egyetlen élen keresztül kapcsolódik D -hez. Az A csúcs van a legközelebb D -hez, és az AD éllel együtt második csúcsként van kiválasztva .
{HIRDETÉS}	(D,B) = 9 (D,E) = 15 (D,F) = 6V (A,B) = 7	{B,C,E,F,G}	A következő csúcs az, amelyik a legközelebb van a kiválasztott D vagy A csúcsokhoz . B 9 távolságra van D -től és 7 távolságra A -tól. E távolsága 15, F -é pedig 6. F a legközelebbi csúcs, tehát benne van az F fában a DF éllel együtt .
{ADF}	(D,B) = 9 (D,E) = 15 (A,B) = 7 V (F,E) = 8 (F,G) = 11	{B,C,E,G}	Hasonlóképpen a B csúcsot választjuk, amely 7 távolságra van A -tól.
{A,B,D,F}	(B, C) = 8 (B, E) = 7 V (D, B) = 9 hurok (D, E) = 15 (F, E) = 8 (F, G) = 11	{C,E,G}	Ebben az esetben választhat C , vagy E , vagy G -t . C 8 távolságra van B -től , E 7 távolságra B -től, G pedig 11 -re van F -től. E a legközelebbi csúcs, ezért E -t és BE élt választunk .
{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 ciklus (D,E) = 15 ciklus (E,C) = 5 V (E,G) = 9 (F,E) = 8 ciklus (F,G ) ) = 11	{C,G}	Itt csak a C és G csúcsok érhetők el . A távolság E -től C -ig 5, G -től 9. Egy C csúcsot és egy EC élt választunk .
{A,B,C,D,E,F}	(B,C) = 8 hurok (D,B) = 9 hurok (D,E) = 15 hurok (E,G) = 9 V (F,E) = 8 hurok (F,G) = 11	{G}	Az egyetlen megmaradt csúcs a G. Az F -től a távolság 11, az E -től a 9 -ig. E közelebb van, tehát a G csúcs és az EG él van kiválasztva .
{A,B,C,D,E,F,G}	(B, C) = 8 ciklus (D, B) = 9 ciklus (D, E) = 15 ciklus (F, E) = 8 ciklus (F, G) = 11 ciklus	{}	Az összes csúcs ki van jelölve, a minimális feszítőfa megépül (zölddel kiemelve). Ebben az esetben a súlya 39.

Megvalósítás

Jelölés

$d[i]$ a -edik csúcs és a megépített fa távolsága $én$
$p[i]$ őse a -edik csúcsnak, vagyis olyan csúcsnak , amelyben a legkönnyebb az i-t a szerkesztett fa egyik csúcsával összekötő élek közül. $én$ $u$ ${\megjelenítési stílus (u,i)}$
$w(i,j)$ - borda súlya $(i,j)$
$K$ a gráf csúcsainak prioritási sora, ahol a kulcs van $d[i]$
$T$ a minimális feszítőfa éleinek halmaza

Pszeudokód

T\gets

{} Minden csúcshoz Még nem üres

i\in V

d[i]\gets\infty

p[i]\nullát kap

d[1]\0-t kap

Q: V-t kap

v\gets\Extract.Min(Q)

K

Az If és minden csúcsához

u

v

u\in Q

w(v,u)<d[u]

d[u]\w(v,u)

p[u]\gets v

v\gets Extract.Min(Q)

T\kapja a T+(p[v],v)

Értékelés

Az algoritmus aszimptotikája attól függ, hogy hogyan tároljuk a gráfot, és hogyan tároljuk azokat a csúcsokat, amelyek nem szerepelnek a fában. Ha a prioritási sor reguláris tömbként van implementálva , akkor ez tart , és a művelet költsége . Ha egy bináris piramist ábrázol , akkor a költség -ra csökken, a költség pedig -re nő . Fibonacci piramisok használatakor a műveletet a , és a számára hajtjuk végre . $K$ $d$ $Kivonat.Min(Q)$ $Tovább)$ $d[u]\w(v,u)$ $O(1)$ $K$ $Kivonat.Min(Q)$ $O(\log n)$ $d[u]\w(v,u)$ $O(\log n)$ $Kivonat.Min(Q)$ $O(\log n)$ $d[u]\w(v,u)$ $O(1)$

A prioritási sor és grafikon ábrázolásának módja	Aszimptotikumok
d tömb, szomszédsági listák (szomszédsági mátrix)	$O(V^{2})$
Bináris piramis, szomszédsági listák	$O((V+E)\log V)=O(E\log V)$
Fibonacci piramis, szomszédsági listák	$O(E+V\log V)$

Lásd még

Irodalom

V. Jarník: O jistém problému minimálním [Egy bizonyos minimális problémáról], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63. (Cseh)
RC Prim: A legrövidebb kapcsolati hálózatok és néhány általánosítás . In: Bell System Technical Journal , 36 (1957), pp. 1389-1401 (angol)
D. Cheriton és RE Tarjan : Minimális átnyúló fák keresése . In: SIAM Journal on Computing , 5 (1976. december), pp. 724-741_ _
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest és Clifford Stein . Bevezetés az algoritmusokba , harmadik kiadás. MIT Press, 2009. ISBN 0-262-03384-4 . 23.2. szakasz: Kruskal és Prim algoritmusai, pp. 631-638. (Angol)

Linkek

A Prim-algoritmus leírása és megvalósítása
DISZKRÉT MATEMATIKA: ALGORITMUSOK: Minimális feszítőfák (hivatkozás nem érhető el) . Letöltve: 2009. július 7. Az eredetiből archiválva : 2014. január 11.. (határozatlan)

Grafikon keresési algoritmusok
Tájékozatlan módszerek	Kétirányú keresés Sugárkeresés Lexikográfiai szélesség első keresés Szélesség első keresés Keresés költségkritérium szerint Mélységi első keresés Keresés visszafelé Keresés a csúcsra való mászás alapján Mélységben korlátozott keresés Mélység-első keresés iteratív elmélyítéssel
Tájékozott módszerek	Alfa béta vágás Elágazás és kötött módszer Keresés az első legjobb találat alapján A* B* D* Átmeneti pont keresése IDA* Rekurzív keresés az első legjobb találaton SMA*
Parancsikonok	Hullám algoritmus Bellman-Ford algoritmus Dijkstra algoritmusa Johnson algoritmus Levit algoritmusa Floyd-Warshall algoritmus Edge keresés
Minimálisan átívelő fa	Boruvka algoritmusa Prim algoritmusa Kruskal algoritmusa
Egyéb	British Museum algoritmus Edmonds algoritmus Fa bejárás Legközelebbi szomszéd algoritmus az utazó eladó problémájában