中国数学建模-编程交流-贪婪算法 ├数学思想 ├编程交流 ├学术杂谈 ├English Fans wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> VC++,C,Perl,Asp...编程学习,算法介绍. 我的收件箱 (0) 中国数学建模 → 学术区 → 编程交流 → 贪婪算法 您是本帖的第 890 个阅读者 * 贴子主题：贪婪算法 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 11 楼 1.3.6 最小耗费生成树 在例 1 - 2 及 1 - 3 中已考察过这个问题。因为具有 n 个顶点的无向网络 G 的每个生成树刚好具有 n-1 条边，所以问题是用某种方法选择 n-1 条边使它们形成 G 的最小生成树。至少可以采用三种不同的贪婪策略来选择这 n-1 条边。这三种求解最小生成树的贪婪算法策略是： K r u s k a l 算法，P r i m 算法和 S o l l i n 算法。 1. Kruskal 算法 (1) 算法思想 K r u s k a l 算法每次选择 n- 1 条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l 算法分 e 步，其中 e 是网络中边的数目。按耗费递增的顺序来考虑这 e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 考察图 1-12a 中的网络。初始时没有任何边被选择。图 13-12b 显示了各节点的当前状态。边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图 1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树中（如图 1 3 - 1 2 d 所示）。然后考虑边( 2，7 )，将它加入树中并不会产生环路，于是便得到图 1 3 - 1 2 e。下一步考虑边（ 2，3）并将其加入树中（如图 1 3 - 1 2 f 所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（ 5，4）加入树中，得到的树如图 13-12g 所示。下一步考虑边（ 7，5），由于会产生环路，将其丢弃。最后考虑边（ 6，5）并将其加入树中，产生了一棵生成树，其耗费为 9 9。图 1 - 1 3 给出了K r u s k a l 算法的伪代码。 / /在一个具有 n 个顶点的网络...
