Prim算法
1.概覽
普裡姆算法（Prim算法），圖論中的一種算法，可在權重連通圖裡搜尋最小生成樹。意即由此算法搜尋到的邊子集所構成的樹中，不但包括了連通圖裡的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。該算法于1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；并在1957年由美國計算機科學家羅伯特·普裡姆（英語：Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該算法。是以，在某些場合，普裡姆算法又被稱為DJP算法、亞爾尼克算法或普裡姆－亞爾尼克算法。
2.算法簡單描述
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來描述所得到的最小生成樹。
下面對算法的圖例描述
| 圖例 | 說明 | 不可選 | 可選 | 已選（Vnew） |
|---|---|---|---|---|
 | 此為原始的權重連通圖。每條邊一側的數字代表其權值。 | - | ||
 | 頂點D被任意選為起始點。頂點A、B、E和F通過單條邊與D相連。A是距離D最近的頂點，是以将A及對應邊AD以高亮表示。 | C, G | A, B, E, F | D |
| | 下一個頂點為距離D或A最近的頂點。B距D為9，距A為7，E為15，F為6。是以，F距D或A最近，是以将頂點F與相應邊DF以高亮表示。 | B, E, F | A, D | |
| | 算法繼續重複上面的步驟。距離A為7的頂點B被高亮表示。 | C | B, E, G | A, D, F |
| | 在目前情況下，可以在C、E與G間進行選擇。C距B為8，E距B為7，G距F為11。E最近，是以将頂點E與相應邊BE高亮表示。 | 無 | C, E, G | A, D, F, B |
| | 這裡，可供選擇的頂點隻有C和G。C距E為5，G距E為9，故選取C，并與邊EC一同高亮表示。 | A, D, F, B, E | ||
| | 頂點G是唯一剩下的頂點，它距F為11，距E為9，E最近，故高亮表示G及相應邊EG。 | G | A, D, F, B, E, C | |
| | 現在，所有頂點均已被選取，圖中綠色部分即為連通圖的最小生成樹。在此例中，最小生成樹的權值之和為39。 | A, D, F, B, E, C, G |
3.簡單證明prim算法
反證法：假設prim生成的不是最小生成樹
1).設prim生成的樹為G0
2).假設存在Gmin使得cost(Gmin)<cost(G0) 則在Gmin中存在<u,v>不屬于G0
3).将<u,v>加入G0中可得一個環，且<u,v>不是該環的最長邊(這是因為<u,v>∈Gmin)
4).這與prim每次生成最短邊沖突
5).故假設不成立，命題得證.
4.算法代碼實作(未檢驗)
#define MAX 100000
#define VNUM 10+1 //這裡沒有ID為0的點,so id号範圍1~10
int edge[VNUM][VNUM]={/*輸入的鄰接矩陣*/};
int lowcost[VNUM]={0}; //記錄Vnew中每個點到V中鄰接點的最短邊
int addvnew[VNUM]; //标記某點是否加入Vnewint adjecent[VNUM]={0}; //記錄V中與Vnew最鄰近的點
void prim(int start)
{
int sumweight=0;
int i,j,k=0;
for(i=1;i<VNUM;i++) //頂點是從1開始
{
lowcost[i]=edge[start][i];
addvnew[i]=-1; //将所有點至于Vnew之外,V之内，這裡隻要對應的為-1，就表示在Vnew之外
}
addvnew[start]=0; //将起始點start加入Vnew
adjecent[start]=start;
for(i=1;i<VNUM-1;i++)
{
int min=MAX;
int v=-1;
for(j=1;j<VNUM;j++)
{
if(addvnew[j]!=-1&&lowcost[j]<min) //在Vnew之外尋找最短路徑
{
min=lowcost[j];
v=j;
}
}
if(v!=-1)
{
printf("%d %d %d\n",adjecent[v],v,lowcost[v]);
addvnew[v]=0; //将v加Vnew中
sumweight+=lowcost[v]; //計算路徑長度之和
for(j=1;j<VNUM;j++)
{
if(addvnew[j]==-1&&edge[v][j]<lowcost[j])
{
lowcost[j]=edge[v][j]; //此時v點加入Vnew 需要更新lowcost
adjecent[j]=v;
}
}
}
}
printf("the minmum weight is %d",sumweight);
} 5.時間複雜度
這裡記頂點數v，邊數e
鄰接矩陣:O(v2) 鄰接表:O(elog2v)
Kruskal算法
Kruskal算法是一種用來尋找最小生成樹的算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim算法和Boruvka算法等。三種算法都是貪婪算法的應用。和Boruvka算法不同的地方是，Kruskal算法在圖中存在相同權值的邊時也有效。
1).記Graph中有v個頂點，e個邊
2).建立圖Graphnew，Graphnew中擁有原圖中相同的e個頂點，但沒有邊
3).将原圖Graph中所有e個邊按權值從小到大排序
4).循環：從權值最小的邊開始周遊每條邊 直至圖Graph中所有的節點都在同一個連通分量中
if 這條邊連接配接的兩個節點于圖Graphnew中不在同一個連通分量中
添加這條邊到圖Graphnew中
圖例描述：
首先第一步，我們有一張圖Graph，有若幹點和邊
将所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這裡再次展現了貪心算法的思想。資源排序，對局部最優的資源進行選擇，排序完成後，我們率先選擇了邊AD。這樣我們的圖就變成了右圖
在剩下的變中尋找。我們找到了CE。這裡邊的權重也是5
依次類推我們找到了6,7,7，即DF，AB，BE。
下面繼續選擇， BC或者EF盡管現在長度為8的邊是最小的未選擇的邊。但是現在他們已經連通了（對于BC可以通過CE,EB來連接配接，類似的EF可以通過EB,BA,AD,DF來接連）。是以不需要選擇他們。類似的BD也已經連通了（這裡上圖的連通線用紅色表示了）。
最後就剩下EG和FG了。當然我們選擇了EG。最後成功的圖就是右：
3.簡單證明Kruskal算法
對圖的頂點數n做歸納，證明Kruskal算法對任意n階圖适用。
歸納基礎：
n=1，顯然能夠找到最小生成樹。
歸納過程：
假設Kruskal算法對n≤k階圖适用，那麼，在k+1階圖G中，我們把最短邊的兩個端點a和b做一個合并操作，即把u與v合為一個點v'，把原 來接在u和v的邊都接到v'上去，這樣就能夠得到一個k階圖G'(u,v的合并是k+1少一條邊)，G'最小生成樹T'可以用Kruskal算法得到。
我們證明T'+{<u,v>}是G的最小生成樹。
用反證法，如果T'+{<u,v>}不是最小生成樹，最小生成樹是T，即W(T)<W(T'+{<u,v>})。顯然T應該包含<u,v>，否則，可以用<u,v>加入到T中，形成一個環，删除環上原有的任意一條邊，形成一棵更小權值的生成樹。而T-{<u,v>}，是G'的生成樹。是以W(T-{<u,v>})<=W(T')，也就是W(T)<=W(T')+W(<u,v>)=W(T'+{<u,v>})，産生了沖突。于是假設不成立，T'+{<u,v>}是G的最小生成樹，Kruskal算法對k+1階圖也适用。
由數學歸納法，Kruskal算法得證。
typedef struct
{
char vertex[VertexNum]; //頂點表
int edges[VertexNum][VertexNum]; //鄰接矩陣,可看做邊表
int n,e; //圖中目前的頂點數和邊數
}MGraph;
typedef struct node
{
int u; //邊的起始頂點
int v; //邊的終止頂點
int w; //邊的權值
}Edge;
void kruskal(MGraph G)
{
int i,j,u1,v1,sn1,sn2,k;
int vset[VertexNum]; //輔助數組，判定兩個頂點是否連通
int E[EdgeNum]; //存放所有的邊
k=0; //E數組的下标從0開始
for (i=0;i<G.n;i++)
{
for (j=0;j<G.n;j++)
{
if (G.edges[i][j]!=0 && G.edges[i][j]!=INF)
{
E[k].u=i;
E[k].v=j;
E[k].w=G.edges[i][j];
k++;
}
}
}
heapsort(E,k,sizeof(E[0])); //堆排序，按權值從小到大排列
for (i=0;i<G.n;i++) //初始化輔助數組
{
vset[i]=i;
}
k=1; //生成的邊數，最後要剛好為總邊數
j=0; //E中的下标
while (k<G.n)
{
sn1=vset[E[j].u];
sn2=vset[E[j].v]; //得到兩頂點屬于的集合編号
if (sn1!=sn2) //不在同一集合編号内的話，把邊加入最小生成樹
{
printf("%d ---> %d, %d",E[j].u,E[j].v,E[j].w);
k++;
for (i=0;i<G.n;i++)
{
if (vset[i]==sn2)
{
vset[i]=sn1;
}
}
}
j++;
}
}