基于剪枝的最小生成树算法在供水管网的应用

摘要

在进行供水管网网络设计时,如何使铺设的供水管网线路最短,构建的供水管网造价最低是设计者需要重点考虑的问题之一.文章就此问题提出了一种基于剪枝的最小生成树算法.算法首先将交叉点(街道的交汇处)和节点(用户)都视为图的顶点,然后求出最小生成树,最后再将最小生成树中以交叉点为末梢的"枝叶"剪掉.该算法简洁、快速、易于实现.对铺设公路,架设网线等一类网络问题也有实际的参考意义.%When designing water supply networks, it is the problem to be emphatically considered by the designer that how to pave shortest lines of water supply networks with lowest cost.This paper presents a pruning-based minimum spanning tree algorithm for this problem.In this algorithm, the cross-points ( road intersections) and nodes (users) are pointed out as vertices of a graph, and then the minimum spanning tree of this graph is to be solved.The final step is to prune the top vertices which are also the cross-points in the minimum spanning tree.This algorithm is simple and fast, easy to be realized.It also has practical significance to other similar networks such as paving roads and setting up cables.