北京信息科技大学软件课程设计

1、北京信息科技大学计算机软件基础课程设计题 目： 最小生成树最优通信网 学 院： 信息与通信工程学院 专 业： 通信工程专业 学生姓名： XXXX 班级/学号 通信14XX/2014XXXXX 指导老师： 李振松，曹林 起止时间： 9月24日 至 10月30日 摘要题目6最小生成树最优通信网（难度系数10，全部做出给100分）主要内容1、 如果以无向图表示n个城市之间的通信网络的建设规划，顶点表示城市，边上权值表示该线路的造价，设计一个方案，使这个通信网的总造价最低。2、 学会建立图的邻接表，理解图的基本概念。3、 学会编写DLL函数。4、 掌握建立最小生成树的Prim算法、Kruskal算法。

2、5、 掌握C+编程环境的基本调试方法，熟练使用可视化C+编程工具。6、 提示：在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，使总的耗费最少，构成最优通信网呢？这个问题本质上就是构造连通图的最小代价生成树。设计要求1、上交课程设计的书面材料，要求打印。包括课程设计任务书、主要内容，源程序，对程序的功能进行客观评价，明确指出自己编写了哪些具体函数。2、上交电子版源程序，包括邻接表建立程序、Prim算法、Kruskal算法。3、自己编写一个求素数函数，把它书写成一个动态链接库形式，并在主函

3、数中调用它。尝试把自己编写的程序写成动态链接库和静态链接库形式（无需上交），并比较以下三种EXE文件的大小。A：调用静态链接库生成的EXE执行文件。B：调用动态链接库生成的EXE执行文件。C：直接调用函数生成的EXE执行文件。主要仪器设备计算机一台，安装Windows XP 操作系统、Microsoft Visual C+ 6.0、MSDN Library。主要参考文献1 侯俊杰. 深入浅出MFC(第二版)M. 武汉：华中科技大学出版社, 2001.2 谭浩强. C程序设计（第二版）M. 北京：清华大学出版社, 1999.3 孟彩霞. 计算机软件基础M. 陕西：西安电子科技大学出版社, 200

4、3.4 严蔚敏, 吴伟民. 数据结构M. 北京：清华大学出版社, 2005.课程设计进度计划（起止时间、工作内容）选做图的遍历和最小生成树题目的同学，2人1组，1人做图的遍历，1人做最小生成树，整个课程设计共20学时，具体进度如下：4 学时 了解课题背景，选题，学习DLL，学习图的基本概念。4 学时 编写邻接表建立程序。4 学时 最小生成树Prim算法。4 学时 最小生成树Kruskal算法。4 学时 调试程序，答辩。课程设计开始日期见选题说明课程设计完成日期见选题说明课程设计实验室名称计算中心机房地 点健翔桥校区摘要 最小生成树最优通信网对于这个题目，首先，我想到的是如何来构建一个通信网，也

5、就是如何构建一张无向图，当然图在计算机内的存储有 很多种，我这里应用了邻接表来存储无向图，但是后来又将其转换成邻接矩阵和边集数组的形式来存储，一方面我想了解比对一下这几种存储方式，另一方面也使得接下来的prim算法和Kruskal算法的处理变得容易，再 说一下这两个最小生成树的算法，prim算法相比较而言更适合较多节点 的图，而Kruskal算法则更适合于较少节点的图，prim算法给我的感觉更像是顺藤摸瓜，它先有一个起始点，之后顺着这个点往下遍历，当找到最优路径时，我的想法是就把他们合为一个整体，依次将整个图的最优路径遍历出来，而Kruskal算法我感觉稍稍有一点不足，就是需要对权值进行排序，

6、这在很多节点时就显得很不足，但这个算法对于节点很少的图来说非常好，基本上结果就是那个排好序的边集数组的前几项，当然如果形成环，就再加几项，我想这种情况也不是特别特别常见，因此很多时候不需要完整遍历整个图，所以相对较好一些，最后说一下输出，我这里采用邻接表和链接矩阵两种方式来做输出。19参考文献目录 任务书1摘要2目录3正文4参考文献11源代码12int main()函数用途：主函数是这个工程的入口函数，函数调用菜单函数，开始整个程序的运行void menu();函数用途：菜单函数，询问用户接下来要做的事情，并调用响应的功能函数void addHeadNode();函数用途：添加头节点void

7、addNode();函数用途：添加普通节点void change();函数用途：将邻接表转换成邻接矩阵void completeNode();函数用途：完成输入，输出当前的邻接表和邻接矩阵void MiniSpanTree_Prim();函数用途：prim算法计算输出最优路径int Find(int *parent,int f);函数用途：Kruskal算法判断是否构成环路void MiniSpanTree_Kruskal();函数用途：Kruskal算法计算输出最优路径以下为概念部分，即在学习过程中参考的一些概念或者别人的理解图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式

8、分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器(n个顶点建立n个容器)，第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。在有向图中，描述每个点向别的节点连的边(点a-点b这种情况)。在无向图中，描述每个点所

9、有的边(点a-点b这种情况)与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫亚尔尼克（英语：Vojtch Jarnk）发现；并在1957年由美国计算机科学家罗伯特普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格迪科斯彻再次发现了该算法。1).输入：一个加权连通图，其中顶点集合为V，边集合

10、为E；2).初始化：Vnew= x，其中x为集合V中的任一节点（起始点），Enew= ,为空；3).重复下列操作，直到Vnew= V：a.在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且vV（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；b.将v加入集合Vnew中，将边加入集合Enew中；4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。下面对算法的图例描述图例说明不可选可选已选（Vnew）此为原始的加权连通图。每条边一侧的数字代表其权值。-顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近

