#include "stdio.h"
#include "stdlib.h"
#define MAXINT 32767
#define MAX 100
/*普里母算法 以节点为向导,找出节点相连最短的边*/
/*
test data: 6 0 1 1 0 2 33 0 3 43 0 4 5 0 5 32 1 2 3 1 3 4 1 4 5 1 5 76 2 3 2 2 4 5 2 5 6 3 4 5 3 5 665 4 5 4 -1 -1 -1
result:
please input node num:
(V0 ,V1)(V1 ,V2)(V2 ,V3)(V0 ,V4)(V4 ,V5)the sum is 15
*/
//输入顶点和边信息
void read(int a[][MAX],int *v)
{
int n,i,j,w;
printf("please input node num:\n");
scanf("%d",&n);
if(n>MAX)
{
printf("input node value not > %d",MAX);
return;
}
*v=n;
//初始化a
for(i=0;i<n;i++)
for(j=0;j<n;j++)a[i][j]=MAXINT;
do
{
scanf("%d%d%d",&i,&j,&w);
if(i==-1||j==-1||w==-1)break;
a[i][j]=w;
}while(9);
}
void plmMST(int a[][MAX],int n)
{
int c,i,j,min_w,min_i,min_j,sum=0;
//开始选中0节点 扫描
a[0][0]=-1;
for(c=0;c<n-1;c++)
{
min_w = MAXINT;
min_i = -1;
min_j = -1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
//从节点扫描,找出同i点相关的节点(该节点未访问)最小的权
if(i!=j&&(a[i][i]==-1&&a[j][j]!=-1||a[i][i]!=-1&&a[j][j]==-1)&&a[i][j]<min_w)
{
min_w=a[i][j];
min_i=i;
min_j=j;
}
}
}
//找到最小权 ,置为访问
if(min_i!=-1)
{
printf("(V%-2d,V%d)",min_i,min_j);
//a[min_i][min_j]=MAXINT;?
a[min_i][min_i]=a[min_j][min_j]=-1;
sum+=min_w;
}
else
{
printf("图不是连通的\n");
exit(-2);
}
}
printf("the sum is %d\n",sum);
}
void main()
{
int a[MAX][MAX],vnum;
read(a,&vnum);
plmMST(a,vnum);
}
分享到:
相关推荐
图的算法之一,最小生成树的普里姆算法 自己编写的,有不足的地方欢迎大家指出来
数据结构的课程设计。用普里姆算法求图的最小生成树
用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来实现最小生成树的方法的报告。