‘壹’ 普里姆算法(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，要严格证明请参考算法导论和计算机程序设计的艺术中的相关内容。由于其相关论文比较久远，我也不建议你去查了。