网络最小生成树更新策略

• 作者: 程远
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: Kruskal算法 Prim算法 最小生成树 连通网络
• 年，卷（期）: 2012,（6）
• 所属期刊栏目: 网络与通信
• 页码范围: 125-130
• 分类号: TP301.6
• 字数: 5996字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2012.06.034

摘要

求解最小生成树问题被广泛应用于求解现实中的搜索相关问题.然而现实瞬息万变,一个连通网络的节点常常发生变动.而一旦发生改变,传统算法必须要再次计算最小生成树.但是虽然节点发生了变动,最小生成树未必全部发生改变,这就造成了不必要的浪费.鉴于此提出一种基于Kruskal算法和Prim算法的最小树更新策略,对Kruskal算法和Prim算法做了改进,使其不必重新计算也能在连通图发生改变时更新最小生成树.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	程远	中国科学技术大学计算机科学与技术学院	4	17	2.0	4.0