搜索
1、问题简述题目：图的操作。要求：用kruskal算法求最小生成树。最短路径：①输入任意源点，求到其余顶点的最短路径。②输入任意对顶点，求这两点之间的最短路径和所有路径。2、程序设计思想首先要确定图的存储形式。经过的题目要求的初步分析，发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。其次是kruskal算法。该算法的主要步骤是：GENERNIC-MIT(G,W)1.A←2.whileA没有形成一棵生成树3do找出A的一条安全边(u,v);4.A←A∪{(u,v)};5.returnA算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边(u,v)添加到集合A中，其添加条件是A∪{(u,v)}仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。然后就是Dijkstra算法。Dijkstra算法基本思路是：假设每个点都有一对标号(dj,pj)，其中dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下： 1)初始化。起源点设置为：①ds=0,ps为空;②所有其他点:di=∞,pi=?;③标记起源点s，记k=s,其他所有点设为未标记的。 2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：dj=min［dj,dk+lkj］式中，lkj是从点k到j的直接连接距离。 3)选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：di=min［dj,所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。 4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2)再继续。而程序中求两点间最短路径算法。其主要步骤是：1调用dijkstra算法。2将path中的第“终点”元素向上回溯至起点，并显示出来。程序结构框图为：Begin输入顶点数n输入边数e输入边集显示菜单，等待选择end4123求两点间最短距离Dij-kstra算法Kru-skal算法3、程序具体实现1、kruskal函数：因为kruskal需要一个有序的边集数组，所以要先对边集数组排序。其次，在执行中需要判断是否构成回路，因此还另有一个判断函数seeks，在kruskal中调用seeks。2、dijkstra函数：因为从一源到其余各点的最短路径共有n-1条，因此可以设一变量vnum作为计数器控制循环。该函数的关键在于dist数组的重新置数。该置数条件是：该顶点示被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为：if（s[w]==0&&cost[u][w]+dist[u]dist[w]）。但是在实际运行中，发现有些路径的权值为负。经过分析发现，因为在程序中∞由32767代替。若cost[u][w]==32767，那么cost[u][w]+dist[u]肯定溢出主负值，因此造成权值出现负值。但是如果cost[u][w]==32767，那么dist[w]肯定不需重新置数。所以将条件改为：if（s[w]==0&&cost[u][w]+dist[u]dist[w]&&cost[u][w]!=32767）。修改之后，问题果然解决。3、printpath1函数：该函数主要用来输出源点到其余各点的最短路径。因为在主函数调用该函数前，已经调用了dijkstra函数，所以所需的dist、path、s数组已经由dijkstra函数生成，因此在该函数中，只需用一变量控制循环，一一将path数组中的每一元素回溯至起点即可。其关键在于不同情况下输出形式的不同。4、printpath2函数：该函数主要用来输出两点间的最短路径。其主要部份与printpath1函数相同，只是无需由循环将所有顶点一一输出，只需将path数组中下标为v1的元素回溯至起点并显示出来。4、源程序#defineMAXE100structedges{intbv;inttv;intw;};typedefstructedgesedgeset;intseeks(intset[],intv){inti;i=v;while(set[i]0)i=set[i];returni;}kruskal(edgesetge[],intn,inte){intset[MAXE],v1,v2,i,j;for(i=1;in+1;i++)set[i]=0;i=1;j=1;while(j=e&&i=n-1){v1=seeks(set,ge[j].bv);v2=seeks(set,ge[j].tv);if(v1!=v2){printf((%d,%d):%d\n,ge[j].bv,ge[j].tv,ge[j].w);set[v1]=v2;i++;}j++;}}voidinsertsort(edgesetge[],inte){inti,j;for(i=2;i=e;i++)if(ge[i].wge[i-1].w){ge[0]=ge[i];j=i-1;while(ge[0].wge[j].w){ge[j+1]=ge[j];j--;}ge[j+1]=ge[0];}}voiddijkstra(intcost[MAXE][MAXE],intdist[MAXE],intpath[MAXE],ints[MAXE],intn,intv0){intu,vnum,w,wm;for(w=1;w=n;w++){dist[w]=cost[v0][w];if(cost[v0][w]32767)path[w]=v0;}vnum=1;while(vnum=n-1){wm=32767;u=v0;for(w=1;w=n;w++)if(s[w]==0&&dist[w]wm){u=w;wm=dist[w];}s[u]=1;vnum++;for(w=1;w=n;w++)if(s[w]==0&&dist[u]+cost[u][w]dist[w]&&cost[u][w]!=32767){dist[w]=dist[u]+cost[u][w];path[w]=u;}}}voidprintpath1(intdist[],intpath[],ints[],intn,intv0){inti,k;for(i=1;i=n;i++)if(s[i]==1){k=i;while(k!=v0){printf(%d-,k);k=path[k];}printf(%d:%d\n,k,dist[i]);}elseprintf(%d-%d:32767\n,i,v0);}voidprintpath2(intdist[],intpath[],intv0,intv1){intk;k=v1;while(k!=v0){printf(%d-,k);k=path[k];}printf(%d:%d\n,k,dist[v1]);}main(){edgesetge[MAXE];intcost[MAXE][MAXE],dist[MAXE],path[MAXE],s[MAXE],a,n,e,i,j,k,v0,v1;printf(inputthenumberofpoint:);scanf(%d,&n);printf(inputthenumberofedges:);scanf(%d,&e);printf(inputtheedges:\n);for(i=1;i=e;i++)scanf(%d,%d,%d,&ge[i].bv,&ge[i].tv,&ge[i].w);printf(pleasechoise\n);printf(1.kruskal\n);printf(“2.shortpath\n”);printf(“3.shortpathbetweentwopoint\n”);printf(“4.exit\n”);scanf(%d,&a);while(a!=4){switch(a){case1:insertsort(ge,e);kruskal(ge,n,e);break;case2:printf(inputthestartpoint:);scanf(%d,&v0);for(i=1;i=n;i++)for(j=1;j=n;j++)cost[i][j]=32767;for(k=1;k=e;k++){i=ge[k].bv;j=ge[k].tv;cost[i][j]=ge[k].w;}for(i=1;i=n;i++)s[i]=0;s[v0]=1;dijkstra(cost,dist,path,s,n,v0);printpath1(dist,path,s,n,v0);break;case3:printf(inputthestartpoint:);scanf(%d,&v0);printf(inputtheendpoint:);scanf(%d,&v1);for(i=1;i=n;i++)for(j=1;j=n;j++)cost[i][j]=32767;for(k=1;k=e;k++){i=ge[k].bv;j=ge[k].tv;cost[i][j]=ge[k].w;}for(i=1;i=n;i++)s[i]=0;s[v0]=1;dijkstra(cost,dist,path,s,n,v0);printpath2(dist,path,v0,v1);break;}printf(pleasechoise\n);printf(1.kruskal\n);printf(“2.shortpath\n”);printf(“3.shortpathbetweentwopoint\n”);printf(“4.exit\n”);scanf(%d,&a);}}5、程序调试将如下图输入：①65②1④55③3642⑤6⑥依次输入：6（六个顶点）10（十条边）1，2，61，3，11，4，52，3，52，5，33，4，53，5，63，6，44，6，25，6，6显示菜单。选择1输出：（1，3）：1（4，6）：2（2，5）：3（3，6）：4（2，3）：5选择2输入1（起点）输出：1：327672-1:63-1:14-1:55-3-1:76-3-1:5选择3输入1(起点)5(终点)输出:5-3-1:7选择4退出。六、附录将序列3，7，2，1，4，6，8，9，10，5插入到初始为空的平衡树和3阶B_树中，画出插入过程，然后依次删除每个元素，画出删除过程。平衡树插入过程如下所示：33337272713332727LR26141414763332626RR261471471488879933326RR282814816916979471047101056RL3824791510平衡树删除过程如下所示：6删36删763828282479147914915105105106删266RR2919LR491481048101581055删16删46删654959958108108108删859RL599RR5101010删95删105删510B-树的插入过程如下所示：插入33插入737插入23插入1327127插入43插入636插入8361247124712478插入96插入1063838124791247910插入563812457910