『壹』 prim演算法不是很理解啊
其實它就是一個貪心
不知道你學過dijkstra沒有，這兩個是很類似的（代碼上也是，樸素實現好象就差1句）。
如果點A是未加入樹中最近的那個點，那麼我們貪心地加入A肯定是最優的！
假設B是任意一個未加入樹中不是最近的點，而我們這次加入了B。
那麼接下來可能有兩種情況再加入A：
1、直接加入A，這跟我們直接加入A是一樣的，但我們不能保證當時加入B是最優的。
2、用B更新邊後加入A，但是A比B要離樹近，所以之前加入A，再用A更新B然後加入B要比這種情況更優。
綜上，我們每次加入A總是最優的！
所以prim是對的。
『貳』 Prim演算法，求大牛通俗易懂地解釋下為什麼成立。。。
prim演算法就是把點分成兩個集合，一個集合裡麵包含已經加入生成樹的點，另一個包含未加入的，然後不斷在兩個集合之間找最短的邊，直到所有的點都加入到生成樹中，這時候就構成了最小生成樹。
『叄』 KRUSKAL演算法和PRIM演算法
不是吧，網路白科裡面有這倆個演算法的詳細的講解，你可以去查查
『肆』 利用Prim（普里姆）演算法 構造最小生成樹 程序
演算法同樣是解決最小生成樹的問題。
其演算法為：在這n個點中的相通的邊進行排序，然後不斷地將邊添加到集合中（體現了貪心的演算法特點），在並入集合之前，必須檢查一下這兩點是不是在一個集合當中，這就用到了並查集的知識。直到邊的集合達到了n-1個。
與prim演算法的不同：prim演算法為單源不斷尋找連接的最短邊，向外擴展，即單樹形成森林。而Kruskal演算法則是不斷尋找最短邊然後不斷將集合合並，即多樹形成森林。
復雜度的不同：prim演算法的復雜度是O(n^2),其中n為點的個數。Kruskal演算法的復雜度是O(e*loge)，其中e為邊的個數。兩者各有優劣，在不同的情況下選擇不同的演算法。
Prim演算法用於求無向圖的最小生成樹
設圖G =（V，E），其生成樹的頂點集合為U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。
③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。
其演算法的時間復雜度為O(n^2)
Prim演算法實現：
（1）集合：設置一個數組set(i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）
（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
{先選定一個點，然後從該點出發，與該點相連的點取權值最小者歸入集合，然後再比較在集合中的兩點與其它各點的邊的權值最小者，再次進入集合，一直到將所有的點都歸入集合為止。}
『伍』 prim演算法是基於什麼原理
貪心
具體證明可以看《演算法導論》最小生成樹那章
『陸』 什麼是Prim演算法
Prim演算法
Prim演算法用於求無向圖的最小生成樹
設圖G =（V，E），其生成樹的頂點集合為U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。
③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。
其演算法的時間復雜度為O(n^2)
Prim演算法實現：
（1）集合：設置一個數組set[i](i=0,1,..,n-1),初始值為 0,代表對應頂點不在集合中（注意：頂點號與下標號差1）
（2）圖用鄰接陣表示，路徑不通用無窮大表示，在計算機中可用一個大整數代替。
參考程序
/* Prim.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
/* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */
#include "stdio.h"
#define maxver 10
#define maxright 100
int main()
{
int G[maxver][maxver],in[maxver]=,path[maxver][2];
int i,j,k,min=maxright;
int v1,v2,num,temp,status=0,start=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if(num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for(j=0;j<num;j++)
for(k=0;k<num;k++)
{
if(j==k)
G[j][k]=maxright;
else
if(j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
scanf("%d",&temp);
if(temp>=maxright||temp<-1)
{
printf("Invalid input!\n");
goto re;
}
if(temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
}
}
for(j=0;j<num;j++)
{
status=0;
for(k=0;k<num;k++)
if(G[j][k]<maxright)
{
status=1;
break;
}
if(status==0)
break;
}
do
{
printf("Please enter the vertex where Prim algorithm starts:");
scanf("%d",&start);
}while(start<0||start>num);
in[start-1]=1;
for(i=0;i<num-1&&status;i++)
{
for(j=0;j<num;j++)
for(k=0;k<num;k++)
if(G[j][k]<min&&in[j]&&(!in[k]))
{
v1=j;
v2=k;
min=G[j][k];
}
if(!in[v2])
{
path[i][0]=v1;
path[i][1]=v2;
in[v1]=1;
in[v2]=1;
min=maxright;
}
}
if(!status)
printf("We cannot deal with it because the graph is not connected!\n");
else
{
for(i=0;i<num-1;i++)
printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+1);
}
return 1;
}
Prim演算法。
設圖G =（V，E），其生成樹的頂點集合為U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。
③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。
其演算法的時間復雜度為O(n^2)
參考程序
//Prim 演算法 讀入頂點數(n)、邊數(m)，邊的起始點和權值 用鄰接矩陣儲存
//例如
//7 12 (7個頂點12條邊)
//1 2 2
//1 4 1
//1 3 4
//2 4 3
//2 5 10
//3 4 2
//4 5 7
//3 6 5
//4 6 8
//4 7 4
//5 7 6
//6 7 1
#include <stdio.h>
#include <string.h>
int main()
{
int m , n;
int a[201][201] , mark[201] , pre[201] , dist[201];
int s , t , w;
int i , j , k , min , tot;
freopen("Prim.txt" , "r" , stdin);
//讀入數據
memset(a , 0 , sizeof(a));
scanf("%d %d" , &n , &m);
for (i = 0; i < m; i ++)
{
scanf("%d %d %d" , &s , &t , &w);
a[s][t] = w; a[t][s] = w;
}
//賦初值
memset(mark , 0 , sizeof(mark));
memset(pre , 0 , sizeof(pre));
memset(dist , 9999 , sizeof(dist));
dist[1] = 0;
//Prim
for (i = 1; i <= n; i ++)
{
min = 9999; k = 0;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (dist[j] < min)) {min = dist[j]; k = j;}
if (k == 0) break;
mark[k] = 1;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (a[k][j] < dist[j]) && (a[k][j] > 0))
{
dist[j] = a[k][j];
pre[j] = k;
}
}
tot = 0;
for (i = 1; i <= n; i ++) tot += dist[i];
printf("%d\n" , tot);
return 0;
}
『柒』 Prim演算法，解釋一步就好！
到C時可以得到的結果是：到2的最短長度為5，到5的最短長度為6，所以選最小的那個長度為5，即選擇下一個連接節點為2，即得到了D圖
『捌』 根據PRIM演算法構造最小生成樹怎麼確定出發點
用pascal語言的，可以轉成C++很容易的
首先定義數據類型:
type adjmatrix=array [1．.n,1..n] of real;
//定義一個n＊n的矩陣類型adjmatrix,以便存儲鄰接矩陣//
edge=record
beg,en:1..n;
length:real;
end;
//定義邊的存儲結構為edge,其中beg是邊的起點, en 是邊的終點,length是邊的權值//
treetype=array [1..n－1] of edge;
//定義一個基類型為edge的數組類型 treetype,其元素個數為n－1個//
var net:adjmatrix;
//定義一個adjmatrix類型的變數net,圖的鄰接矩陣就存放在net中//
tree:treetype;
//定義一個treetype類型的變數tree,tree中可以存放n－1條邊的信息，包括起點、終點及權值。在演算法結束後，最小生成樹的n－1 條邊就存放在tree中//
演算法如下(設n為構造的出發點)：
procere prim(net:adjmatrix;var tree:treetype);
//過程首部.參數的含義是:值參數net傳遞圖的鄰接矩陣,變參tree指明最小生成樹的存放地址//
begin
for v:=1 to n－1 do
//此循環將頂點n與圖中其它n－1個頂點形成的n－1條邊存放在變數tree中//
[tree[v].beg:=n;
tree[v].en:=v;
tree[v].length:=net[v]]
for k:=1 to n－1 do
//此循環執行演算法思想中的步驟2,循環體每執行一次,TE中將增加一條邊,在演算法中,這條增加的邊存放在變數tree中的第k個元素上,可以這樣認為,tree中從第1到第k號元素中存放了TE和U的信息。注意:在演算法思想中我們特別提醒了TE和U的動態性,表現在演算法中,這種動態性 體現在循環變數k的變化上。//
[min:=tree[k].length;
for j:=k to n－1 do
if tree[j].length<min then
[min:=tree[j].length;
m:=j;]
//上面兩條語句用於搜索權值最小的邊//
v:=tree[m].en;
//此語句記錄剛加入TE中的邊的終點,也即即將加入U中的頂點//
edge:=tree[m];
tree[m]:=tree[k];
tree[k]:=edge;
//上面三句用於將剛找到的邊存儲到變數tree的第k號元素上//
for j:=k＋1 to n－1 do
//此循環用於更新tree中第k＋1到第n－1號元素。更新以後這些元素中的en子項是各不相同的,它們的全部就是集合V－U;beg子項則可以相同,但它們需滿足兩個條件:一是應屬於集合U;另一是beg子項和en子項行成的邊,在所有與頂點en聯系的邊中權值應最小。//
[d:=net[v.tree[j].en];
if d<tree[j].length
then [tree[j].length:=d;
tree[j].beg:=v;]
]
]
for j:=1 to n－1 do
//此循環用於輸出最小生成樹//
writeln(tree[j].beg,tree[j].en,tree[j].length);
end;
『玖』 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。
『拾』 數據結構（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]啊。