最小生成树实习报告 -实习报告

最小生成树实习报告 -实习报告

实习报告题目：停车场的管理班级：姓名：学号：完成日期：一.需求分析1.若要在n个城市之间建设同心网络，只需要架设n-1条线路即可。以最低的经济代价建设这个通信网。2.利用克鲁斯卡尔算法求网的最小生成树，抽象数据类型MFSet，以文本形式输出生成树各条边及权值。3.测试数据见如下二.概要设计1.MFSet Graph{数据对象：vex1,wex2为图的点数据关系：R={vex1,vex2|vex1,vex2∈N,vex1,vex2表示vex1到vex2的弧}基本操作：kruskal(Edge E,int n,int e)初始条件：E存在操作结果：对插入边判定，生成最小生成树order(Edge E,int n)初始条件：E数组存在操作结果：对E数组按权值排序}三.详细设计#define MAXE 11#define MAXV 10#include stdio.h#include stdlib.h#include math.h typedef struct{int vex1；//边的起始顶点int vex2；//边的终止顶点int weight；//边的权值}Edge；void kruskal(Edge E,int n,int e){int i,j,m1,m2,sn1,sn2,k；int vset[MAXV]；for(i=1；i=n；i++)//初始化辅助数组vset[i]=i；k=1；//表示当前构造最小生成树的第k条边，初值为1 j=0；//E中边的下标，初值为0 while(k e)//生成的边数小于e时继续循环{m1=E[j].vex1；m2=E[j].vex2；//取一条边的两个邻接点sn1=vset[m1]；sn2=vset[m2]；//分别得到两个顶点所属的集合编号if(sn1！=sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边{printf("(v%d,v%d)：%d\n",m1,m2,E[j].weight)；k++；//生成边数增l if(k=e)break；for(i=1；i=n；i++)//两个集合统一编号if(vset[i]==sn2)//集合编号为sn2的改为sn1 vset[i]=sn1；}//if j++；//扫描下一条边}//while}//kruskal int order(Edge E,int n)//对边进行排序{int k；for(int i=0；i n；i++){for(int j=0；j n；j++){if(E[i].weight E[j].weight){k=E[i].vex1；E[i].vex1=E[j].vex1；E[j].vex1=k；k=E[i].vex2；E[i].vex2=E[j].vex2；E[j].vex2=k；k=E[i].weight；E[i].weight=E[j].weight；E[j].weight=k；}}}return 1；}int main(){Edge E[MAXE]；int nume,numn；printf("输入边数和顶数：\n")；scanf("%d%d",&nume,&numn)；//nume=10；//numn=6；printf("请输入各边及对应的的权值(起始顶点终止顶点权值)\n")；for(int i=0；i nume；i++){scanf("%d%d",&E[i].vex1,&E[i].vex2)；E[i].weight=rand()0；}//在这里对输入的数据进行排序，达到假设的要求，即：假设数组E存放图G中的//所有边，且边已按权值从小到大的顺序排列order(E,nume)；kruskal(E,numn,nume)；}主程序order kruskal四.调试分析1.该程序使用一个额外的数组用于对边能否成为生成树边进行判定，该方法很巧妙得让程序的简单明了。由于判定好后要对数组进行一次比较，所以时间和空间上有待优化。2.该程序在对E数组进行排序时的时间复杂度为O(n),再对边进行插入时的时间复杂度为O(n)3.程序在输入时比较繁琐，输出的结果也不是很直观，最好能改进成图的形式输出。五.用户手册1.本程序的运行环境为DOS操作系统，执行文件为kruskal.exe 2.进入程序后显示用户界面：3.按提示输入边的顶点即可权值随机生成，以回车符表示结束4.接受命令后执行相应的算法生成最小生成树并输出六.测试结果E[0].vex1=1；E[0].vex2=3；E[4].vex1=1；E[4].vex2=

4；E[6].vex1=2；E[6].vex2=3；E[2].vex1=2；E[2].vex2=5；E[5].vex1=3；E[5].vex2=4；E[3].vex1=3；E[3].vex2=6；E[1].vex1=4；E[1].vex2=6；输出v2,v3：1 v1,v2：24 v1,v4：34 v3,v5：58 v3,v6：62七.附录由函数写在同一文件下，无其他源程序文件名MSN空间完美搬家到新浪博客！