运筹学课程设计报告书---最小生成树问题

运筹学课程设计报告书专业班级学号姓名LMZZ日期2011.09.01设计题目：最小生成树问题设计方案：本设计是在C语言环境下运行的，主要有:minitree_KRUSKAL()此函数包含几个算法有对树的邻接矩阵的构造，数据的输入，克鲁斯卡尔算法（又称Kruskal算法，其类似于求生成树的“避圈法”）求网的最小生成树，最小生成树的最小代价，输出最小生成树的顶点及其最小代价。ljjzprint(intn)定义并输出邻接矩阵。主程序：intmain(){minitree_KRUSKAL();（函数调用）printf(输出邻接矩阵是：\n);ljjzprint(n);（函数调用）}方案实施：•1、定义结构体以及各个变量；•2、数据的输入；•3、采用克鲁斯卡尔算法求出该图的最小生成树；•4、采用邻接矩阵做储存结构创建图；•5、在主函数中分别调用以上各个函数，最终实现设计目的。克鲁斯卡尔算法的表示：while(in){min=INFINITE;for(j=0;jm;j++){if(e[j].weightmin&&e[j].flag==0){min=e[j].weight;sum+=min;k=j;}}if(t[e[k].vexh].jihe!=t[e[k].vext].jihe){e[k].flag=1;for(j=1;j=n;j++)if(t[j].jihe==t[e[k].vext].jihe)t[j].jihe=t[e[k].vexh].jihe;t[e[k].vext].jihe=t[e[k].vexh].jihe;i++;}elsee[k].flag=2;}邻接矩阵的表示：voidljjzprint(intn)/*定义并输出邻接矩阵*/{inti,j;for(i=1;i=n;i++){for(j=1;j=n;j++)printf(%d\t,adjmatrix[i][j]);printf(\n);}}intmain(){minitree_KRUSKAL();函数调用printf(输出邻接矩阵是：\n);ljjzprint(n);输出矩阵return0;}调试过程：原设计在定义输出矩阵函数时，没有形参，在调用时必须输入树的定点数这和前面的函数在输入树的数据时重复操作，为了避免重复如果这个函数添加一个参数为n的形参，再main函数调用minitree_KRUSKAL();后n为定值，n为了在ljjzprint(n)中为已知量则需在程序的开头定义一个全局变量n即可。在求最小生成树的代价时，因为其顶点的权值时变的故重新定义个变量sum，以实现其权值的相加然后输出。结果与结论：测试结果：顶点为：a，b，c,d,e其标号分别为1，2，3，4，5Vexh和vext分别为边的两端顶点，weight为边的权值运行如下:结论：通过实际操作，运用简单的C语言程序编程能比较清楚和简单的把运筹学当中的相对抽象的最小树问题表现出来。具体分工：我主要负责程序后期的修改以及调试，才能使整个程序正常的运行出来。还有对ppt的制作和课程设计书整体的把握！收获与致谢：紧张而又忙碌的课设学习终于结束了，在本次课设中我们也取得了相对很大的成就，通过本次课程设计我们也学到了很多，它增加了我们编程软件的兴趣，在具体操作中对所学的C语言的理论知识得到了巩固，达到实训的目的也发现了自己的不足之处，在以后的上机中应更加注意，同时体会到了C语言具有语句简洁，使用灵活，执行效率高等特点，并且通过此次运筹学课程设计，我们通过C语言将其中抽象的最小树问题比较直观的变现出来，掌握了求最小树问题的克鲁斯卡尔算法以及邻接矩阵的构造，特别是对C语言中数组和循环有了深刻的了解。通过实际操作将C语言编程和运筹学有机的结合起来，学会了C语言编程的基本步骤和基本方法，开发了自己的逻辑思维能力，培养了分析问题和解决问题的能力。在此衷心感谢学院安排这次课设，让我们又多了一次学习交流的机会，更好的巩固了所学的知识，拓展了知识面。本次课设能取得成功，要感谢老师的帮助和指导。在课设期间老师帮助我们分析思路，提供方法，才使得我们的程序做的更加的完善。其次是要感谢和我同组的同学感谢对方对本次课设的付出。参考文献：《运筹学教程》（第三版）胡运权主编《C程序设计》（第三版）谭浩强编著《C程序设计题解与上机指导》（第三版）谭浩强编著附件：本设计的详细代码如下：#includestdio.h#defineM30#defineINFINITE9999#definen0100intadjmatrix[n0+1][n0+1];intn;typedefstruct{chardata;intjihe;}VEX;typedefstruct{intvexh,vext;intweight;intflag;}EDGE;voidminitree_KRUSKAL(){inti,m,min,k,j;intsum=0;VEXt[M];EDGEe[M];printf(最小生成树问题\n);printf(程序设计者：冯云广，吕金刚\n);printf(输入顶点数及边数:);fflush(stdin);scanf(%d%d,&n,&m);//n个点m条边printf(输入各个顶点名称:\n);for(i=1;i=n;i++){printf(t[%d].data=:,i);//输入顶点字符getchar();fflush(stdin);//清除缓存scanf(%c,&t[i].data);//输入点对应的字符t[i].jihe=i;}printf(输入两个不同顶点及其边权:\n);for(i=1;i=m;i++)for(j=1;j=m;j++)adjmatrix[i][j]=0;for(i=0;im;i++){printf(vexh,vext,weight:);fflush(stdin);scanf(%d%d%d,&e[i].vexh,&e[i].vext,&e[i].weight);if(e[i].weight0){adjmatrix[e[i].vexh][e[i].vext]=1;adjmatrix[e[i].vext][e[i].vexh]=1;}e[i].flag=0;}i=1;while(in){min=INFINITE;for(j=0;jm;j++){if(e[j].weightmin&&e[j].flag==0){min=e[j].weight;k=j;}}if(t[e[k].vexh].jihe!=t[e[k].vext].jihe){e[k].flag=1;for(j=1;j=n;j++)if(t[j].jihe==t[e[k].vext].jihe)t[j].jihe=t[e[k].vexh].jihe;t[e[k].vext].jihe=t[e[k].vexh].jihe;i++;}elsee[k].flag=2;}printf(克鲁斯卡尔算法及代价如下：\n);for(i=0;im;i++)if(e[i].flag==1){printf((%d,%d)%d\n,e[i].vexh,e[i].vext,e[i].weight);sum+=e[i].weight;}printf(最小生成树的权是：);printf(%d\n,sum);}voidljjzprint(intn)/*定义并输出邻接矩阵*/{inti,j;for(i=1;i=n;i++){for(j=1;j=n;j++)printf(%d\t,adjmatrix[i][j]);printf(\n);}}intmain(){minitree_KRUSKAL();printf(输出邻接矩阵是：\n);ljjzprint(n);return0;}指导教师评语：课程设计报告成绩：，占总成绩比例：20%答辩成绩：，占总成绩比例：30%课程设计作品，占总成绩比例：50%总成绩：。