1、 目录目录 一、问题描述一、问题描述 1 二、需求分析与设计二、需求分析与设计.1 1、 基本信息（包括顶点数、边数、权值等） 。 1 2、 实现功能（城市之间距离、最小距离、最大值等） 。. 1 三、两种算法比较三、两种算法比较 .1 （一） 、普里姆（PRIM)算法:. 1 （二） 、 克鲁斯卡（KRUSKAL)算法: . 1 四、四、 算法的设计思想算法的设计思想.1 求图的最小生成树主要有两种方法： 1 (一） 、算法的相同点： . 1 （二） 、算法的不同点： 2 六、总结六、总结 .4 七七 源代码源代码 .5 1 最小生成树最小生成树 一、问题描述一、问题描述 为了解决在 n 个
2、城市之间建设网络，但需要保证连通，求最经济的架 设方法；因此利用了最小生成树的两种算法 Prim 算法和 kruskal 算法， 从而 来解决此问题。 二、需求分析与设计二、需求分析与设计 可以计算出两城市之间的距离、可以计算出城市之间最小距离。 1、 基本信息（包括顶点数、边数、权值等） 。 2、 实现功能（城市之间距离、最小距离、最大值等） 。 三、两种算法比较三、两种算法比较 （一）、普里姆（Prim)算法: 普利姆算法的时间复杂度为 O（n 2),与网中的边数无关因此适用于求 边稠密的网的最小生成树。 （二） 、 克鲁斯卡（Kruskal)算法: 克鲁斯卡算法恰恰相反，它的时间复杂度为
3、 O（eloge)(e 为网中的边 的数目） 。因此它适用稀疏的网的最小生成树。 四、四、算法的设计思想算法的设计思想 求图的最小生成树主要有两种方法： 1. 普里姆算法; 2.克鲁斯卡算法。 (一） 、算法的相同点：一） 、算法的相同点： 都利用了顶点集和中顶点的最小值；都有一出发点；每次都 2 是选出最小的值并入中以作为过渡顶点，而不再求其最小；都涉及最短 问题；它们都是从一个原始顶点开始将顶点一个个按一定顺序转移到所求 终点中都用到了辅助向量；都从顶点出发，并在过程中都依据了顶点；都 包含其顶点连通分量；都是对网进行操作；用找到的路径将顶点连接起来 都是树。 （二） 、算法的不同点：（二
4、） 、算法的不同点： 普里姆算法从顶点集 U 中任一顶点出发到 VU 中顶点， 迪杰斯特拉算 法从源点出发通过顶点到找到中顶点的最小值；普里姆算法的出 发点是算法的开始点；而迪杰斯特拉算法的出发点是求最短路径的源点； 普里姆算法用 lowcost 数组，而迪杰斯特拉算法用 j =MinD i |vi 属于顶点集普里姆算法解决最小生成树，迪杰斯特拉算法解决最短 路径；普里姆算法是顺着已找到的顶点找其余应并入中的顶点，而迪杰 斯特拉算是顺着顶点去找其余顶点到源点的最短路径；普里姆算法的最短 是两个顶点集间的最短，而迪杰斯特拉算法的最短是某点通过一个顶点集 到源点的最短。普里姆算法的最短是两个顶点间
5、的最短，而迪杰斯特拉 算法的最短是某点到源点的最短。普法无需按最短的并入，它寻找并入 U 的点的依据是在 U 和 V-U 之间的最短路径。迪法在找到最短路径后，还要 对其余结点的当前最短路径进行修改，而普法则不进行修改。普法是从顶 点集的思路出发，而迪法则是按路径长度递增思路出发。普法的出发点是 任意的，而迪法的出发点是规定的。 普法在执行过程中不改变两点间的权值，而迪法在执行过程中会求出一个 或者是两点的权值或者是权值之和作为最短的路径；迪法具有方向性，而 3 普法则可以不具有. 五、五、系统测试系统测试 /*建立图的邻接矩阵*/ void CreatMatrix(adjmatrix GA) int i,j,k,e; printf(“图中有%d 个顶点n“,n); for(i=1;i0;-q) HeadAdjust(H,q,H.Elength); for(q=H.Elength;q1;-q) rb=H.space1; H.space1=H.spaceq; H.spaceq=rb; HeadAdjust(H,1,q-1); void main() int q; do printf(“*
