一种基于二进制编码的最小生成树算法

• 作者: 王防修
• 来源期刊: 武汉工业学院学报
• 学科: 数学
• 关键词: 最小生成树 连通图 二进制编码 染色体 算法
• 年，卷（期）: 2012,（1）
• 所属期刊栏目: 信息与控制工程
• 页码范围: 39-42
• 分类号: O157.5
• 字数: 2892字
• 语种: 中文
• DOI: 10.3969/j.issn.1009-4881.2012.01.010

摘要

针对目前的最小生成树算法只能求一个最小生成树问题,提出一种新的最小生成树算法.该算法主要采用二进制编码的方式,并结合最小生成树的特点,通过先判断图的边数淘汰一些非生成树,然后通过判断连通性再淘汰一些非生成树,最后从所有的生成树中找到所有最小生成树.由于算法的本质就是在全局范围内寻找最优,故该算法可以找到一个连通图的所有最小生成树.算例表明,该算法具有步骤清晰、方便程序实现、通用性好的特点.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王防修	武汉工业学院数学与计算机学院	20	78	5.0	8.0