《Prim算法最小生成树(C语言)》由会员分享，可在线阅读，更多相关《Prim算法最小生成树(C语言)（4页珍藏版）》请在金锄头文库上搜索。
1、最小生成树一 目的给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计 算得到的最小生成树的代价。二 需求分析（1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课 本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义 的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路， 并显示得到的最小生成树的代价；（2）表示城市间距离网的邻接矩阵（要求至少 6个城市， 10条边）；并且 利用文件对数据进行提取。（3）输出最小生成树中包括的边及其权值，并显示得到的最小生成树的代 价。（4）采用模块化设计；三 概要设计1、相关定义以及算法概述（1
2、）最小生成树的定义： 假设一个单位要在 n 个办公地点之间建立通信 网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点 以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的 线路，赋于边的权值表示相应的代价。对于 n 个顶点的连通网可以建立许多不 同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最 少，即边的权值之和最小的生成树，称为最小生成树。（2）普里姆（Prim）算法即是利用MST性质构造最小生成树的算法。算法 思想如下：假设N=（V,E）和是连通网，TE是N上最小生成树中边的集合。算 法从U=u0（ u0eV），TE=开始，重复执行下
3、述操作：在所有uU，vV-U 的边（u, v） e E中找一条代价最小的边（u0, v0）并入集合TE，同时vO并入 U，直到U=V为止。此时TE中必有n-1条边，则T=（V,TE）为N的最小生成 树。2、函数设计函数名函数参数返回值功能main无无系统主函数 输入路径信息Prim无向图邻接矩阵 路径数目代价Prim算法实现四 详细设计1、mian 函数mian 函数是一个程序的入口和出口，在我的课程设计中，输入城市和城市 间的路径以及各条路径的信息生成所输入信息的邻接矩阵是在主函数实现。如果两城市为同一城市或者两城市之间无通路路径，则在邻接矩阵中用整形最大值 MAXCOST （0x7ffff
4、fff表示。例如：ABCAMAXCOST23B2MAXCOST1C31MAXCOST流程： 初始化所有路径为无穷大 获取城市和城市间通路路径的数目 获取边信息 将边信息对称存储在二维数组里，则形成邻接矩阵 求解最小生成树（调用Prim函数） 输出最小权值和2、Prim 函数Prim 函数的功能用于 Prim 算法的实现，也就是求解最小树并返回该最小生 成树的总代价。在函数中：数组 BianQuan 记录以 i 为终点的边的最小权值，当 BianQuani=0 时表示 终点 i 加入生成树数组QiDian记录对应BianQuani的起点，当QiDiani=O时表示起点i 加入生成树。流程： 默认
5、选择 1 号节点加入生成树，找出与它的所有通路，更新相应数组。 找出最小边权的路径进行输出，更新相应数组。 把步骤输出的路径的终点作为新的起点，找到他所有通路（不包括 已经加入生成树的结点），更新相应数组。 同步骤 跳转到步骤，直到所有结点都加入生成树。 返回代价，结束。五 调试分析起初在编写程序时，没考虑城市与城市之间无通路的情况，导致当程序输 入数据中每个城市都对每个城市有通路时运行正常，而当输入数据某个城市对 某个城市之间无通路时运行错误，通过请教其他同学，我发现了这个问题，并 通过在建立邻接矩阵时初始化所有路径为最大值解决了它。六 测试结果假设有一城市分布图如下图输入数据:7 11A B 7A D 5B C 8B D 9B E 7C E 5D E 15D F 6E F 8E G 9F G 11输出:A - D : 5D - F : 6A - B : 7B - E : 7E - C : 5E - G : 9Total:39七 用户使用说明八 课程设计总结 本次课程设计实验过程中遇到了很多问题，但通过多次 调试最终得到解 决。并且通过本次课设，我掌握了 Prim 算法的实现最小生成树的方法，对我在 课堂上学的知识进一步加深；另外通过编写此程序，我感受到了数据结构的重 要性，作为一名程序员数据结构是必不可少的。
