一种新的最小生成树算法

A new algorithm for minimum spanning tree

针对在最小生成树求解中常用的Prim算法和Kruskal算法适合直接在图上作业而不适于计算机求解,提出了一种新的最小生成树算法:根据最小生成树的定义和性质,对权矩阵进行操作。其优点是:求解过程简单清晰,形象直观,快速有效,易于编程,且具有更广泛的适用性,在求解多节点网络的最小生成树时更能体现其计算速度快的优越性。最后用大庆油田电网作为具体的实例验证了本算法的正确性。

Prim and Kruskal algorithms of minimum spanning tree commonly used in solving minimum spanning tree are more suitable for working directly on the map but not suitable for computer solving.Aiming at that,this paper presents a new minimum spanning tree algorithm.According to the definition and nature of the minimum spanning tree,t he weight matrix is operated.The advantages are that the solving process is simple and clear,v ivid,f ast and effective,easy to program,and it has a broader applicability.W hen solving the minimum spanning tree with multi-node network,the superiority of its calculation speed can be better reflected.F inally,D aqing oil field power is taken as a specific instance to verify the validity of the algorithm.