最小生成树之Prim算法 Prim算法用于求无向图的最小生成树



设图G =（V，E），其生成树的顶点集合为U。



①、把v0放入U。



②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。



③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。



其算法的时间复杂度为O(n^2)



Prim算法实现：



（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）



（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。



采用堆可以将复杂度降为O(m log n)，如果采用Fibonaci堆可以将复杂度降为O(n log n + m)-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)