普里姆演算法的簡述

㈠ prim演算法是什麼

prim演算法是圖論中的一種演算法。

普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。

簡介

最小生成樹是數據結構中圖的一種重要應用，它的要求是從一個帶權無向完全圖中選擇n－1條邊並使這個圖仍然連通（也即得到了一棵生成樹）,同時還要考慮使樹的權最小。

為了得到最小生成樹，人們設計了很多演算法，最著名的有prim演算法和kruskal演算法。教材中介紹了prim演算法，但是講得不夠詳細，理解起來比較困難，為了幫助大家更好的理解這一演算法，本文對書中的內容作了進一步的細化，希望能對大家有所幫助。

㈡ 普里姆演算法

可以這么理解：因為最小生成樹是包含所有頂點的所以開始lowcost先儲存到第一個點的所有值，然後執行下面演算法，找到最小值並記錄是第幾個點，比如說這個點是3，這樣有了一條1-3得道路已經確定，現在從3出發找從3出發到其他頂點的路徑，如果這個從3出發到達的路徑長度比從1出發的短，則更新lowcost，這樣使得lowcost保存一直到達該頂點的最短路徑。比如1-4是5，3-4是4，則lowcost從原來的5被改為4。

㈢ 什麼是普里姆演算法

構造最小生成樹用的，使用貪心策 略。prime演算法的基本思想 1.清空生成樹，任取一個頂點加入 生成樹 2.在那些一個端點在生成樹里，另 一個端點不在生成樹里的邊中，選 取一條權最小的邊，將它和另一個 端點加進生成樹 3.重復步驟2，直到所有的頂點都 進入了生成樹為止，此時的生成樹 就是最小生成樹

㈣ 普里姆演算法(Prime)

普利姆(Prim)演算法求最小生成樹，也就是在包含 n 個頂點的連通圖中，找出只有(n-1)條邊包含所有 n 個頂點的連通子圖，也就是所謂的極小連通子圖

普利坦鬧仔姆的演算法如下:

1. 有七個站點 A,B,C,D,E,F,G，現在需要修線路把彎嘩七個站點聯通

2. 各個站點的距離用邊線表示(權)，比如 A->C 為7公里

問： 如讓汪何修線路使各個站點都能聯通， 同時修的線路里程最短？

㈤ 普里姆演算法是什麼

在計算機科學中，普里姆(也稱為Jarník's)演算法是一種貪婪演算法，它為加權的無向圖找到一個最小生成樹 。

相關簡介：

這意味著它找到邊的一個子集，能夠形成了一個包括所有頂點的樹，其中在樹中所有邊的權重總和最小。該演算法通過從任意起始頂點開始一次給樹增加一個頂點來操作，在每個步驟中添加從樹到另一個頂點的花費最小的可能的連接。

該演算法由捷克數學家沃伊茨奇·賈尼克於1930年開發後，後來在1957年被計算機科學家羅伯特·普里姆，以及在1959年被艾茲赫爾·戴克斯特拉重新發現和重新出版。因此，它有時也被稱為Jarník演算法,普里姆-jarník演算法。普里姆-迪克斯特拉演算法或者DJP演算法。

這個問題的其他眾所周知的演算法包括克魯斯卡爾演算法和 Borvka's演算法。這些演算法在一個可能的非連通圖中找到最小生成森林；相比之下，普里姆演算法最基本的形式只能在連通圖中找到最小生成樹。然而，為圖中的每個連通分量單獨運行普里姆演算法，也可以用於找到最小生成森林。

就漸近時間復雜度而言，這三種演算法對於稀疏圖來說速度相同，但比其他更復雜的演算法慢。然而，對於足夠密集的圖，普里姆演算法可以在線性時間內運行，滿足或改進其他演算法的時間限制。

㈥ 簡述最小生成樹的Prime演算法的思想

因該是prim演算法
假設V是圖中頂點的集合,E是圖中邊的集合,TE為最小生成樹中的邊的集合,則prim演算法通過以下步驟可以得到最小生信含寬成樹:
1:初始化:U={u 0},TE={f}.此步驟設立一個只有結點u 0的結點集U和一個空的邊集TE作為最小生成樹的初始形態,在隨後的演算法執行中,這個形態會不斷的發生變化,直到得到最小生成樹為止.
2:在所有u∈U,v∈V－U的邊(u,v)∈E中,找一條權最小的邊(u 0,v 0),將此邊加進集合TE中,並將此邊的非U中頂點加入U中.此步驟的功能是在邊集E中找一條邊,要求這條邊滿足以下條件:首先邊的兩個頂點要分別在頂點集合U和V－U中,其次邊的權要最小.找到這條邊以後,把這條邊放到邊集TE中,並把這條邊上不在U中的那個頂點加入到U中.這一步驟在演算法中應執行多次,每執行一次,集合TE和U都將發生變化,分別增加一條邊和一個頂點滑亮,因此,TE和U是兩個動態的集合,這一點在理解演算法時要密切注意.
3:如果U=V,則演算法結束;否則重復步驟2.可以把本步驟看成循環終止條件.我們可以算出當U=V時,步驟2共執行了n－1次(設n為圖中頂點的數目),TE中也增加了n－1條邊,這n－1條邊就是需要求出老粗的最小生成樹的邊.

㈦ 普里姆演算法和克魯斯卡爾演算法區別

普里姆演算法和克魯斯卡爾演算法區別如下：
克魯斯卡爾演算法：是在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構埋或成迴路，則放棄，選晌液宴取次小邊。
普里姆演算法：同樣是在未選取的邊中尋找最小邊，但是選取的原則多了宴銀一條，就是該邊必須和已選取的邊相連，比如，如果邊(1, 2)已被選取，那麼接下來選取的邊，必須是和頂點1，或者頂點2相連的。

㈧ prim演算法 復雜度

普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點，且其所有邊的權值之和亦為最小。該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克發現；並在1957年由美國計算機科學家羅伯特·普里姆獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆－亞爾尼克演算法。
演算法簡單描述
1).輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；
2).初始化：Vnew = {x}，其中x為集合V中的任一節點（起始點），Enew = {},為空；
3).重復下列操作，直到Vnew = V：
a.在集合E中選取權值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，並且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；
b.將v加入集合Vnew中，將<u, v>邊加入集合Enew中；
4).輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。
時間復雜度
這里記頂點數v，邊數e
鄰接矩陣:O(v2) 鄰接表:O(elog2v)

