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

Abstract: According to the minimum span tree’s algorithm devised by prim, design 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, set up an adjacency multiple doubly linked list to show a undirected graph with top triangle matrix, build 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.

Key words: Minimum Span Tree, Dynamic optimum, Closedge vector, Adjacency multiple doubly linked list, doubly linked VU list