#include<stdio.h>// 用prim算法构造五项连通图网的最小生成树
#define maxcost 1000
int gm[50][50];
void prim(int tree[],int cost[],int n)
{//从序号为0的顶点出发,建立连通网的最小生成树,二维数组gm[][]是其邻接矩阵
//顶点编号依次为0......n-1,建立的最小生成树存于数组tree中,对应的边值在cost中
int flag[50]={0};//标记数组,用于记录点是否加入到U中
int i,j,k,mincost;
for(i=0;i<n;i++)
{
cost[i]=gm[0][i];//从存储序号为0的顶点出发生成最小生成树
tree[i]=0;
}
// tree[0]=-1;
flag[0]=1;//顶点0进入U
for(i=1;i<n;i++)
{
mincost=maxcost;
for(j=1;j<n;j++)
{
if(flag[j]==0&&cost[j]<mincost)
{
mincost=cost[j];
k=j;//记忆最小的边
}
}
flag[k]=1;//k加入U集合
printf("k==%d\n",k);
for(j=1;j<n;j++)
if(flag[j]==0&&gm[k][j]<cost[j])//其中条件flag[j]==0是非常重要的
{
cost[j]=gm[k][j];//更新cost[]的最新值
tree[j]=k;
printf(" %d->%d\n",k,j);
// printf("j==%d\n",j);
}
}
}
int main()
{ freopen("1.txt","r",stdin);
printf("以序号为0的顶点出发生成最小生成树\n");
int i,j,k,n,e,c;
int tree[50],cost[50];
scanf("%d%d",&n,&e);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
gm[i][j]=maxcost;
for(k=1;k<=e;k++)
{
scanf("%d%d%d",&i,&j,&c);
gm[i][j]=gm[j][i]=c;
}
prim(tree,cost,n);
for(i=0;i<n;i++)
printf("tree[%d]==%d\n",i,tree[i]);
printf("\n");
return 0;
}
//测试用例
/*7 10
0 1 50
0 2 60
1 3 65
1 4 40
2 3 52
2 6 45
3 4 50
3 5 30
3 6 42
4 5 70*/
分享到:
相关推荐
图的算法之一,最小生成树的普里姆算法 自己编写的,有不足的地方欢迎大家指出来
数据结构的课程设计。用普里姆算法求图的最小生成树
用Prim算法构造一颗最小生成树 (2) 实验原理: ①从网中任一顶点开始,先把该顶点包含在生成树中,此时生成树只有 一个顶点。 ②找出一个端点在生成树中另一端点在生成树外的所有边,并把权值最 小的边连到同它所...
用普里姆算法求最小生成树并用mfc实现界面化。输入图的信息可以画出图及最小生成树。
普里姆(Prim)算法构造最小生成树 编译通过版本 可以直接运行使用
基于matlab的最小生成树的prim算法,有详细的解释,可直接运行
最小生成树之普里姆算法
利用普里姆算法求解最小生成树 利用普里姆算法求解最小生成树 利用普里姆算法求解最小生成树
第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小...
数据结构 普里姆算法建立最小生成树 c语言 源代码
本程序使用MFC可视化界面实现的,用普里姆算法实现最小生成树,在MFC上显示出来
若要在n个城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网,是一个网...(2)利用普里姆算法和克鲁斯卡尔算法求网的最小生成树; (3)按顺序输出生成树中各条边以及它们的权值。
用C++实现的图的建立 以及用普里姆算法和克鲁斯卡尔算法求图的最小生成树
普里姆算法生成最小生成树课程设计报告书.doc
【最新精选】普里姆算法生成最小生成树_课程设计.doc
建立一个图,其存储方式采用邻接矩阵形式,利用普里姆算法和克鲁斯卡尔算法求网的最小生成树,按顺序输出生成树中各条边以及它们的权值。
C语言写的 数据机构的课程设计,用普利姆算法构造最小生成树。。想要的可以下载。。。
克鲁斯卡尔算法构造最小生成树 克鲁斯卡尔算法构造最小生成树
最小生成树之普里姆算法
离散数学中用kruskal来实现最小生成树的方法的报告。