利用通风网络数据结构构造最小生成树的方法

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

来源：地下空间与工程学报, 2018, 14(S2): 887-892.

• 通风网络
• 赋权有向图
• 最小生成树
• 数据结构

构建最小生成树对于网络通风系统是一个需要解决的关键问题,而传统方法的最小生成树构造过程中存在的大量的判断。为了优化图的数据存储结构,缩小最小生成树构造过程的搜寻范围,提高搜索效率,减小构造过程中的判断,以赋权有向图权矩阵为基础,结合最小生成树性质提出了用于存储通风网络数据的表格,并将表格进行了分区处理。借助通风网络表,提出了通风网络最小生成树构造方法,并结合具体通风网络结构以表格方式给出了最小生成树的具体构成过程。研究结果表明:基于通风网络数据结构的最小生成树的算法与Prim算法对工程算例的最小生成树构造分析结果是一致的。

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