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

A study on minimum spanning tree algorithm of ventilation network based on weight matrix

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

In order to optimize the data storage structure of the graph,narrow the search range of the minimum spanning tree construction process,improve the search efficiency and reduce the judgment in the construction process,based on weight matrices of weighted directed graph and combined properties of minimum spanning tree,a table for storing ventilation network data was proposed and partitioned.Based on the Prim algorithm and data storage structure of ventilation network,the minimum spanning tree construction method was proposed and the corresponding program was developed.In combination with the specific ventilation network structure,the process of minimum spanning tree was given in tabular form.The results show that the construction method based on weight matrix for analyzing the minimum spanning tree of an engineering example is consistent with the classical Prim algorithm.The program also proves that the method can correctly and effectively construct the minimum spanning tree of the ventilation network.