Prim最小生成树算法的动态优化

摘要：

根据Prim最小生成树算法的设计思想,设计了独特CloseEdge型closedge向量表示U到V-U集合中的边,用上三角法建立了无向图的邻接多重双向链表,构造了链接closedge向量和邻接多重双向链表表结点的VU集合双向链.查找最小权值的边仅在VU集合双向链上进行,且当顶点被加入U集合后,常量时间删除其对应的VU集合双向链和邻接多重双向链表中的结点,使得最小生成树的生成达到极小化,其语句执行频度平均为e.

关键词：最小生成树、closedge向量、邻接多重双向链表、VU集合双向链、动态优化

所属期刊栏目：43

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

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

页数：共5页

页码：69-73