11、的顶点，因此将A及对应边AD以高亮表示。C, GA, B, E, FD下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。C, GB, E, FA, D算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。CB, E, GA, D, F在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。E最近，因此将顶点E与相应边BE高亮表示。无C, E, GA, D, F, B这里，可供选择的顶点只有C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。无C, GA, D, F, B, E

12、顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。无GA, D, F, B, E, C现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。无无A, D, F, B, E, C, GKruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。2.算法简单描述1).记Graph中有v个顶点，e个边2).新建图Gra

13、phnew，Graphnew中拥有原图中相同的e个顶点，但没有边3).将原图Graph中所有e个边按权值从小到大排序4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中添加这条边到图Graphnew中图例描述：首先第一步，我们有一张图Graph，有若干点和边将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择，排序完成后，我们率先选择了边AD。这样我们的图就变成了右图在剩下的变中寻找。我们找到了CE。这里边的权重也是5依次

14、类推我们找到了6,7,7，即DF，AB，BE。下面继续选择， BC或者EF尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是右：参考文献 1 孟彩霞. 计算机软件基础M. 陕西：西安电子科技大学出版社, 2003.2 严蔚敏, 吴伟民. 数据结构M. 北京：清华大学出版社, 2005.源代码源文件/引入头文件 #include stdio.h#include st

15、dlib.h#include malloc.h/定义可能的最大头节点数目 #define MAX_HEADNODE 100/定义最大可能值 #define INTINITY 65535/边集数组 #define MAGEDGE 1000/定义当前操作节点,从-1做起始值,之后在每次添加头结点时+1 int nowHead = -1;int mapMAX_HEADNODEMAX_HEADNODE;/函数声明void menu();void addHeadNode();void addNode();void change();void completeNode();void MiniSpanTre

16、e_Prim();int Find(int *parent,int f);void MiniSpanTree_Kruskal();/定义单个节点 struct node int adjvex;int data;struct node *next;/给结构体重命名 typedef struct node NODE;/为单链表附一个头节点struct headnodeint vexdata;NODE *firstnode;nodeListMAX_HEADNODE;/定义边集数组struct Edgeint begin;int end;int weight; /菜单,每次结束节点的插入返回此菜单 v

17、oid menu()int n;printf(请选择你将要进行的任务n1.添加一个新的头节点n2.继续添加邻接节点n3.完成输入n4.普里姆算法n5.克鲁斯卡尔算法n0.退出程序n);scanf(%d,&n);switch (n)case 0:exit(0);case 1:addHeadNode();break;case 2:addNode();break;case 3:completeNode();break;case 4:MiniSpanTree_Prim();break;case 5:MiniSpanTree_Kruskal();break;default :printf(您输入的操作信

18、息有误，请重新输入n);menu();break; /添加头节点 void addHeadNode()/头结点+1 nowHead+;/无向图，双向不需要判断是否有邻接节点 printf(请输入一个头节点名称n);/头节点信息域 scanf(%d,&(nodeListnowHead.vexdata);/头节点指针域 nodeListnowHead.firstnode=NULL;/结束节点的添加，返回主菜单 menu(); /添加普通节点void addNode()/生成一个节点 NODE *p = (NODE *)malloc(sizeof(NODE);printf(请输入此节点相关信息n);

19、/节点表示名 printf(请输入节点名称n);scanf(%d,&(p-adjvex);/节点的权值 printf(请输入此节点的权值n);scanf(%d,&(p-data);/插入节点 ，反向建立链表 p-next=nodeListnowHead.firstnode;nodeListnowHead.firstnode = p;/结束节点的添加返回主菜单menu(); /结束输入void completeNode()int i=0; NODE *p;printf(已经为您建立好的当前节点邻接表n);/输出所有已经建立好的节点 for(i=0;i,nodeListi.vexdata);p =

20、 nodeListi.firstnode;while(p!=NULL)printf(%d|%d| -,p-adjvex,p-data);p=p-next; printf(n);change();/返回主菜单 menu(); void change()int i,j; NODE *p;for(i=0;i=nowHead;i+)/初始化数组 for(j=0;jadjvex = p-data;p=p-next; mapii=0;/自己到自己 for(i=0;i=nowHead;i+)for(j=0;j=nowHead;j+)printf(%dt,mapij);printf(n);/Prim算法生成最

21、小生成树void MiniSpanTree_Prim()int min,i,j,k;int count = nowHead + 1;/VC下需将count改为一个数字 int adjvexvcount;/保存相关顶点下标,有无联系 int lowcostcount;/保存相关顶点边的权值lowcost0 = 0;/V0作为最小生成树的根开始遍历，权值为0adjvexv0 = 0;/V0第一个加入/初始化操作for(i=1;icount;i+)lowcosti = map0i;/将邻接矩阵第0行所有权值先加入数组adjvexvi = 0;/ 初始化全部为 V0的下标 /真正构建最小生成树的过程f

22、or(i=1;icount;i+)min = INTINITY;/初始化最小权值为65535等不可能的数值j=1;k=0;/遍历全部顶点while(j count) /找出lowcost数组已存储的最小权值if(lowcostj!=0 & lowcostj min)/0代表自己和自己连线，min代表无关系 min = lowcostj;k=j;/将发现的最小权值的下标存入k，以待使用 j+; /打印当前顶点边中权值最小的边printf(%d,%d),adjvexvk,k);lowcostk = 0; /将当前顶点的权值设置为0，表示此顶点已经完成任务，进行下一个顶点的遍历/邻接矩阵k行逐个遍历全部顶点for(j=1;jcount