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

doi:10.3969/j.issn.1000-3428.2011.23.082

计算机工程 ›› 2011, Vol. 37 ›› Issue (23): 241-243. doi: 10.3969/j.issn.1000-3428.2011.23.082

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

孙小军 ¹，刘三阳 ²，王志强 ³

(1. 宝鸡文理学院数学系，陕西宝鸡 721013；2. 西安电子科技大学理学院，西安 710071；3. 总装备部驻天水地区军事代表室，陕西宝鸡 721006)

收稿日期:2011-07-15 出版日期:2011-12-05 发布日期:2011-12-05
作者简介:孙小军(1978－)，男，副教授、硕士，主研方向：网络优化；刘三阳，教授、博士生导师；王志强，硕士
基金资助:
陕西省教育厅专项科研计划基金资助项目(11JK0509)；宝鸡文理学院基金资助重点项目(ZK0931)

Algorithm for Solving Minimum Spanning Tree Problem

SUN Xiao-jun ¹, LIU San-yang ², WANG Zhi-qiang ³

(1. Dept. of Mathematics, Baoji University of Arts and Sciences, Baoji 721013, China; 2. School of Science, Xidian University, Xi’an 710071, China; 3. General Armament Department Military Representative Office in Tianshui Region, Baoji 721006, China)

Received:2011-07-15 Online:2011-12-05 Published:2011-12-05

摘要/Abstract

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

关键词: 最小生成树, 节点合并, 反向追踪, 前点标号数组, 邻接矩阵

Abstract: This paper presents an algorithm for solving Minimum Spanning Tree(MST) problem based on the node combination and reverse direction tracing method. According to the adjacent matrix, the source node and the adjacent nodes are combined into new source node repeatedly and all the nodes in the network are combined into one single node. By introducing the front point label array, it gets the MST. The correctness and complexity of the algorithm are analyzed. It applies the algorithm to the highway system engineering construction plan, the results prove the validity of the algorithm.

Key words: Minimum Spanning Tree(MST), node combination, reverse direction tracing, front point label array, adjacent matrix

中图分类号:

O224

孙小军, 刘三阳, 王志强. 一种求解最小生成树问题的算法[J]. 计算机工程, 2011, 37(23): 241-243.

SUN Xiao-Jun, LIU San-Yang, WANG Zhi-Jiang. Algorithm for Solving Minimum Spanning Tree Problem[J]. Computer Engineering, 2011, 37(23): 241-243.

http://www.ecice06.com/CN/Y2011/V37/I23/241

参考文献

[1] Jark A, Orlinjb M. Network Flows: Theory, Algorithms, and Applications[M]. 北京: 电子工业出版社, 2005.
[2] Kruskal J. On the Shortest Spanning Subtree of a Graph and the Traveling Sales Man Problem[J]. Proceedings of the AMS, 1956, 7(1): 48-50.
[3] Prim R C. Shortest Connection Networks and Some Genera- tions[J]. Bell System Technical Journal, 1957, 36(6): 1389-1401.
[4] Sollin M, Le Trace de Canalisation. Programming, Games, and Transportation Networks[M]. New York, USA: John Wiley & Sons, Inc., 1965.
[5] Dijkstra E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik, 1959, (1): 269-271.
[6] 孙凌宇, 冷明, 谭云兰, 等. 赋权有向图的最小生成树算法[J]. 计算机工程, 2010, 36(2): 61-63.
[7] Richard L J. DNA Solution of Hard Computation Problems[J]. Science, 1995, 268(28): 542- 545.
[8] Liu Xikui, Li Yan, Xu Jin. Solving Minimum Spanning Tree Problem with DNA Computing[J]. Journal of Electronics, 2005, 22(2): 112-117.
[9] Raidl G R, Julstrom B A. Edge Sets: An Effective Evolutionary Coding of Spanning Trees[J]. IEEE Trans. on Evolutionary Computation, 2003, 7(3): 225- 239.
[10] Neumann F, Wegener I. Randomized Local Search, Evolutionary Algorithms, and the Minimum Spanning Tree Problem[J]. Theoretical Computer Science, 2007, 378(1): 32- 40.
[11] Neumann F, Witt C. Ant Colony Optimization and the Minimum Spanning Tree Problem: Learning and Intelligent Optimiza- tion[C]//Proc. of the 2nd International Conference. Berlin, Germany: Springer-Verlag, 2007.
[12] 吕欣, 李勇, 邓宏钟, 等. 基于节点合并的最短路问题新算法[J]. 小型微型计算机系统, 2009, 30(4): 695-699.
[13] 谢政. 网络算法与复杂性理论[M]. 长沙: 国防科学技术大学出版社, 2003.

[1]	王智铎, 江波, 苗瑞, 赵慧. 基于有向图的外键冲突解决算法设计与实现[J]. 计算机工程, 2021, 47(2): 254-260.
[2]	杨罡, 晋涛, 王大伟, 曹京津, 张娜, 严碧武, 李涛, 程远. 改进的代价聚集快速立体匹配算法[J]. 计算机工程, 2019, 45(7): 268-272,281.
[3]	吴娟,陈丽芳. 基于慢特征分析的智能拼图算法[J]. 计算机工程, 2019, 45(2): 207-212.
[4]	王魁,马宏,黄瑞阳. 基于重要节点删除法的社会网络层次结构分析[J]. 计算机工程, 2018, 44(5): 174-181,187.
[5]	吴亚锋,谭文安. 基于邻接矩阵的业务流程间距离计算方法[J]. 计算机工程, 2018, 44(4): 52-58.
[6]	李玉龙,刘任任,赵津锋,臧浪,曹斌. 分簇感知网络中基于压缩感知的数据收集方法[J]. 计算机工程, 2018, 44(10): 129-135.
[7]	韩毅,赵凯,周晏. 基于分数阶变换和改进最小生成树的图像配准算法[J]. 计算机工程, 2017, 43(9): 263-269.
[8]	刘海客,李集林,尤启迪,张华健. 一种OpenFlow网络的动态负载均衡方法[J]. 计算机工程, 2016, 42(8): 85-90.
[9]	任亮,徐志刚,赵祥模,周经美. 基于Prim最小生成树的路面裂缝连接算法[J]. 计算机工程, 2015, 41(1): 31-36.
[10]	吴拥民, 张斌. 虚拟场景中有宽度物体移动路径的优化方法[J]. 计算机工程, 2014, 40(10): 308-313.
[11]	汤进, 陈影, 江波, 罗斌. 基于复杂网络的图像建模与特征提取方法[J]. 计算机工程, 2013, 39(5): 243-247,252.
[12]	徐沁，罗斌. 结合mean-shift与MST的K-means聚类算法[J]. 计算机工程, 2013, 39(12): 204-210.
[13]	唐德权, 谭阳. 一种频繁子图挖掘算法[J]. 计算机工程, 2012, 38(7): 31-33.
[14]	何林, 林锋, 周激流. 一种基于DT-MSN的性能预评估方法[J]. 计算机工程, 2012, 38(21): 81-85.
[15]	薛洁, 刘希玉. 基于DNA计算的层次图聚类算法[J]. 计算机工程, 2012, 38(12): 188-190.

选择文件类型/文献管理软件名称

选择包含的内容

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

Algorithm for Solving Minimum Spanning Tree Problem

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

Algorithm for Solving Minimum Spanning Tree Problem

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价