| 最小生成树的又一种生成法 |
| |
| 引用本文： | 曾宪军,李爱华,李先明.最小生成树的又一种生成法[J].吉首大学学报(自然科学版),2001,22(4):91-92. |
| |
| 作者姓名： | 曾宪军 李爱华 李先明 |
| |
| 作者单位： | (吉首大学数学与计算机科学系, 湖南 吉首 416000) |
| |
| 摘 要： | 提出一种关于最小生成树的生成法, 此方法是在一个给定的网络中,首先找到一条权最大的边,判断此边的 2个结点在不经过此边的情况下是否有另路相通,若相通则删除此边.否则, 保留此边,再寻找所剩余的权最大的边, 作类似的处理,直到在原网络中剩下的边为顶点数减 1 为止, 由此即得最小生成树.与传统的 Prim 算法及 Kruskal 算法相比较, 此法在点多而边数相对较少的网络中,能迅速地找到它的最小生成树.
|
| 关 键 词： | 最小生成树 网络 权 相通 |
| 文章编号： | 1007-2985(2001)04-0091-02 |
| 修稿时间： | 2001年5月16日 |
A New Algorithm of the Minimal Produced Tree |
| |
| Zeng Xian-jun,LI Ai-hua,LI Xian-ming.A New Algorithm of the Minimal Produced Tree[J].Journal of Jishou University(Natural Science Edition),2001,22(4):91-92. |
| |
| Authors: | Zeng Xian-jun LI Ai-hua LI Xian-ming |
| |
| Institution: | ( Department of Mathematics and Computer Science, Jishou Universty, Jishou 416000, Hunan China) |
| |
| Abstract: | Compared with the traditional algorithms of Prim and Kruskal,the new algorithm introduced in this paper has its own advantage.In the given network, find the edge of the maximal power and determine whether there is another access which connects the two vertices of the edge , if there is, delete the edge, or remain it.Search for the edge of the maximal power in the rest edges and deal with it similarly.Repeat this procedure until the amount of edges in the network is equal to that of the vertices minus one.By this way the minimal tree is produced |
| |
| Keywords: | a minimal produced tree network power connect |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《吉首大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《吉首大学学报(自然科学版)》下载免费的PDF全文 |
|
