摘要
最小生成树算法是解决带权无向图中生成最小生成树的重要方法.探讨了最小生成树算法在工业控制领域仪表回路图中的应用,即在有向图中,找出有向的最小生成树.介绍了应用Kruskal算法、Prim算法和Boruvka算法、破圈法构造最小生成树过程.对比分析了四种算法在构造最小生成树的时间复杂度和空间复杂度.应用结果表明:该算法可在仪表回路图中,找到其最小生成树,不仅可以以最小的代价得到仪表数据反馈的完整路径,而且还可以去掉多余的路径分支,减少存储空间,提高仪表回路图的展示性能.
The minimum spanning tree algorithm is an important method to generate a directed minimum spanning tree in a undirected graph with weight.The application of the minimum spanning tree algorithm in the instrument loop diagram in the field of industrial control is discussed,that is to find the minimum spanning tree in the directed graph.The processes of constructing minimal tree with application of Kruskal algorithm,Prim algorithm and Boruvka algorithm and broken circle method are introduced.The time complexity and space complexity of the four algorithms in constructing the minimum spanning tree are compared and analyzed.The application results show that the algorithm can find its minimum spanning tree in the instrument loop diagram,not only can obtain the complete path from the instrument to the data feedback at the minimum cost,but also can remove the redundant path branches,reduce the storage space,improve the display performance of the instrument loop diagram.
作者
钟世平
闫婷
张立飞
周忠敏
Zhong Shiping;Yan Ting;Zhang Lifei;Zhou Zhongmin(Zhejiang SUPCON Co.Ltd.,Hangzhou,310053,China)
出处
《石油化工自动化》
CAS
2023年第3期13-16,28,共5页
Automation in Petro-chemical Industry
关键词
最小生成树
仪表回路图
带权无向图
有向无环图
the minimum spanning tree
the instrument loop diagram
the undirected graph with weight
the directed acyclic graph