㈨ Prim演算法的實現過程

G=（V,E）
①初始化：讀入的數據用鄰接矩陣x存儲，一個一維布爾型數組chosen，記錄第i個節點是否已選，初始值除1外全部設為false，記錄權值的變數cost賦值為0；
以下②到④循環執行v-1次（每次生成一條邊，運行（點的個數減1）次後，生成一棵最小生成樹）：
②臨時變數p賦值為無限大，用於記錄當前最小值；
③二重循環（外循環i，內循環j）掃描鄰接矩陣：如果chosen[i]=true（也就是說第i個點已選），那麼掃描x[i]，如果not(chosen[j])（也就是說第j個點未選），那麼如果x[i,j]<p，那麼p賦值為x[i,j],臨時變數q賦值為j;
④把cost賦值為cost+o，把chosen[q]賦值為true（也就是說第j個點已選）；
⑤輸出cost。

一、以上給出具體的運行過程。這個演算法的策略就是貪心，和dijkstra差不多，每次都選擇未選的邊中權值最小的那一條，直到生成最小生成樹。用chosen的目的就是保證生成過程中沒有環出現，也就是說保證選擇的邊不會通向一個已經包含在生成樹中的點。
二、這個只輸出最小生成樹的每條邊權值之和，如果要輸出整棵最小生成樹，加一個[1..n,1..2]的數組，在第④步的時候把每次選的邊記錄下來就可以了。
三、用小頂堆在第③步優化一下的話就不用每次都掃描那麼多邊了，只不過建堆維護堆代碼寫起來很麻煩。
四、prim適合用於比較稠密的網，點數和邊數差不多的時候效率很惡心，一般都用kruskal。

㈩ 普里姆演算法的相關信息

1）演算法的基本思想：
普里姆演算法的基本思想：普里姆演算法是另一種構造最小生成樹的演算法，它是按逐個將頂點連通的方式來構造最小生成樹的。
從連通網路N = { V, E }中的某一頂點u0出發，選擇與它關聯的具有最小權值的邊(u0, v)，將其頂點加入到生成樹的頂點集合U中。以後每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權值最小的邊(u, v),把該邊加入到生成樹的邊集TE中，把它的頂點加入到集合U中。如此重復執行，直到網路中的所有頂點都加入到生成樹頂點集合U中為止。
假設G=(V，E)是一個具有n個頂點的帶權無向連通圖，T(U，TE)是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，則構造G的最小生成樹T的步驟如下：
（1）初始狀態，TE為空，U={v0}，v0∈V；
（2）在所有u∈U，v∈V-U的邊(u，v)∈E中找一條代價最小的邊(u′，v′)並入TE，同時將v′並入U；
重復執行步驟（2）n-1次，直到U=V為止。
在普里姆演算法中，為了便於在集合U和(V-U)之間選取權值最小的邊，需要設置兩個輔助數組closest和lowcost，分別用於存放頂點的序號和邊的權值。對於每一個頂點v∈V-U，closest[v]為U中距離v最近的一個鄰接點，即邊(v，closest[v])是在所有與頂點v相鄰、且其另一頂點j∈U的邊中具有最小權值的邊，其最小權值為lowcost[v]，即lowcost[v]=cost[v][closest[v]]，採用鄰接表作為存儲結構：
設置一個輔助數組closedge[]：
lowcost域存放生成樹頂點集合內頂點到生成樹外各頂點的各邊上的當前最小權值；
adjvex域記錄生成樹頂點集合外各頂點距離集合內哪個頂點最近(即權值最小)。
應用Prim演算法構造最小生成樹的過程: