网络最小生成树更新策略  

An Update Strategy for Minimum Spanning Tree of Net

作　　者：程远[1,2] 

机构地区：[1]中国科学技术大学计算机科学与技术学院,安徽合肥230027 [2]铜陵学院网络中心,安徽铜陵244000

出　　处：《计算机与现代化》2012年第6期125-130,共6页Computer and Modernization

摘　　要：求解最小生成树问题被广泛应用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动。而一旦发生改变,传统算法必须要再次计算最小生成树。但是虽然节点发生了变动,最小生成树未必全部发生改变,这就造成了不必要的浪费。鉴于此提出一种基于Kruskal算法和Prim算法的最小树更新策略,对Kruskal算法和Prim算法做了改进,使其不必重新计算也能在连通图发生改变时更新最小生成树。Solving the problem of minimum spanning tree has been widely used to solve searching issues in reality. However, the node of a connected graph net is often changed, and, once it＇ s changed, the traditional algorithm has to recalculate the minimum spanning tree. But, even the graph node changes, not all of minimum spanning tree will be changed, which results in unnecessa- ry waste. This article is aimed at improving Kruskal algorithm and Prim algorithm, which can update the minimum spanning tree when the graph changes without recalculating.

关 键 词：KRUSKAL算法 PRIM算法 最小生成树 连通网络 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]