基于权矩阵的通风网络最小生成树算法研究

作者：涂鹏; 张恒^*; 孙建春; 王路

来源：铁道科学与工程学报, 2018, 15(09): 2285-2292.

DOI：10.19713/j.cnki.43-1423/u.2018.09.015

• 通风网络
• 最小生成树
• Prim算法
• 权矩阵

为优化图的数据存储结构,缩小最小生成树构造过程的搜寻范围,提高搜索效率,减小构造过程中的判断,以赋权有向图权矩阵为基础,结合最小生成树性质提出用于存储通风网络数据的表格,并将表格进行分区处理。基于Prim算法和通风网络数据存储结构,提出通风网络最小生成树构造方法并编制相应程序,结合具体通风网络结构以表格方式给出最小生成树的具体构成过程。研究结果表明:基于权矩阵的构造方法与经典Prim算法对工程算例的最小生成树进行构造分析所得到结果是一致的,同时编制的程序也验证了该方法能够正确有效地构造通风网络最小生成树。

• 单位
  西南交通大学; 四川交通职业技术学院