『壹』 普里姆演算法(Prime)
普利姆(Prim)演算法求最小生成樹，也就是在包含 n 個頂點的連通圖中，找出只有(n-1)條邊包含所有 n 個頂點的連通子圖，也就是所謂的極小連通子圖
普利姆的演算法如下:
1. 有七個站點 A,B,C,D,E,F,G，現在需要修線路把七個站點聯通
2. 各個站點的距離用邊線表示(權)，比如 A->C 為7公里
問： 如何修線路使各個站點都能聯通， 同時修的線路里程最短？
『貳』 普里姆演算法
你要先明白prim演算法的原理，明白原理後看下面的程序要點：
1.程序實現的時候將點分成兩部分，加入集合的和沒有加入集合的；
2.每次從沒有加入集合中找點；
3.對所有沒有加入到集合中的點中，找一個邊權最小的；
4.將邊權最小的點加入集合中，並且修改和加入點相連的沒有加入的點的權，重復第2步，知道所有的點都加入到集合中；
『叄』 用c語言描述prim演算法求最小生成樹.... 求高人指點啊，給出完整的代碼，那個鄰接矩陣是要要一次全部輸入的
#include <cstdio>
#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=102;
const int inf=1<<30;
int map[maxn][maxn];
int dis[maxn];
bool flag[maxn];
int a,b,c,n,m,ans;
void init()
{
memset(map,-1,sizeof(map));
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]==-1 || c< map[a][b])
{
map[a][b]=map[b][a]=c;
}
}
}
void prim()
{
memset(flag,false,sizeof(flag));
for(int i=1;i<=n;i++)dis[i]=inf;
dis[1]=0;
ans=0;
for(int j=1;j<=n;j++)
{
int now,value=inf;
for(int i=1;i<=n;i++)
{
if(flag[i]==false && dis[i]<value)
{
value=dis[i];
now=i;
}
}
if(value==inf)
{
cout << "-1" <<endl;
return;
}
flag[now]=true;
ans+=dis[now];
for(int i=1;i<=n;i++)
{
if(!flag[i] && map[now][i]!=-1 && dis[i]>map[now][i])
dis[i]=map[now][i];
}
}
cout << ans <<endl;
}
int main()
{
//'freopen("in.txt","r",stdin);
while(cin >> n >> m)
{
init();
prim();
}
return 0;
}
測試數據：
Sample Input
3 3
1 2 1
1 3 1
2 3 3
Sample Output
2
既然問到了prim演算法相信你能看懂測試數據是什麼意思~
『肆』 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;
}
『伍』 用普里姆演算法求最小生成樹（C++）
求最小生成樹的譜里姆演算法
#include <iostream>
using namespace std;
const int n=6;
const int e=10;
class edgeset
{public :
int front;
int end;
int weight;};
class tree
{public :
int s[n+1][n+1];
edgeset ct[n+1];
void prim(tree &t)
{
int i,j,k,min,t1,m,w;
for(i=1;i<n;i++)
{t.ct[i].front=1;
t.ct[i].end=i+1;
t.ct[i].weight=t.s[1][i+1];}
for(k=2;k<=n;k++)
{min=32767;
m=k-1;
for(j=k-1;j<n;j++)
if(t.ct[j].weight<min)
{min=t.ct[j].weight;
m=j;}
edgeset temp=t.ct[k-1];
t.ct[k-1]=t.ct[m];
t.ct[m]=temp;
j=t.ct[k-1].end;
for(i=k;i<n;i++)
{t1=t.ct[i].end;
w=t.s[j][t1];
if(w<t.ct[i].weight)
{t.ct[i].weight=w;
t.ct[i].front=j;}}}}
};
void main ()
{int j,w;tree t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)t.s[i][j]=0;
else t.s[i][j]=32767;
for(int k=1;k<=e;k++)
{cout<<"輸入一條邊及邊上的權值 ";
cin>>i>>j>>w;
cout<<endl;
t.s[i][j]=w;
t.s[j][i]=w;}
t.prim(t);
for(i=1;i<n;i++)
{cout<<t.ct[i].front<<" "<<t.ct[i].end<<" "<<t.ct[i].weight<<endl;}
}
我們的實驗上機做了的
運行結果
輸入一條邊及邊上的權值 1 2 6
輸入一條邊及邊上的權值 1 3 1
輸入一條邊及邊上的權值 1 4 6
輸入一條邊及邊上的權值 2 3 5
輸入一條邊及邊上的權值 2 5 3
輸入一條邊及邊上的權值 3 4 7
輸入一條邊及邊上的權值 3 5 5
輸入一條邊及邊上的權值 3 6 4
輸入一條邊及邊上的權值 4 6 2
輸入一條邊及邊上的權值 5 6 6
1 3 1
3 6 4
6 4 2
3 5 5
5 2 3
Press any key to continue
你有的圖不一樣就該頂點和邊就是
const int n=6;
const int e=10;
『陸』 用prim演算法求最小生成樹:c語言
把main函數改成：
main(){
GraphMatrix graph = {
"abcd",
{{7,8,Max,15},{12,100,6,20},{Max,100,4,13},{Max,4,8,10}},
};
Edge mst[Max];
int i,j;
prim(graph,mst);
for(j=0;j<Max;j++)
{
printf("%c\t",mst[j].stop_vex);
printf("%c\t",mst[j].start_vex);
printf("%d\n",mst[j].weight);
}
}
還有GraphMatrix結構體里的vexs數組最好定義為vexs[VN+1]給字元串末尾的『\0'留地方。
『柒』 普里姆演算法
測試結果:
610
123456
016
021
035
125
143
235
246
254
352
456
1---31
3---64
6---42
3---25
2---53
//圖最小生成樹Prim演算法
#include"stdio.h"
#include"stdlib.h"
#defineMAXVEX200
#defineINFINITY65535
typedefstruct
{
charvexs[MAXVEX];//頂點
intarc[MAXVEX][MAXVEX];//邊的權值
intnumVertexes;//頂點總數
intnumEdges;//邊的總數
}MGraph;
voidCreateMGraph(MGraph*G)/*構件圖*/
{
charstr[200];
intbeginVert,endVert,weight;
inti,j;
//輸入頂點總數,邊的總數
scanf("%d%d",&i,&j);
G->numVertexes=i;
G->numEdges=j;
//輸入頂點符號
scanf("%s",str);
for(i=0;i<G->numVertexes;i++)
{
G->vexs[i]=str[i];
}
for(i=0;i<G->numVertexes;i++)/*初始化圖*/
{
for(j=0;j<G->numVertexes;j++)
{
if(i==j)
{
G->arc[i][j]=0;
}
else
{
G->arc[i][j]=G->arc[j][i]=INFINITY;
}
}
}
//輸入所有邊的權值
for(i=0;i<G->numEdges;i++)
{
scanf("%d%d%d",&beginVert,&endVert,&weight);
G->arc[beginVert][endVert]=weight;
}
for(i=0;i<G->numVertexes;i++)
{
for(j=i;j<G->numVertexes;j++)
{
G->arc[j][i]=G->arc[i][j];
}
}
}
/*Prim演算法生成最小生成樹*/
voidMiniSpanTree_Prim(MGraphG)
{
intmin,i,j,k;
intadjvex[MAXVEX]; /*保存相關頂點下標*/
intlowcost[MAXVEX]; /*保存相關頂點間邊的權值*/
charbeginVert,endVert;
lowcost[0]=0;/*初始化第一個權值為0，即v0加入生成樹*/
/*lowcost的值為0，在這里就是此下標的頂點已經加入生成樹*/
adjvex[0]=0; /*初始化第一個頂點下標為0*/
for(i=1;i<G.numVertexes;i++) /*循環除下標為0外的全部頂點*/
{
lowcost[i]=G.arc[0][i]; /*將v0頂點與之有邊的權值存入數組*/
adjvex[i]=0; /*初始化都為v0的下標*/
}
for(i=1;i<G.numVertexes;i++)
{
min=INFINITY; /*初始化最小權值為∞，*/
/*通常設置為不可能的大數字如32767、65535等*/
j=1;k=0;
while(j<G.numVertexes) /*循環全部頂點*/
{
if(lowcost[j]!=0&&lowcost[j]<min)/*如果權值不為0且權值小於min*/
{
min=lowcost[j]; /*則讓當前權值成為最小值*/
k=j; /*將當前最小值的下標存入k*/
}
j++;
}
beginVert=G.vexs[adjvex[k]];
endVert=G.vexs[k];
//列印當前頂點邊中權值最小的邊
printf("%c---%c%d ",beginVert,endVert,min);
lowcost[k]=0;/*將當前頂點的權值設置為0,表示此頂點已經完成任務*/
for(j=1;j<G.numVertexes;j++) /*循環所有頂點*/
{
if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j])
{//如果下標為k頂點各邊權值小於此前這些頂點未被加入生成樹權值
lowcost[j]=G.arc[k][j];//將較小的權值存入lowcost相應位置
adjvex[j]=k; //將下標為k的頂點存入adjvex
}
}
}
}
intmain(void)
{
MGraphG;
CreateMGraph(&G);
MiniSpanTree_Prim(G);
return0;
}
『捌』 求一個學過數據結構（C語言版）的大神，有一個關於克魯斯卡爾演算法和普里姆演算法的問題！
克魯斯卡爾和prime演算法都是最小生成樹的貪心演算法，可以證明其擁有最優解結構。證明簡單的可以參考wiki，要嚴格證明請參考演算法導論和計算機程序設計的藝術中的相關內容。由於其相關論文比較久遠，我也不建議你去查了。