贪心算法 最小生成树

课程设计说明书(论文)用纸I摘要网络的最小生成树在实际中有广泛的应用，例如，网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价）。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。本课程设计采用贪心算法中Prim算法解决最小生成树问题，贪心算法包括两个基本要素：最优子结构性质和贪心选择利性质，贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。通过分析用贪心算法解决最小生成树问题能得到问题的最优解。根据算法的设计结果，采用C++语言实现算法，通过测试分析，程序运行结果正确，运行效率较高。关键词：最小生成树，贪心算法课程设计说明书(论文)用纸II目录1问题描述....................................................................................................................12问题分析....................................................................................................................23建立数学模型............................................................................................................34算法设计....................................................................................................................55算法实现....................................................................................................................66测试分析..................................................................................................................12结论..........................................................................................................................13参考文献......................................................................................................................14课程设计说明书(论文)用纸第1页共14页1问题描述设图G=(V，E)是一简单连通图，|V|=n，|E|=m，每条边ei都给以权wi，wi假定是边ei的长度（其他的也可以），i=1，2，3，…，m。求图G的总长度最短的树。首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jv-s，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。课程设计说明书(论文)用纸第2页共14页2问题分析首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jv-s，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。该算法的特点是当前形成的集合T始终是一棵树。将T中U和TE分别看作红点和红边集，V-U看作蓝点集。算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。MST性质保证了此边是安全的。T从任意的根r开始，并逐渐生长直至U=V，即T包含了C中所有的顶点为止。MST性质确保此时的T是G的一棵MST。因为每次添加的边是使树中的权尽可能小，因此这是一种“贪心”的策略。该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。基本思想：首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。此时，这个连通分支就是G的一棵最小生成树。当输入的连通带权图有e条边时，则将这些边依其权组成优先队列需要O(e)时间，在上述算法的while循环中，DeleteMin运算需要O(loge)时间，因此关于优先队列所作运算的时间为O(eloge)。实现UnionFind所需的时间为O(eloge)或O(elog*e)。所以Kruskal算法所需的计算时间为O(eloge)。当e=Ω(n2)时，Kruskal算法比Prim算法差，但当e=O(n2)时，Kruskal算法却比Prim算法好得多。Kruskal算法的时间主要取决于边数。它较适合于稀疏图。课程设计说明书(论文)用纸第3页共14页3建立数学模型1.在编译时，出现有些库函数没有定义和警告错误；解决方法：需要在程序首部加入以下包含文件：#includestdio.h、#includestring.h、#includemalloc.h、#includeiomanip.h；出现的警告错误是由于定义一指针变量时，需用库函数malloc（）为其分配内存空间2.在创建无向网函数creat()中，当输入的顶点个数=1时，由于其不满足网的定义，因此如何求其最小生成树；当通过键盘分别输入边所关联的两个顶点和权值时，用语句“scanf(“%d%d%d”,v1,v2,weight)”输入时，会导致结果出现错误；解决方法：通过在函数首部定义一标记变量flag，将其初始化为0，当输入的顶点个数=1时，直接输出“最小生成树不存在!”并将flag置为1，其后语句不在继续执行，进入下次操作；通过语句“cinv1v2weight;”输入边所关联的两个顶点和权值；3.在函数Minium()中，当用语句“min=close[0].lowcost”初始化min时，会导致结果出现错误；解决方法：用语句“min=INFINIT;”可以将其置为∞；4.在普里姆算法函数prim()，如何将最小生成树中的顶点序列显示出来；解决方法：首先，定义AdjMatrix结构体类型的指针变量*p，并通过语句“p-vexs[n++]=u;”将起点存入顶点向量表中，然后在for循环体中用语句“p-vexs[n++]=v0;”将每条边的终点依次放入顶点向量表中，最后向量表中的数据就是最小生成树中的顶点序列，通过fou循环将其输出；5.在输出邻接矩阵函数display()中，如何将矩阵中值为INFINIT的元素在屏幕上用∞显示；解决方法：通过if判断语句“if(G-arcs[i][j].adj==INFINIT)cout\t∞;”达到要求；6.在主函数main()中，当前一次创建网时输入的顶点个数=1时，而后一次创建网时输入的顶点个数1时，此时若求最小生成树时，得到的结果将出错。课程设计说明书(论文)用纸第4页共14页解决方法：需在main()函数的第一层while()循环体的最后加入语句“flag=0;”，因为在创建函数creat()中，当第一次创建网时输入的顶点个数=1时，会将flag置1，并且它是外部变量，所以flag在程序结束之前将一直为1，这导致当第二次创建的网中的顶点个数1时，由于flag此时为1，所以仍将其按照第一种情况处理，从而导致结果出错；课程设计说明书(论文)用纸第5页共14页4算法设计1.输入网中的顶点数。您可以输入在定义范围之内的任意值，当输入的顶点数=1时，会显示“最小生成树不存在!”2.请输入网中的边数。根据用户自己定义3.请输入网中的顶点编号。分别输入网中的所有顶点4.输入每条弧所对应的两个顶点及权值格式：起点终点权值。分别输入起点、终点和权值，输入时两者之间以空格隔开5.请输入起点。输入从网中的哪个顶点出发，生成最小生成树，可以输入网中的任意顶点，若输入的起点不是网中的某一顶点则显示“输入起点有错，请重新输入!”若想退出此操作则输入06.继续创建无向网请输入'Y',否则按任意键。如果用户想再次创建网并做相关操作，则输入‘Y’或‘y’否则输入任意字符退出运行环境课程设计说明书(论文)用纸第6页共14页5算法实现#includestdio.h#includestring.h#includemalloc.h#includeiostream.h#includeiomanip.h#defineMAX20//最多顶点个数#defineINFINIT32768//表示极大值，即∞typedefstruct{intadj;//adj是权值类型}ArcNode;typedefstruct{intvexs[MAX],vexnum,arcnum;/*vexs表示顶点向量;vexnum,arcnumf分别表示图的顶点数和弧数*/ArcNodearcs[MAX][MAX];/*邻接矩阵*/}AdjMatrix;typedefstruct{intadjvex;//存放顶点编号intlowcost;//存放顶点权值}Node;Nodeclose[MAX];//求最小生成树时的辅助数组intflag=0;intLocate(AdjMatrix*G,intV)//求顶点位置函数{intj=-1,k;for(k=0;kG-vexnum;k++)if(G-vexs[k]==V){j=k;break;}returnj;课程设计说明书(论文)用纸第7页共14页}AdjMatrix*creat(AdjMatrix*G)//创建无向网{inti,j,k,v1,v2,weight,m=1;printf(请输入网中的顶点数：);scanf(%d,&G-vexnum);if(G-vexnum=1){cout\n****************最小生成树不存在!*********************endl;flag=1;returnG;}else{printf(请输入网中的边数：);scanf(%d,&G-arcnum);for(i=0;iG-vexnum;i++)//初始化邻接矩阵for(j=0;jG-vexnum;j++)if(i==j)G-arcs[i][j].adj=0;elseG-arcs[i][j].adj=INFINIT;printf(请输入网中的顶点编号：);//输入网中的顶点编号for(i=0;iG-vexnum;i++)scanf(%d,&G-vexs[i]);printf(输入每条弧所对应的两个顶点及权值格式：起点终点权值!\n);for(k=0;kG-arcnum;k++){cout请输入第m++条弧：;cinv1v2weight;//输入一条弧的两个顶点及权值i=Locate(G,v1);j=Locate(G,v2);G-arcs[i][j].adj=weight;G-arcs[j][i].adj=weight;课程设计说明书(论文)用纸第8页共14页