最小生成树问题

最小生成树问题1.问题描述若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。2.需求分析1． 利用克鲁斯卡尔算法求网的最小生成树。2． 利用普里姆算法求网的最小生成树。3． 要求输出各条边及它们的权值。3.算法设计3.1算法思想通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机函数产生。图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。输出边时，输出所选择的边的起点和终点。Kruskal算法简介(适用于稀疏图)--按照边的权值大小排序,每次从剩余的边中选择权值较小且边的两个顶点不在同一个集合内的边加入到生成树中,直到加入n-1条边为止。Prim算法简介(适用于稠密图)--我们从1号顶点开始,找到与选过的点相连接的最短边,并且这条边可以连接到没有被选中的点.这样一直重复n-1次即可找到最小生成树。3.2数据结构逻辑结构:图结构3.3算法设计Kruskal算法—先将各个边进行排序，这里用到堆排序。堆排序:堆排序就是先将一个无序序列建成大根堆，然后反复进行交换和堆调整。建成大根堆:要将一个无序序列调整成堆，必须将其所对应的完全二叉树中的每一个结点为根的子树都调整成堆，只有一个结点的树比为堆，而在完全二叉树中，所有序号大于[n/2]的结点都是叶子，这些结点为根的子树都已经是堆。只要利用筛选法，从最后一个分支结点[n/2]开始，依次它之前的每一个分支结点作为根的子树都调整为堆即可。调整堆:现在如果要调整序号为s的结点，我们需要从r[2s]和r[2s+1]中选出关键字较大的一个，找到最大的之后和r[s]做比较。如果比根结点大，就和根结点交换，然后最大的那个下标的位置就是根，继续向下调整，直至进行到叶子结点为止。如果没有根结点大说明以r[s]为根的子树已经是堆，不必做任何调整。按照边的顺序进行选择，如果边的两个端点属于同一个祖先，那么说明这两个点已经都被选择过，不能再被选择了。那么怎么来判断两个点是否属于同一个祖先呢？这里就用到了并查集的知识。并查集:我们有一个数组，刚开始，他们都是等于他们的结点的值，我们在输入的时候，会输入一个边的起点，假如输入的是1，2，那么我们就修改f[2]的值让他等于f[1]，假如我们第二次输入的值是3，2，此时本来应该是还是修改f[2]的值，但是由于我们已经修改过了f[2]的值，那么我们就找到f[2]的祖先，让f[2]的祖先的值修改为f[3]。等到全部输入完了以后，我们就需要判断两个点是否属于同一个连通分量，我们就找这两个点的祖先是否是一样的，再找祖先的时候，中间经过的点都修改为祖先表示的值，这样在后面找的时候，就可以大大的降低时间复杂度。都建立好了以后，我们就可以按照3.1算法思想的方法进行边的选择。Prim算法—假设一个无向图G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，要求输出T的各条边。实现这个算法需要一个辅助数组，记录U到V-U具有最小权值的边和边的起点，只要我们更新最小边的时候，权值和边的起点都需要修改，直到把所有的点都选完。3.4函数之间的调用关系4.调试分析4.1调试中出现的问题及解决方案在用Prim算法的时候，由于需要输出边的两个端点，那么在记录已经选择的端点到未选择的端点最短距离时要记录下那一个最短距离的边是由哪一个端点得到的，刚开始我想的是，只要选择边就将i，j输出，当实现之后发现，输出完全是错误的，因为每次选择最小的边的时候，起点不一定是从已经选择的顶点中哪一个顶点得到的，后来我就用了一个结构体保存最小权值的边的起点和最小的权值。最后输出起点，当前正在枚举的点，以及最小权值。4.2优点及不足优点:使用并查集的时候，将一个属于一个祖先的结点的值都赋予相同的值，这样一来在查找的时候不用每一次都找到祖先，只要能够找到他们所表示的值相等即可。不足:没有将所有的算法写成函数，都写在了main函数中，所以代码显得特别乱，结构很不清晰。4.3算法的时空分析时间复杂度:Kruskal算法O(eloge)Prim算法O(v^2)4.4改进思路多使用函数令程序的结构更加清晰和美观。5.实验结果源代码#include<cstdio>#include<iostream>#defineinf0x3f3f3f3fusingnamespacestd;constintMax_e=1000;constintMax_v=30;intf[Max_v+1],v,e,count=0;intedge[Max_v][Max_v],book[Max_v];////book:标记点是否加入到生成树中,全局变量初始为0(未加入)edge:邻接矩阵structA{ intdistance;//distance:各个顶点到"生成树"的距离 intindex;//记录生成树中的点(起点)}dis[Max_v];structB{ intmmin1; intindex;}mmin;structE{ intst; intet; intw;}Edge[Max_e];/**打印信息*/voidPrintEdgeMes(){ cout<<""<<endl; cout<<"权值\t起点\t终点\t"<<endl; for(inti=1;i<=e;i++){ cout<<Edge[i].w<<"\t"<<Edge[i].st<<"\t"<<Edge[i].et<<"\t"<<endl; } cout<<""<<endl; cout<<endl;}/**交换两条边的信息*/voidSwap(inti,intj){ intst,et,w; st=Edge[i].st;Edge[i].st=Edge[j].st;Edge[j].st=st; et=Edge[i].et;Edge[i].et=Edge[j].et;Edge[j].et=et; w=Edge[i].w;Edge[i].w=Edge[j].w;Edge[j].w=w;}/**筛选法调整堆*/voidHeapAdjust(ints,intm){ //s根结点,m序列长度 Edge[0]=Edge[s];//保存根结点信息 for(inti=2*s;i<=m;i*=2){//沿着权值较大的孩子结点向下筛选 if(i<m&&Edge[i].w<Edge[i+1].w)i++; if(Edge[0].w>=Edge[i].w)break;//根结点的权值大于两个孩子,0号位置的信息应该在s位置上 Edge[s]=Edge[i];s=i;//否则0号位的信息应该在i,更新根结点,继续找他的左右堆,直到找到叶子结点,一次调整完毕 } Edge[s]=Edge[0];}/**建立大根堆*/voidCreatHeap(){ intn=e; //所有大于n/2的位置上都是叶子结点,我们从叶子最后一个非叶子结点筛选 for(inti=n/2;i>0;i--){ HeapAdjust(i,e);//不断的调整堆 } }/**对边进行排序(堆排序)*/voidHeapSort(){CreatHeap();//把无序序列建成大根堆for(inti=e;i>1;i--){ //1:堆顶元素的位置,i:未排序的最后一个 Swap(1,i);//将堆顶元素与没有排序(1-i)的的最后一个记录交换 HeapAdjust(1,i-1);//除了堆顶信息,剩下的继续调整为大根堆 }}/**找到第一个标记*/intgetf(intn){if(f[n]==n) returnn;else{ f[n]=getf(f[n]);//在找到最终的那个点之前遇到的点都"属于最终的那个点" returnf[n]; }}/**判断边的顶点是否属于一个连通分量*/intmerge(intst,intet){ intt1,t2; t1=getf(st); t2=getf(et); if(t1!=t2){//t1是否是一个连通分量 f[t1]=t2;//标记值都靠近左边的值 return1; } return0;}/*Kruskal算法简介(适用于稀疏图)按照边的权值大小排序,每次从剩余的边中选择权值较小且边的两个顶点不在同一个集合内的边加入到生成树中,直到加入n-1条边为止*/voidMiniSpanTree_Kruskal(){ //对边进行排序(堆排序) HeapSort(); //打印对边排序的结果 cout<<endl<<"对所有边排序(堆排序)的结果为:"<<endl; PrintEdgeMes(); for(inti=1;i<=v;i++) f[i]=i;//各顶点自成一个连通分量 //枚举边 cout<<"Kruskal算法选用的边极其权值为:"<<endl; cout<<""<<endl; cout<<"起点\t终点\t权值"<<endl; for(inti=1;i<=e;i++){ if(merge(Edge[i].st,Edge[i].et)){ count++; //检查这两个点是否在同一个集合中,如果不在返回1,就选用这条边 cout<<Edge[i].st<<"\t"<<Edge[i].et<<"\t"<<Edge[i].w<<"\t"<<endl; if(count==v-1)//选了n-1条边时退出循环 break; } } cout<<""<<endl;}/*Prim算法简介(适用于稠密图)我们从1号顶点开始,找到与选过的点相连接的最短边,并且这条边可以连接到没有被选中的点.这样一直重复n-1次即可找到最小生成树*/intmain(){ cout<<"Kruskal算法"<<endl<<endl; cout<<"请输入顶点数和边数:" ; cin>>v>>e; cout<<"请依次输入e条边及其权值:"<<endl; for(inti=1;i<=e;i++) cin>>Edge[i].st>>Edge[i].et>>Edge[i].w; MiniSpanTree_Kruskal(); cout<<endl<<""<<endl; cout<<">>Enter键进入Prim算法"<<endl; system("pause"); system("cls"); cout<<"Prim算法"<<endl<<endl; count=0;//加入到生成树中的顶点数置为0 cout<<"请输入顶点数和边数:" ; cin>>v>>e; for(inti=1;i<=v;i++){ for(intj=1;j<=v;j++){ if(i==j)edge[i][j]=0; elseedge[i][j]=inf; } } intst,et,w,j; cout<<"请依次输入e条边及其权值:"<<endl; for(inti=1;i<=e;i++){ cin>>st>>et>>w; edge[st][et]=w;//无向图 edge[et][st]=w; } //先把一号顶点加入到生成树中 for(inti=1;i<=v;i++){ dis[i].distance=edge[1][i]; dis[i].index=1;//目前记录的最短路径都是从1出发的 } book[1]=1; count++; cout<<endl<<"Prim算法选用的边及其权值为:"<<endl; cout<<""<<endl; cout<<"起点\t终点\t权值"<<endl; while(count<v){ mmin.mmin1=inf;//最短的边 for(inti=1;i<=v;i++){ if(book[i]==0&&dis[i].distance<mmin.mmin1){ mmin.mmin1=dis[i].distance;j=i;//新加入的顶点 mmin.index=dis[i].index; } } cout<<mmin.index<<"\t"<<j<<"\t"<<m