Description: Prim minimum spanning tree algorithm of Prim algorithm for the undirected minimum spanning tree graph
Set graph G = (V, E), the spanning tree of the vertex set of the U.
①, the v0 into U.
②, all u ∈ U, v ∈ VU edge (u, v) ∈ E, find a minimum weight edge, join the spanning tree.
③, ② to find the edge to join the U v collection. If the set has n elements U, then the end, or continue to ②.
The algorithm s time complexity is O (n ^ 2)
Prim algorithm:
(1) set: Set an array of set (i = 0,1, .., n-1), the initial value is 0, the corresponding vertex is not in the collection (Note: vertex under the label with the No. 1 bad)
(2) map with the adjacency matrix that is not universal infinite path that is available in the computer instead of a large integer.
Complexity of using the heap can be reduced to O (m log n), if the heap can be used Fibonaci reduced complexity O (n log n+ m)
File list (Check if you may need any files):
2(2).txt
Download