2012216706汪京城 实验五
算法
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
与
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
实验日志
实验六
指导教师 实验时间: 年 月 日 学院 计算机科学与技术 专业 网络技术 班级 5321203 学号 2012216706 姓名 汪京城 实验室
实验题目:
采用普里姆(prim)算法构造网络的最小生成树。 实验目的:
深入理解最小生成树的概念，熟练掌握普里姆(prim)算法的工作过程，并通过定义合适的数据结构，采用C语言程序实现。
实验原理:
通过一系列不断扩张的指树来构造最小生成树，从图的顶点集合V中任意选择一个单顶点，作为序列中的初始子树。。每依次迭代时，以一种贪婪的方式来扩张当前的生成树，即简单的把不在树中的最近顶点添加到树中。
实验主要程序:
#include
/*定义一个结构体，用于记录一条边的始点与终点*/
typedef struct pp
{
int p,q;
} edge;
int g[100][100],u[100],v[100],vexnum; edge p[100];//用于记录最小生成树的各条边
void input()//读入图的邻接矩阵
{
int i,j,temp;
FILE *fp;
fp=fopen("pp5.txt","r");
fscanf(fp,"%d",&vexnum);
for (i=1;i<=vexnum;i++)
{
printf("\n");
for (j=1;j<=vexnum;j++)
{
fscanf(fp,"%d",&temp);
g[i][j]=temp;
printf("%d ",temp);
}
}
fclose(fp);
}
void main()
{
int i,j,k,m,n,ma,s=0;
input();//输入数据
for (i=1;i<=vexnum;i++)//集合V中包含了所有顶点
v[i]=1;
u[1]=1;v[1]=0;//第1个节点加入至集合U中，并从集合V中去掉
for (i=1;i<=vexnum-1;i++)//最多需vexnum-1条边
{
//以下找连接节点集U至节点集V的最小边
ma=1000;//ma存放最小边的权值
for (j=1;j<=i;j++)//集合U中的第j个节点，其编号为u[j],每次增加一个，共有i个
for (k=1;k<=vexnum;k++)
/*v[k]!=0
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示节点k在集合V中;g[u[j][k]>0表示有边*/
if(v[k]!=0&&ma>g[u[j]][k]&&g[u[j]][k]>0)
{
ma=g[u[j]][k];//保存最小边值
m=u[j];//最小边的始点编号
n=k;//最小边的终点编号
}
s=s+ma;//求和
u[i+1]=n;v[n]=0;//把找到最小边的终点编号从V中去掉，并加入至U中
p[i].p=m;p[i].q=n;//保存最小边的始点编号与终点编号
}
printf("\n");
for (i=1;i<=vexnum-1;i++)
printf("\n%d %d %d",p[i].p,p[i].q,g[p[i].p][p[i].q]);
printf("\nsum=%d\n\n",s);
}
实验结果:
心得体会:
深入理解了最小生成树的概念，并熟练掌握普里姆(prim)算法的工作过程，并通过定义合适的数据结构，采用C语言程序实现。
浙公网安备 33021202002483