最小生成树的又一种生成法

• 作者: 曾宪军 李先明 李爱华
• 来源期刊: 吉首大学学报(自然科学版)
• 学科: 数学
• 关键词: 最小生成树 网络 权 相通
• 年，卷（期）: 2001,（4）
• 所属期刊栏目: 科研简报
• 页码范围: 91-92
• 页数: 2页
• 分类号: O157.6
• 字数: 1178字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-2985.2001.04.026

摘要

提出一种关于最小生成树的生成法,此方法是在一个给定的网络中,首先找到一条权最大的边,判断此边的2个结点在不经过此边的情况下是否有另路相通,若相通则删除此边.否则,保留此边,再寻找所剩余的权最大的边,作类似的处理,直到在原网络中剩下的边为顶点数减1为止,由此即得最小生成树.与传统的Prim算法及Kruskal算法相比较,此法在点多而边数相对较少的网络中,能迅速地找到它的最小生成树.