摘要
求解最小生成树问题被广泛应用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动。而一旦发生改变,传统算法必须要再次计算最小生成树。但是虽然节点发生了变动,最小生成树未必全部发生改变,这就造成了不必要的浪费。鉴于此提出一种基于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.
出处
《计算机与现代化》
2012年第6期125-130,共6页
Computer and Modernization
