一种求解最小生成树问题的算法

• 作者: 刘三阳 孙小军 王志强
• 来源期刊: 计算机工程
• 学科: 数学
• 关键词: 最小生成树 节点合并 反向追踪 前点标号数组 邻接矩阵
• 年，卷（期）: 2011,（23）
• 所属期刊栏目: 开发研究与设计技术
• 页码范围: 241-243,247
• 分类号: O224
• 字数: 3034字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2011.23.082

摘要

基于节点合并和反向追踪的思想,提出一种求解最小生成树问题的算法.该算法依据网络邻接矩阵,将与源节点相邻的节点逐步合并为新的源节点,使网络中的所有节点合并为一个点,借助引入的前点标号数组得到网络的最小生成树,对算法正确性与算法复杂度进行分析.将该算法应用于某高速公路网工程建设方案,结果证明了算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘三阳	西安电子科技大学理学院	662	5562	32.0	51.0
2	孙小军	宝鸡文理学院数学系	57	242	9.0	11.0
3	王志强		9	32	4.0	5.0