Prims algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 juni 2020; kontroller kräver 11 redigeringar .

Prims algoritm är en algoritm för att konstruera det minsta spännträdet för en viktad sammankopplad oriktad graf. Algoritmen upptäcktes först 1930 av den tjeckiske matematikern Wojciech Jarnik , senare återupptäckt av Robert Prim 1957, och oberoende av E. Dijkstra 1959.

Beskrivning

Algoritmens ingång är en ansluten oriktad graf. För varje kant fastställs dess kostnad.

Först tas en godtycklig vertex och en kant hittas som är infallande till denna vertex och har den lägsta kostnaden. Den hittade kanten och de två hörnen som är förbundna med den bildar ett träd. Sedan betraktas grafens kanter, vars ena ände är en vertex som redan tillhör trädet, och den andra inte är det; från dessa kanter väljs kanten av lägsta kostnad. Den kant som väljs vid varje steg läggs till i trädet. Trädet växer tills alla hörn i den ursprungliga grafen är uttömda.

Resultatet av algoritmen är en minimikostnad som spänner över trädet.

Exempel

Uppsättningen av valda hörn U	Kant (u, v)	Uppsättningen av omarkerade hörn V \ U	Beskrivning
{}		{A,B,C,D,E,F,G}	Den ursprungliga viktade grafen. Siffrorna bredvid kanterna visar deras vikter, vilket kan ses som avstånden mellan hörnen.
{D}	(D,A) = 5V (D,B) = 9 (D,E) = 15 (D,F) = 6	{A,B,C,E,F,G}	Spetsen D är godtyckligt vald som den initiala . Var och en av hörnen A , B , E och F är ansluten till D med en enda kant. Vertex A är närmast D , och väljs som andra vertex tillsammans med kant AD .
{A,D}	(D,B) = 9 (D,E) = 15 (D,F) = 6V (A,B) = 7	{B,C,E,F,G}	Nästa hörn är den som ligger närmast någon av de valda D- eller A -punkten . B är 9 från D och 7 från A. Avståndet till E är 15 och till F är 6. F är närmaste vertex, så det ingår i trädet F tillsammans med kanten DF .
{A,D,F}	(D,B) = 9 (D,E) = 15 (A,B) = 7 V (F,E) = 8 (F,G) = 11	{B,C,E,G}	På samma sätt väljs vertex B , som är 7 från A.
{A,B,D,F}	(B,C) = 8 (B,E) = 7 V (D,B) = 9 loop (D,E) = 15 (F,E) = 8 (F,G) = 11	{C,E,G}	I detta fall är det möjligt att välja antingen C , eller E , eller G . C är 8 från B , E är 7 från B och G är 11 från F. E är närmaste vertex, så E och kant BE väljs .
{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 cykler (D,E) = 15 cykler (E,C) = 5 V (E,G) = 9 (F,E) = 8 cykler (F,G ) ) = 11	{C,G}	Endast hörn C och G är tillgängliga här . Avståndet från E till C är 5 och från G är 9. En vertex C och en kant EC väljs .
{A,B,C,D,E,F}	(B,C) = 8 loopar (D,B) = 9 loopar (D,E) = 15 loopar (E,G) = 9 V (F,E) = 8 loopar (F,G) = 11	{G}	Den enda kvarvarande vertexen är G . Avståndet från F till det är 11, från E - 9. E är närmare, så vertex G och kanten EG väljs .
{A,B,C,D,E,F,G}	(B,C) = 8 cykler (D,B) = 9 cykler (D,E) = 15 cykler (F,E) = 8 cykler (F,G) = 11 cykler	{}	Alla hörn är valda, det minsta spännträdet byggs (markerat i grönt). I det här fallet är dess vikt 39.

Implementering

Notation

$d[i]$ är avståndet från -th vertex till det konstruerade trädet $i$
$pi]$ är en förfader till -th vertex, det vill säga en vertex sådan att den lättaste av alla kanter förbinder i med en vertex från det konstruerade trädet. $i$ $u$ $(u,i)$
$w(i,j)$ - revbensvikt $(I j)$
$F$ är prioritetskön för grafens hörn, där nyckeln är $d[i]$
$T$ är uppsättningen av kanter för det minsta spännträdet

Pseudokod

T\får

{} För varje vertex Ännu inte tom

i\i V

d[i]\blir\infty

p[i]\får noll

d[1]\får 0

Q\får V

v\gets\Extract.Min(Q)

F

För varje vertex som gränsar till If och

u

v

u\i Q

w(v,u)<d[u]

d[u]\får w(v,u)

p[u]\får v

v\gets Extract.Min(Q)

T\får T+(p[v],v)

Betyg

Algoritmens asymptotik beror på hur grafen lagras och hur de hörn som inte ingår i trädet lagras. Om prioritetskön implementeras som en vanlig array , så tar det , och kostnaden för operationen är . Om representerar en binär pyramid , så minskar kostnaden till och kostnaden ökar till . När du använder Fibonacci-pyramider utförs operationen för , och för . $F$ $d$ $Extrahera.Min(Q)$ $På)$ $d[u]\får w(v,u)$ $O(1)$ $F$ $Extrahera.Min(Q)$ $O(\log n)$ $d[u]\får w(v,u)$ $O(\log n)$ $Extrahera.Min(Q)$ $O(\log n)$ $d[u]\får w(v,u)$ $O(1)$

Sätt att representera prioriterad kö och graf	Asymptotika
Array d, angränsande listor (angränsningsmatris)	$O(V^{2})$
Binär pyramid, angränsande listor	$O((V+E)\log V)=O(E\log V)$
Fibonacci pyramid, angränsande listor	$O(E+V\log V)$

Se även

Litteratur

V. Jarník: O jistém problému minimálním [Om ett visst minimalt problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, s. 57-63. (tjeckiska)
RC Prim: Kortaste anslutningsnätverk och några generaliseringar . I: Bell System Technical Journal , 36 (1957), s. 1389-1401 (engelska)
D. Cheriton och RE Tarjan : Hitta minsta spännande träd . I: SIAM Journal on Computing , 5 (dec. 1976), s. 724-741 _
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest och Clifford Stein . Introduktion till algoritmer , tredje upplagan. MIT Press, 2009. ISBN 0-262-03384-4 . Avsnitt 23.2: Algoritmerna för Kruskal och Prim, s. 631-638. (Engelsk)

Länkar

Beskrivning och implementering av Prims algoritm
DISKRET MATEMATIK: ALGORITHMER: Minsta spännande träd (länk ej tillgänglig) . Hämtad 7 juli 2009. Arkiverad från originalet 11 januari 2014. (obestämd)

Algoritmer för grafsökning
Oinformerade metoder	Dubbelriktad sökning Strålsökning Lexikografisk bredd första sökning Utöka första sökningen Sök efter kostnadskriterium Djup första sökning Backtracking sökning Sök genom att klättra till toppen Djupbegränsad sökning Djup-första sökning med iterativ fördjupning
Informerade metoder	Alfa beta-klippning Gren och bunden metod Sök efter första bästa matchning A* B* D* Att hitta en övergångspunkt IDA* Rekursiv sökning på den första bästa matchningen SMA*
Genvägar	Vågalgoritm Bellman-Ford algoritm Dijkstras algoritm Johnsons algoritm Levits algoritm Floyd-Warshall algoritm Kantsökning
Minsta spännträd	Boruvkas algoritm Prims algoritm Kruskals algoritm
Övrig	British Museum Algoritm Edmonds algoritm Trädpassering Algoritmen för närmaste granne i problemet med resande säljare