Prim算法和Dijkstra算法非常類似，他們的僞碼幾乎相近，隻是他們優先隊列所排序的鍵值不同而已。Prim算法的鍵值為節點與集合S中頂點間的最輕邊的權重，而在Dijkstra算法中，鍵值為由起始點到某節點的完整路徑長度。
在後面的部落格中會說明最小生成樹MST與最短路徑的差別。
#include<iostream>
#include<malloc.h>
#include<queue>
#include <algorithm>
#include<stdlib.h>
#include<functional>
using namespace std;
#define maxNum 100 //定義鄰接舉證的最大定點數
#define maxWeight 1000000 //邊權最大值
int cost[maxNum];//使用者存儲節點與最小生成樹MST之間的權重，初始狀态cost[i]=maxWeight
int prev_Elem[maxNum];//該數組使用者存儲結點的前序，比如prev[v]=u，則表示u是v的前序
int set[maxNum];//集合S，一開始為空，初始化的時候确定一個頂點，後續頂點都是通過prim算法找到的。set[i]=1表示頂點i屬于集合s
//頂點資訊
typedef struct
{
int id;//頂點編号
int cost;//用于儲存該頂點到MST的最小權值
}node;
//圖的鄰接矩陣表示結構
typedef struct
{
//char v[maxNum];//圖的頂點資訊
node v[maxNum];
int e[maxNum][maxNum];//圖的頂點資訊
int vNum;//頂點個數
int eNum;//邊的個數
}graph;
//函數聲明
void createGraph(graph *g);//建立圖g
void Prim(graph *g) ;//核心算法，是BFS的改版，隻是将普通隊列改成了優先隊列。
int cmp(node a,node b);//定義優先隊列以升序還是降序排列
int cmp(node a,node b)
return a.cost<b.cost;//升序
}
//prim算法
void Prim(graph *g)
{
node Q[maxNum]; //定義結構體數組
int front;//隊列頭
int rear;//隊列尾
int count;//隊列計數
front=rear=count=0;//表示隊列為空
int k,i,j;
//初始化cost的值
for(i=1;i<=g->vNum;i++)
{
g->v[i].cost=maxWeight; //cost為最大值
g->v[i].id=i;
prev_Elem[i]=-1;
set[i]=0;
}
g->v[1].cost=0;//1作為MST第一個頂點，初始化其cost為0
//初始化優先隊列
for(i=1;i<=g->vNum;i++)
{
Q[++rear]=g->v[i];
count++;//頂點進入隊列Q
while(count>0)//隊列不空 ，一直循環，也可是front<rear,也表示隊列不空，count=rear-front
{
sort(Q+front+1,Q+rear+1,cmp);//對隊列Q進行排序，按cost的升序排列。
//以下兩行是隊列的出隊操作
node n1=Q[++front]; //取出目前非s集合中離s距離最近的點
count--;//出隊列操作
k=n1.id;//
cout<<k<<endl;
set[k]=1;//将上述從隊列中取出的頂點加入到集合s中去
for(j=1;j<=g->vNum;j++)
{
if(g->e[k][j]!=maxWeight&&set[j]==0)//i->j之間有邊，并且頂點j不屬于集合s的時候
{
//如果頂點j到集合s的距離權值大于集合中一點k到j的距離，那麼更新(update)j點距離權值
//并令該j的前序為k
if((g->v[j].cost>g->e[k][j]))
//if((g->v[j].cost>g->e[k][j]))
{
g->v[j].cost=g->e[k][j];
prev_Elem[j]=k;
}
}
}
//更新隊列
for(i=1;i<=g->vNum;i++)
{
Q[i]=g->v[i];
}
cout<<"更新cost後各頂點的cost值"<<endl;
for(i=1;i<=g->vNum;i++)
cout<<g->v[i].cost<<" ";
cout<<endl;
}
void createGraph(graph *g)//建立圖g
cout<<"正在建立無向圖..."<<endl;
cout<<"請輸入頂點個數vNum:";
cin>>g->vNum;
int i,j;
//構造鄰接矩陣，頂點到自身的距離是無窮大的。
cout<<"輸入鄰接矩陣權值："<<endl;
for(i=1;i<=g->vNum;i++)
for(j=1;j<=g->vNum;j++)
cin>>g->e[i][j];
if(g->e[i][j]==0)
g->e[i][j]=maxWeight;
}
}
int main()
int i;
graph *g;
g=(graph*)malloc(sizeof(graph));
createGraph(g);
Prim(g);
//for(int k=1; k<=g->vNum; k++)
//{
// cout<<g->v[k].cost<<" ";
//}
/*cout<<endl;*/
cout<<"輸出MST的各條邊"<<endl;
//cout<<prev_Elem[i]<<" ";
if(prev_Elem[i]!=-1)
cout<<"存在邊："<<prev_Elem[i]<<"->"<<i<<"，權值為："<<g->e[prev_Elem[i]][i]<<endl;
}
//cout<<endl;
system("pause");
return 0;
/*
正在建立無向圖...
請輸入頂點個數vNum:6
輸入鄰接矩陣權值：
0 5 6 4 0 0
5 0 1 2 0 0
6 1 0 2 5 3
4 2 2 0 0 4
0 0 5 0 0 4
0 0 3 4 4 0
輸出MST的各條邊
存在邊：3->2，權值為：1
存在邊：4->3，權值為：2
存在邊：1->4，權值為：4
存在邊：6->5，權值為：4
存在邊：3->6，權值為：3
請按任意鍵繼續. . .
*/
簡而言之，kruskal是找邊的算法，prim算法是找點的算法。
3.1 kruskal算法基本思想：
kruskal算法每次選擇n-1條邊，所使用的貪婪準則是：從剩下的邊中選擇一條不會産生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若産生環路則不可能形成一棵生成樹。
kruskal算法分e 步，其中e 是網絡中邊的數目。按耗費（邊的權值）遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若将其加入到已選邊的集合中會出現環路，則将其抛棄，否則，将它選入。
3.2 Prim算法的基本思想是：
1) 在圖G=(V, E) （V表示頂點 ，E表示邊）中，從集合V中任取一個頂點（例如取頂點v0）放入集合 U中，這時 U={v0}，集合T(E)為空。
2) 從v0出發尋找與U中頂點相鄰（另一頂點在V中）權值最小的邊的另一頂點v1，并使v1加入U。即U={v0,v1 }，同時将該邊加入集合T(E)中。
3) 重複(2)，直到U = V為止。
這時T(E)中有n-1條邊，T = (U, T(E))就是一棵最小生成樹。
本文轉自xwdreamer部落格園部落格，原文連結：http://www.cnblogs.com/xwdreamer/archive/2011/06/16/2296997.html，如需轉載請自行聯系原作者
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)