论文研究 prim最小生成树算法的动态优化.pdf

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