《计算机仿真》期末大作业
Prim 算法和 Kruskal 算法的 Matlab 实现
05605 刘禹 050697（30）
连线问题应用举例：
欲铺设连接 个城市的高速公路，若 城与 城之间的高速公路造价为 ，试
设计一个线路图，使总的造价最低。
连线问题的数学模型就是图论中在连通的赋权图上求权最小的支撑树。试用
Matlab 分别实现求最小支撑数的 Prim 算法和 Krusal 算法（避圈法）。
一.基本要求：
（1） 画出程序流程图；
（2） 对关键算法、变量和步骤进行解释说明；
（3） 用如下两图对所写算法的正确性进行验证。即输入图的信息，输出对应图
的最小支撑树及其权值。
（4）分析两种算法的实现复杂度。
二.扩展要求：
（1）提供对算法效率（复杂度）进行评估的方法，并通过举例验证，与分析得到的算
法复杂度结果相对照；
（2）从降低内存消耗、减少计算时间的角度，对算法进行优化。
三．实验步骤
I.用 Prim 算法求最小生成树
i．算法分析及需求分析，程序设计
prim 算法的基本思想是：设 G=（V，E）是一个无向连通网，令 T=（U，TE）是 G 的
最小生成树。T 的初始状态为 U={v0}（v0 ）TE={}，然后重复执行下述操作：在所有 u
U，
v V-U 的边中找一条代价最小的边（u，v）并入集合 TE，同时 v 并入 U，直至 U=V
1 / 14
剩余13页未读，继续阅读
评论6