Dynamic optimum of minimum span tree's algorithm devised by Prim
Hongbo Li · Computer Engineering and Applications Journal · 2007
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.