《贪心算法最小生成树》由会员分享，可在线阅读，更多相关《贪心算法最小生成树（15页珍藏版）》请在金锄头文库上搜索。
1、摘要网络的最小生成树在实际中有广泛的应用，例如，网络 G表示n各城市之 间的通信线路网线路其中顶点表示城市，边表示两个城市之间的通信线路， 边 上的权值表示线路的长度或造价。可通过求该网络的最小生成树到达求解通信 线路或总代价最小的最正确方案。本课程设计采用贪心算法中Prim算法解决最小生成树问题，贪心算法包括两个根本要素：最优子结构性质和贪心选择利性质， 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能 产生整体最优解。通过分析用贪心算法解决最小生成树问题能得到问题的最优 解。根据算法的设计结果，采用 C+祁言实现算法，通过测试分析，程序运行 结果正确，运行效率较高。关
2、键词:最小生成树，贪心算法以切融孤潭祐课程设计说明书论文用纸目录1问题描述1.2问题分析2.3建立数学模型 .3.4算法设计5.5算法实现6.6测试分析.12结论13参考文献14#专场耕悠窘祐课程设计说明书论文用纸1问题描述设图G=V, E是一简单连通图，|V|=n , |E|=m，每条边ei都给以权wi, wi假定是边ei的长度其他的也可以，i=1 , 2, 3, , , m求图G的总长度 最短的树。首先置S=1，然后,只要S是V的真子集，就作如下的贪心选择： 选取满足条件i WS, j wv-s ,且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所
3、有边恰好构成G的一棵最小生成树。第#页共14页专场耕悠窘祐课程设计说明书(论文)用纸2问题分析首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取 满足条件隹S,住v-s,且cij最小的边，将顶点j添加到S中。这个过程一 直进行到S=V时为止。在这个过程中选取到的所有边恰好构成 G的一棵最小生 成树。该算法的特点是当前形成的集合 T始终是一棵树。将T中U和TE分别看 作红点和红边集，V-U看作蓝点集。算法的每一步均是在连接红、蓝点集的紫 边中选择一条轻边扩充进T中。MST性质保证了此边是平安的。T从任意的根 r开始，并逐渐生长直至U=V，即T包含了 C中所有的顶点为止。MST性质确
4、 保此时的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条边。这个过程一直进行到只剩下
5、一个连通分支时为止。此时，这个连通分支就是G的一棵最小生成树。当输入的连通带权图有e条边时，那么将这些边依其权组成优先队列需要 O(e) 时间，在上述算法的while循环中,DeleteMin运算需要O(loge)时间，因此关丁 优先队歹0所作运算的时间为 O(eloge)。实现UnionFind所需的时间为O(eloge) 或O(elog*e)。所以Kruskal算法所需的计算时间为 O(eloge)。当e=Q (r2)时，Kruskal算法比Prim算法差，但当e=O(n2)时,Kruskal算法 却比Prim算法好得多。Kruskal算法的时间主要取决丁边数。它较适合丁稀疏 图。3建立数
6、学模型1 .在编译时，出现有些库函数没有定义和警告错误；解决方法：需要在程序首部参加以下包含文件：#includestdio.h、#includestring.h 、#includemalloc.h 、#include iomanip.h ；出现的 警告错误是由丁定义一指针变量时，需用库函数 malloc ()为其分配内存空间2 .在创立无向网函数creat()中，当输入的顶点个数=1时，由丁其不满足网的 定义，因此如何求其最小生成树；当通过键盘分别输入边所关联的两个顶点和 权值时，用语句 scanf( %d%d%d, v1,v2,weight) 输入时，会导致结果出现错 误；解决方法：通过在
7、函数首部定义一标记变量flag,将其初始化为0,当输入 的顶点个数v1v2weight; 输入边 所关联的两个顶点和权值；3 .在函数Minium()中，当用语句 min=close0.lowcost初始化 min时,会导 致结果出现错误；解决方法：用语句“ min=INFINIT; 可以将其置为8；4. 在普里姆算法函数prim(),如何将最小生成树中的顶点序列显示出来；解决方法：首先，定义 AdjMatrix结构体类型的指针变量*p,并通过语 句 p-vexsn+=u;将起点存入顶点向量表中，然后在 for循环体中用语句 “p-vexsn+=v0;将每条边的终点依次放入顶点向量表中，最后向
8、量表中的数据就是最小生成树中的顶点序列，通过fou循环将其输出;5. 在输出邻接矩阵函数display()中，如何将矩阵中值为INFINIT的元素在屏 幕上用00显示；解决方法： 通过 if 判 断语句 “ if(G-arcsij.adj=INFINIT) coutt 8 ; 到达要求；6 .在主函数main()中，当前一次创立网时输入的顶点个数 1时，此时假设求最小生成树时，得到的结果将出错。第#页共14页去切融夷潭祐课程设计说明书(论文)用纸解决方法：需在main()函数的第一层while()循环体的最后参加语句 flag=0;， 因为在创立函数creat()中，当第一次创立网时输入的顶点
9、个数 1时，由丁 flag此时为1,所以仍将其按照第一种情 况处理，从而导致结果出错；第#页共14页专场耕悠窘祐课程设计说明书论文用纸4算法设计1. 输入网中的顶点数。您可以输入在定义范围之内的任意值，当输入的顶点数。分别输入起 点、终点和权值，输入时两者之间以空格隔开5. 请输入起点。输入从网中的哪个顶点出发，生成最小生成树，可以输入网中 的任意顶点，假设输入的起点不是网中的某一顶点那么显示“输入起点有错，请重 新输入! 假设想退出此操作那么输入06. 继续创立无向网请输入Y,否那么按任意键。如果用户想再次创立网并做相关 操作，那么输入Y或y否那么输入任意字符退出运行环境第#页共14页5算法
10、实现#includestdio.h#includestring.h#includemalloc.h#includeiostream.h#include iomanip.h#define MAX 20 最多顶点个数#define INFINIT 32768/表示极大值，即 8typedef struct(int adj; /adj是权值类型ArcNode;typedef struct(int vexsMAX,vexnum,arcnum;/*vexs表示顶点向量;vexnum,arcnumf分别表示图的顶点数和弧数*/ArcNode arcsMAXMAX; /* 邻接矩阵 */AdjMatrix;
11、typedef struct(int adjvex;存放顶点编号int lowcost;存放顶点权值Node;Node closeMAX;/求最小生成树时的辅助数组int flag=0;int Locate(AdjMatrix *G ,int V) / 求顶点位置函数(int j=-1,k;for(k=0;kvexnum;k+)if(G-vexsk=V) (j=k;break;return j;专物耕悠窘祐课程设计说明书(论文)用纸AdjMatrix *creat(AdjMatrix *G) / 创立无向网int i,j,k,v1,v2,weight,m=1;printf(-请输入网中的顶点数
12、：);scanf(%d,&G-vexnum);if(G-vexnum=1)coutn*最小生成树不存在！*arcnum);for(i=0;ivexnum;i+) / 初始化邻接矩阵for(j=0;jvexnum;j+)if(i=j) G-arcsij.adj=0;else G-arcsij.adj=INFINIT;printf(请输入网中的顶点编号：);输入网中的顶点编号 for(i=0;ivexnum;i+)scanf(%d,&G-vexsi);printf(-输入每条弧所对应的两个顶点及权值 !n);for(k=0;karcnum;k+) cout请输入第m+v1v2weight;输入一条弧的两个顶点及权值i=Locate(Gv1);j=Locate(Gv2);G-arcsij.adj=weight;G-arcsji.adj=weight;return(G);int Minium(AdjMatrix *G ,Node close)/close中权值最小的边(int i,min,k;min=INFINIT;/ 置最小权值为 INFINITfor(i=0;ivexnum;i+)if(closei.lowcostvexsn+=u;closek
