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

Dynamic optimum of minimum span tree's algorithm devised by Prim

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

According to the minimum span tree＇s algorithm devised by prim,designs a unique closedge vector whose type is CloseEdge,the closedge vector is used to represent edges between any pairs of point in U set and V-U set,sets up an adjacency multiple doubly linked list to show a undirected graph with top triangle matrix,builds doubly linked list representing VU set to link to closedge vector and to adjacency multiple doubly linked list.Find the edge with minimum weight only in doubly linked VU list,and after adding a vertex into U set,in constant time to delete one corresponding node in doubly linked VU list and another corresponding vertex in adjacency multiple doubly linked list,thus to produce a minimum span tree in minimum time,the average frequent of sentence execution is e,that is the number of edge in graph.