prim演算法模板

⑴ 請教prim演算法正確性的證明

為了減少不必要的麻煩，可以不妨設圖中所有邊的權重都不同，這樣最小生成樹是唯一的
然後直接用反證法就行了
如果Prim演算法得到G，而最小生成樹是T
設在生成G的過程中第一次產生的不在T中的邊是e，而在G中去掉e得到的兩個連通分支記為V1和V2，那麼e連接了V1和V2

把e加入T之後會出現環，在這個環裡面V1的頂點和V2的頂點至少還被另一條邊f連接（否則T本身就不連通了），由Prim演算法的貪心策略可知e比f權重低，那麼在T裡面把f換成e可得一個總權重更小的生成樹，與T的最小性矛盾

（因為最小生成樹的總權重的邊的權重的連續函數，對於有權重重復出現的情況可以利用連續性取極限，這樣即使最小生成樹不唯一仍然可以保證Prim演算法生成的樹具有最小權重）

⑵ Prim演算法的實現過程

貪心過程.
首先,把圖中的點分成兩種,已連通和未連通的,我把它們分別稱為"黑"和"白"點.
一開始時,圖中全是白點,沒有黑點.演算法的第一步,隨機選出一個白點,染成黑色.
然後開始一個重復的過程:
從當前圖的邊中尋找這樣的一些邊:它的其中一個端點是黑點,而另一個端點是一個白點. 我們可以把這類邊稱為"可擴展邊". 然後演算法需要從所有的可擴展邊之中選出權值最小的一條.把這條可擴展邊加入生成樹之中,且把這條邊的白色端點染成黑色.

重復這個過程,直到全部的節點都為黑色.

演算法可以優化的地方是,在選擇權值最小的可行邊時可以使用堆.

⑶ prim演算法是什麼

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

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

該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；並在1957年由美國計算機科學家羅伯特·普里姆（英語：Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆－亞爾尼克演算法。

通過鄰接矩陣圖表示的簡易實現中，找到所有最小權邊共需O（V）的運行時間。使用簡單的二叉堆與鄰接表來表示的話，普里姆演算法的運行時間則可縮減為O(ElogV)，其中E為連通圖的邊數，V為頂點數。如果使用較為復雜的斐波那契堆，則可將運行時間進一步縮短為O(E+VlogV)，這在連通圖足夠密集時（當E滿足Ω（VlogV）條件時），可較顯著地提高運行速度。

⑷ 誰能幫我畫個PRIM演算法的流程圖

對於這種比較高級的演算法代碼直接看程序會比較蒙，你就光看我的演算法流程吧，prim演算法用的是貪心演算法的思想，即每一步都作出局部的最優解，關於prim演算法為什麼能用貪心演算法的證明，你可以參考《計算機演算法設計與分析》這本書。（我反正不想看那麼無聊的證明，也看不明白，呵呵）。
定義一個集合v 和 a，其中v是全體節點（總節點數為n）的集合，v初始為空。定義一個記錄最小生成數邊數的變數c。
1.在v中任選一個節點，並加入到a中。在v中刪除該節點。

2.選一個在所有連接v集合和a集合權值最小的邊（即一個節點是v的某一個節點，一個是a中的某一個節點）

3。將兩個節點連接。將c加1

4.將第3步才在v中節點刪除並加入到a中.

5.如果c為n-1則完成最小生成樹，否則回到第2步。

明白了沒？不明白再問我啊，希望對你有所幫助。

⑸ Prim演算法的題怎麼做

按產生最小生成樹邊的次序
<2,4>, <2, 6>, <6, 1>, <1, 3>, <4, 5>

⑹ 用prim演算法從下面圖中的頂點1開始逐步構造最小代價生成樹

⑺ 數學建模用prim演算法求解最小樹模型時，怎樣構建模型

用 0-1規劃模型

⑻ prim演算法

指的是最小生成樹的一種演算法么，和dijstra演算法思想接近，
但是第一步是先將權最小的邊的兩個點加入以確定set。
然後一步步
從un set加入與這個集合距離最短的點,然後更新這個set到unset的每一點的最短距離，
直到全部加入

⑼ 數據結構（prim演算法）

開始時將v1加入U後，更新ee中的值應該是0 6 1 2 無窮 無窮；
將v3加入U後，更新ee中的值應該是0 5 0 2 6 4；
怎麼會出現你說的0 6 0 5 無窮無窮的情況呢？
for(j = 0;j < G.vexnum;j++)中不是有條件判斷么，要在k到j的距離小於ee[j]的value值時才會更新ee[j]啊。

⑽ Prim演算法c語言表示，求源程序。。。。。。。。。

我原來自己寫的模板

//樸素prim演算法
//復雜度 O(n^2)
//flag[SIZE] 頂點標記
//mindis[SIZE] 當前最短距離
//dis[SIZE][SIZE] 任意兩點間距離 鄰接矩陣表示

int prim()
{
memset(flag,false,sizeof(bool)*(n+1));
flag[0] = true;
for(int i=1;i<n;i++)
mindis[i] = dis[0][i];
int ans = 0;
for(int i=1;i<n;i++)
{
int min = 10000;
int pos;
for(int j=1;j<n;j++)
{
if(!flag[j] && min > mindis[j])
{
min = mindis[j];
pos = j;
}
}
ans+=min;
flag[pos] = true;
for(int j=1;j<n;j++)
{
if(!flag[j] && mindis[j] > dis[pos][j])
mindis[j] = dis[pos][j];
}
}
return ans;
}