网络最小生成树更新策略

摘要：

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

关键词：Kruskal算法、Prim算法、最小生成树、连通网络

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2012-07-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：125-130