数据结构-kruskal算法求最小生成树_实验报告.docVIP

问题简述 题目：图的操作。 要求：用kruskal算法求最小生成树。 最短路径： ①输入任意源点，求到其余顶点的最短路径。 ②输入任意对顶点，求这两点之间的最短路径和所有路径。 程序设计思想 首先要确定图的存储形式。经过的题目要求的初步分析，发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。 其次是kruskal算法。该算法的主要步骤是： GENERNIC-MIT(G,W) 1. A←? 2. while A没有形成一棵生成树 3 do 找出A的一条安全边(u,v); A←A∪{(u,v)}; return A 算法设置了集合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) 再继续。 4 1 2 3 程序具体实现 kruskal函数： 因为kruskal需要一个有序的边集数组，所以要先对边集数组排序。其次，在执行中需要判断是否构成回路，因此还另有一个判断函数seeks，在kruskal中调用seeks。 dijkstra函数： 因为从一源到其余各点的最短路径共有n-1条，因此可以设一变量vnum作为计数器控制循环。该函数的关键在于dist数组的重新置数。该置数条件是：该顶点示被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为：if（s[w]==0cost[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]==0cost[u][w]+dist[u]dist[w]cost[u][w]!=32767）。 修改之后，问题果然解决。 printpath1函数： 该函数主要用来输出源点到其余各点的最短路径。因为在主函数调用该函数前，已经调用了dijkstra函数，所以所需的dist、path、s数组已经由dijkstra函数生成，因此在该函数中，只需用一变量控制循环，一一将path数组中的每一元素回溯至起点即可。其关键在于不同情况下输出形式的不同。 printpath2函数： 该函数主要用来输出两点间的最短路径。其主要部份与printpath1函数相同，只是无需由循环将所有顶点一一输出，只需将path数组中下标为v1的元素回溯至起点并显示出来。 源程序 #define MAXE 100 struct edges {int bv; int tv; int w; }; typedef struct edges edgeset; int seeks(int set[],int v) {int i; i=v; while(set[i]0) i=set[i]; return i; } kruskal(edgeset ge[],int n,int e) {int set[MAXE],v1,v2,i,j; for(i=1;in+1;i++