普里木演算法

⑴ 普里姆演算法

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

⑵ 關於prim演算法的時間復雜度

Prim演算法的時間復雜度與網中的邊數無關，適合於稠密圖。

通過鄰接矩陣圖表示的簡易實現中，找到所有最小權邊共需O（V）的運行時間。使用簡單的二叉堆與鄰接表來表示的話，普里姆演算法的運行時間則可縮減為O(ElogV)，其中E為連通圖的邊數，V為頂點數。

如果使用較為復雜的斐波那契堆，則可將運行時間進一步縮短為O(E+VlogV)，這在連通圖足夠密集時（當E滿足Ω（VlogV）條件時），可較顯著地提高運行速度。

(2)普里木演算法擴展閱讀：

演算法描述：

1、輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；

2、初始化：Vnew= {x}，其中x為集合V中的任一節點（起始點），Enew= {},為空；

3、重復下列操作，直到Vnew= V：

在集合E中選取權值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，並且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；

將v加入集合Vnew中，將<u, v>邊加入集合Enew中；

4、輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。

⑶ 最小生成樹 普里姆演算法有問

普里姆演算法構造最小生成樹演算法的思想是：選擇一個結點，然後從這個結點開始，選擇權值最小的邊，用一條邊連接，然後再以前面的那個結點開始，和你連接的那個結點作為根節點，再選擇權值最小的邊進行連接。
對權值給出解釋：以上圖為例，權值就是你第一個圖那幾條邊（弧）上，所標的數字。
對樓主所提出的問題：並不是連接那圓圈中最小的圓圈，如果沒錯的話，那圓圈中的數字表示的是V1---V6六個頂點，並不是代表數字，以3和6為頂點，找權值最小邊，顯然6——4為最小，即權值為2，頂點364相連接的時候各以364為頂點尋找最小邊，應該先從6連接到2，那麼現在加入頂點的為3642頂點，現在以3642為頂點尋找最小邊，應該從2連接到1，現在被連接的有63421，在以63421為頂點尋找最小邊
出現了問題：如果以5為權值的話，無論從2連接到4還是從3連接到4都出現了環，當然我們知道數中是不能出現環的，所以尋找次小的，剩餘5與13之間權值最小為13.所以將1連接5，即得到最小生成樹。
樓主可以按照我說的在紙上畫一下試試
從6連接到3因為有前提條件：從頂點V3開始用普里姆方法求其最小生成數，可見是從頂點3連接到6，而不是從6連接到3
希望可以解決樓主的疑惑，謝謝！

⑷ 什麼是普利姆演算法

Prim演算法：是圖的最小生成樹的一種構造演算法。

假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，TV 是 WN 上最小生成樹中頂點的集合，TE 是最小生成樹中邊的集合。顯然，在演算法執行結束時，TV=V，而 TE 是 E 的一個子集。在演算法開始執行時，TE 為空集，TV 中只有一個頂點，因此，按普里姆演算法構造最小生成樹的過程為：在所有「其一個頂點已經落在生成樹上，而另一個頂點尚未落在生成樹上」的邊中取一條權值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。

如果看不懂還可以找一本數據結構的書看，這個演算法挺簡單的。

btw：其實你有空問，應該有空網路啊~網路就有了。懶得寫，我還是直接從網路過來的~

⑸ 普里姆演算法是什麼

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

相關簡介：

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

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

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

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

⑹ 普里姆演算法的普里姆演算法的實現

為了便於在兩個頂點集U和V-U之間選擇權最小的邊，建立了兩個輔助數組closest和lowcost，它們記錄從U到V-U具有最小權值的邊，對於某個j∈V-U，closest[j]存儲該邊依附的在U中的頂點編號，lowcost[j]存儲該邊的權值。
為了方便，假設圖G採用鄰接矩陣g存儲，對應的Prim(g,v)演算法如下：
void Prim(MatGraph g,int v) //輸出求得的最小生樹的所有邊
{ int lowcost[MAXVEX]; //建立數組lowcost
int closest[MAXVEX]; //建立數組closest
int min,i,j,k;
for (i=0;i<g.n;i++) //給lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //構造n-1條邊
{ min=INF; k=-1;
for (j=0;j<g.n;j++) //在(V-U)中找出離U最近的頂點k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k為最近頂點的編號
}
printf( 邊(%d,%d),權值為%d ,closest[k],k,min);
lowcost[k]=0; //標記k已經加入U
for (j=0;j<g.n;j++) //修正數組lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
普里姆演算法中有兩重for循環，所以時間復雜度為O(n2)，其中n為圖的頂點個數。由於與e無關，所以普里姆演算法特別適合於稠密圖求最小生成樹。

⑺ 利用普里姆演算法求解最小生成樹，寫出步驟或畫圖表示過程。

<1,6>邊長度未知，這里看成無窮大。
歷次循環中，選擇兩端點分別在U，V中的邊中長度最小者，
具體如下：
1. 將1加入U中，其餘點加入V中。
2. 選擇邊<1,7>，將7加入U中，從V中除去該點。
3. 選擇邊<7,6>，將6加入U中，從V中除去該點。
4. 選擇邊<1,2>，將2加入U中，從V中除去該點。
5. 選擇邊<2,3>，將3加入U中，從V中除去該點。
6. 選擇邊<2,4>，將4加入U中，從V中除去該點。
7. 選擇邊<2,5>，將5加入U中，從V中除去該點。
結束。由上述六條邊組成的樹為求得的最小生成樹。

⑻ prim演算法是什麼

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

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

簡介

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

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

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

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

⑽ 普里姆演算法的相關概念

1）生成樹一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-1條邊。生成樹是對連通圖而言的，是連通圖的極小連通子圖，包含圖中的所有頂點，有且僅有n-1條邊。非連通圖的生成樹則組成一個生成森林；若圖中有n個頂點，m個連通分量，則生成森林中有n-m條邊。
2）和樹的遍歷相似，若從圖中某頂點出發訪遍圖中每個頂點，且每個頂點僅訪問一次，此過程稱為圖的遍歷，(Traversing Graph)。圖的遍歷演算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等演算法的基礎。圖的遍歷順序有兩種：深度優先搜索（DFS）和廣度優先搜索（BFS）。對每種搜索順序，訪問各頂點的順序也不是唯一的。
3）在一個無向連通圖G中，其所有頂點和遍歷該圖經過的所有邊所構成的子圖G′稱做圖G的生成樹。一個圖可以有多個生成樹，從不同的頂點出發，採用不同的遍歷順序，遍歷時所經過的邊也就不同。
在圖論中，常常將樹定義為一個無迴路連通圖。對於一個帶權的無向連通圖，其每個生成樹所有邊上的權值之和可能不同，我們把所有邊上權值之和最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹有很多實際應用。例如，通訊線路鋪設造價最優問題就是一個最小生成樹問題。常見的求最小生成樹的方法有兩種：克魯斯卡爾(Kruskal)演算法和普里姆（Prim）演算法。