journal6 ›› 2001, Vol. 22 ›› Issue (4): 91-92.
• 科研简报 • 上一篇 下一篇
出版日期:
发布日期:
作者简介:
Online:
Published:
摘要：提出一种关于最小生成树的生成法, 此方法是在一个给定的网络中,首先找到一条权最大的边,判断此边的 2个结点在不经过此边的情况下是否有另路相通,若相通则删除此边.否则, 保留此边,再寻找所剩余的权最大的边, 作类似的处理,直到在原网络中剩下的边为顶点数减 1 为止, 由此即得最小生成树.与传统的 Prim 算法及 Kruskal 算法相比较, 此法在点多而边数相对较少的网络中,能迅速地找到它的最小生成树.
关键词： 最小生成树, 网络, 权, 相通
Abstract: Compared wi th the tradi tional algori thms of Prim and Kruskal, the new algori thm introduced in this paper has i ts own advantage. In the given network, find the edge of the ma ximal power and determinewhether there is another access which connects the two vertices of the edge , if there is, delete the edge, or remain i t. Search for the edge of the maximal power in the rest edges and deal wi th i t similarly. Repeat this procedure until the amount of edges in the network is equal to that of the vert ices minus one. By this way the minimal tree is produced
Key words: a minimal produced tree, network, power, connect
曾宪军, 李爱华, 李先明. 最小生成树的又一种生成法[J]. journal6, 2001, 22(4): 91-92.
ZENG Xian-Jun, LI Ai-Hua, LI Xian-Ming. A New Algorithm of the Minimal Produced Tree[J]. journal6, 2001, 22(4): 91-92.
0 / / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: https://zkxb.jsu.edu.cn/CN/
https://zkxb.jsu.edu.cn/CN/Y2001/V22/I4/91
