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

• 作者: 李洪波 陈军
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 最小生成树 closedge向量 邻接多重双向链表 VU集合双向链 动态优化
• 年，卷（期）: 2007,（12）
• 所属期刊栏目: 学术探讨
• 页码范围: 69-73
• 页数: 5页
• 分类号: TP301.6
• 字数: 3818字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2007.12.024

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李洪波	烟台师范学院数学与信息学院	14	130	6.0	11.0
2	陈军	烟台师范学院数学与信息学院	3	27	2.0	3.0