《数据结构-kruskal算法求最小生成树_实验报告》由会员分享，可在线阅读，更多相关《数据结构-kruskal算法求最小生成树_实验报告（10页珍藏版）》请在金锄头文库上搜索。
1、一、 问题简述题目：图的操作。要求：用 kruskal 算法求最小生成树。最短路径： 输入任意源点，求到其余顶点的最短路径。输入任意对顶点，求这两点之间的最短路径和所有路径。二、 程序设计思想首先要确定图的存储形式。经过的题目要求的初步分析，发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。其次是 kruskal 算法。该算法的主要步骤是：GENERNIC-MIT(G,W)1. A2. while A 没有形成一棵生成树3 do 找出 A 的一条安全边(u,v);4. AA(u,v);5. return A算法设置了集合
2、 A，该集合一直是某最小生成树的子集。在每步决定是否把边(u,v)添加到集合 A 中，其添加条件是 A(u,v)仍然是最小生成树的子集。我们称这样的边为 A的安全边，因为可以安全地把它添加到 A 中而不会破坏上述条件。然后就是 Dijkstra 算法。Dijkstra 算法基本思路是：假设每个点都有一对标号 (d j, pj)，其中 dj是从起源点 s 到点 j 的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；p j则是从 s 到 j 的最短路径中 j 点的前一点。求解从起源点 s 到点 j 的最短路径算法的基本过程如下：1) 初始化。起源点设置为： d s=
3、0, ps为空; 所有其他点: d i=, p i=?; 标记起源点 s，记 k=s,其他所有点设为未标记的。2) 检验从所有已标记的点 k 到其直接连接的未标记的点 j 的距离，并设置：dj=mind j, dk+lkj式中，l kj是从点 k 到 j 的直接连接距离。3) 选取下一个点。从所有未标记的结点中，选取 dj 中最小的一个 i：di=mind j, 所有未标记的点 j点 i 就被选为最短路径中的一点，并设为已标记的。4) 找到点 i 的前一点。从已标记的点中找到直接连接到点 i 的点 j*，作为前一点,设置：i=j*5) 标记点 i。如果所有点已标记，则算法完全推出，否则，记 k
4、=i，转到 2) 再继续。而程序中 求两点间最短路径算法。其主要步骤是：调用 dijkstra 算法。将 path 中的第“终点”元素向上回溯至起点，并显示出来。程序结构框图为：41 2 3Begin输入顶点数 n输入边数 e输入边集显示菜单，等待选择 endKru-skal算法Dij-kstra算法求两点间最短距离三、 程序具体实现1、 kruskal 函数：因为 kruskal 需要一个有序的边集数组，所以要先对边集数组排序。其次，在执行中需要判断是否构成回路，因此还另有一个判断函数 seeks，在 kruskal 中调用 seeks。2、 dijkstra 函数：因为从一源到其余各点的最
5、短路径共有 n-1 条，因此可以设一变量 vnum 作为计数器控制循环。该函数的关键在于 dist 数组的重新置数。该置数条件是：该顶点示被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为：if（sw=0&costuw+distu0) i=seti;return i;kruskal(edgeset ge,int n,int e)int setMAXE,v1,v2,i,j;for(i=1;in+1;i+) seti=0;i=1;j=1;while(j=e&i=n-1)v1=seeks(set,gej.bv);v2=seeks(set,gej.tv);if(v
6、1!=v2)printf(%d,%d):%dn,gej.bv,gej.tv,gej.w);setv1=v2;i+;j+;void insertsort(edgeset ge,int e)int i,j;for(i=2;i=e;i+)if(gei.wgei-1.w)ge0=gei;j=i-1;while(ge0.wgej.w)gej+1=gej;j-;gej+1=ge0;void dijkstra(int costMAXEMAXE,int distMAXE,int pathMAXE,int sMAXE,int n,int v0)int u,vnum,w,wm;for(w=1;w=n;w+)dis
7、tw=costv0w;if(costv0w32767)pathw=v0;vnum=1;while(vnum=n-1) wm=32767;u=v0;for(w=1;w=n;w+)if(sw=0&distwwm)u=w;wm=distw;su=1;vnum+;for(w=1;w=n;w+)if(sw=0&distu+costuwdistw&costuw!=32767)distw=distu+costuw;pathw=u;void printpath1(int dist,int path,int s,int n,int v0)int i,k;for(i=1;i=n;i+)if(si=1)k=i;wh
8、ile(k!=v0)printf(%d-,k);k=pathk;printf(%d:%dn,k,disti);elseprintf(%d-%d:32767n,i,v0);void printpath2(int dist,int path,int v0,int v1)int k;k=v1;while(k!=v0)printf(%d-,k);k=pathk;printf(%d:%dn,k,distv1);main()edgeset geMAXE;int costMAXEMAXE,distMAXE,pathMAXE,sMAXE,a,n,e,i,j,k,v0,v1;printf(input the n
9、umber of point:); scanf(%d,&n);printf(input the number of edges:);scanf(%d,&e);printf(input the edges:n);for(i=1;i=e;i+)scanf(%d,%d,%d,&gei.bv,&gei.tv,&gei.w);printf(please choisen);printf(1.kruskaln );printf(“2.shortpathn”);printf(“3.shortpath between two pointn”);printf(“4.exitn”);scanf(%d,&a);whi
10、le(a!=4)switch(a)case 1:insertsort(ge,e);kruskal(ge,n,e);break;case 2:printf(input the start point:);scanf(%d,&v0);for(i=1;i=n;i+)for(j=1;j=n;j+)costij=32767;for(k=1;k=e;k+)i=gek.bv;j=gek.tv;costij=gek.w;for(i=1;i=n;i+)si=0;sv0=1;dijkstra(cost,dist,path,s,n,v0);printpath1(dist,path,s,n,v0);break;cas
11、e 3:printf(input the start point:);scanf(%d,&v0);printf(input the end point:);scanf(%d,&v1);for(i=1;i=n;i+)for(j=1;j=n;j+)costij=32767;for(k=1;k=e;k+)i=gek.bv;j=gek.tv;costij=gek.w; for(i=1;i=n;i+)si=0;sv0=1;dijkstra(cost,dist,path,s,n,v0);printpath2(dist,path,v0,v1);break;printf(please choisen);pri
12、ntf(1.kruskaln );printf(“2.shortpathn”);printf(“3.shortpath between two pointn”);printf(“4.exitn”);scanf(%d,&a);五、 程序调试将如下图输入：6 5 1 5 5 3 6 4 2 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_树中，画出插入过程，然后依次删除每个元素，画出删除过程。平衡树插入过程如下所示：3 3 3 3 7 2 7 2 7 1 3 3 3 2 7 2 7 LR 2 6 1 4 1 4 1 4 7 6 3 3 3 2 6 2 6 RR 2 6 1 4 7 1 4 7 1 4 8 8 8
