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

摘要：

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

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

所属期刊栏目：37

分类号：O224(运筹学)

资助基金：陕西省教育厅专项科研计划基金资助项目11JK0509;宝鸡文理学院基金资助重点项目ZK0931

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：241-243,247