前面的几篇文章学习实现了一下Floyd算法和Dijkstra算法，二者都是用于求解最短路径距离问题的经典算法，今天学习回顾的是Prim算法，这是在求解加权连通图的最小生成树问题中比较经典的算法了，于此齐名的还有一个算法Kruskal算法，之后的时间会学习和实现这个算法，今天的内容是Prim算法的学习，同样，关于Prim算法的原理我也不会长篇累赘，这里简单的概要一下Prim算法的核心思想：
算法的目的是为了解决加权连通图中最小生成树的寻找问题，对于一个给定的图，设置两个空的集合A、B，假设A用于存储原始图的最小生成树的顶点，最开始的时候A中只包含一个顶点，B中存放的是这个最小生成树的边边权值，最开始的B是空集，在图中寻找与A中顶点相连的最小边权值然后将另一端的顶点加入到A中，同时将边权值加入到集合B中去，直至遍历完全所有的顶点后算法终止
下面是算法的具体实现：
#!usr/bin/env python
#encoding:utf-8
'''
__Author__:沂水寒城
功能：使用Prim算法求加权连通图的最小生成树
'''
import random
import time
def random_matrix_genetor(vex_num=10):
'''
随机图顶点矩阵生成器
输入：顶点个数，即矩阵维数
'''
data_matrix=[]
for i in range(vex_num):
one_list=[]
for j in range(vex_num):
one_list.append(random.randint(1, 100))
data_matrix.append(one_list)
return data_matrix
def prim(data_matrix):
'''
prim 算法
'''
vex_num=len(data_matrix)
prims=[]
weights=[]
flag_list=[False]*vex_num
node=0
for i in range(vex_num):
prims.append(0)
weights.append(0)
flag_list[node]=True
for i in range(vex_num):
weights[i]=data_matrix[node][i]
for i in range(vex_num-1):
min_value='N'
for j in range(vex_num):
if weights[j]!='N' and weights[j]<min_value and not flag_list[j]:
min_value=weights[j]
node=j
if node==0:
return
flag_list[node]=True
for m in range(vex_num):
if weights[m]>data_matrix[node][m] and not flag_list[m]:
weights[m]=data_matrix[node][m]
prims[m]=node
return weights, prims
def main_test_func(vex_num=10):
'''
主测试函数
'''
start_time=time.time()
data_matrix=random_matrix_genetor(vex_num)
weights, prims=prim(data_matrix)
print weights
print prims
end_time=time.time()
return end_time-start_time
if __name__=='__main__':
data_matrix=random_matrix_genetor(10)
weights, prims=prim(data_matrix)
print weights
print prims
time_list=[]
print '----------------------------10顶点测试-------------------------------------'
time10=main_test_func(10)
time_list.append(time10)
print '----------------------------50顶点测试-------------------------------------'
time50=main_test_func(50)
time_list.append(time50)
print '----------------------------100顶点测试-------------------------------------'
time100=main_test_func(100)
time_list.append(time100)
print '----------------------------1000顶点测试-------------------------------------'
time1000=main_test_func(1000)
time_list.append(time1000)
print '---------------------------------时间消耗对比--------------------------------'
for one_time in time_list:
print one_time
结果如下：
[33, 11, 2, 6, 1, 1, 4, 30, 5, 19]
[0, 5, 4, 8, 0, 0, 4, 9, 4, 5]
----------------------------10顶点测试-------------------------------------
[44, 12, 3, 16, 10, 8, 16, 1, 6, 34]
[0, 2, 0, 6, 0, 3, 1, 2, 5, 7]
----------------------------50顶点测试-------------------------------------
[31, 4, 1, 1, 2, 3, 4, 4, 3, 3, 2, 4, 11, 2, 4, 4, 1, 1, 3, 3, 2, 1, 4, 1, 1, 9, 1, 2, 1, 6, 2, 3, 1, 2, 2, 1, 1, 1, 3, 1, 2, 5, 2, 1, 6, 5, 1, 1, 4, 2]
[0, 28, 29, 0, 0, 1, 45, 20, 26, 40, 45, 0, 31, 15, 42, 28, 35, 11, 36, 28, 14, 42, 14, 13, 10, 35, 9, 32, 39, 0, 17, 43, 23, 45, 14, 26, 13, 34, 39, 47, 4, 16, 40, 36, 37, 13, 40, 21, 37, 26]
----------------------------100顶点测试-------------------------------------
[36, 3, 2, 1, 2, 1, 2, 2, 3, 1, 1, 1, 2, 1, 3, 1, 3, 3, 1, 3, 3, 1, 1, 1, 2, 1, 4, 2, 1, 1, 1, 1, 5, 3, 1, 2, 2, 3, 1, 2, 2, 3, 3, 1, 3, 1, 1, 3, 4, 3, 1, 2, 2, 2, 1, 4, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 2, 2, 2, 1]
[0, 74, 30, 70, 96, 61, 13, 60, 58, 34, 18, 82, 7, 28, 20, 7, 63, 43, 72, 56, 46, 0, 36, 0, 98, 78, 97, 25, 89, 85, 11, 17, 9, 31, 21, 51, 40, 62, 78, 68, 88, 58, 70, 63, 93, 59, 13, 19, 77, 80, 6, 21, 60, 0, 88, 84, 77, 21, 13, 46, 65, 35, 4, 78, 68, 34, 52, 93, 75, 79, 9, 27, 43, 6, 65, 6, 82, 1, 95, 3, 64, 86, 13, 18, 53, 2, 88, 38, 74, 74, 72, 68, 58, 38, 89, 12, 15, 38, 90, 83]
----------------------------1000顶点测试-------------------------------------
[16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 105, 45, 111, 93, 29, 31, 279, 45, 188, 276, 55, 198, 107, 42, 20, 136, 101, 72, 107, 163, 143, 297, 45, 177, 86, 5, 122, 31, 129, 122, 8, 144, 308, 370, 61, 68, 21, 150, 23, 1, 37, 131, 320, 91, 0, 105, 107, 90, 177, 603, 175, 198, 119, 375, 62, 149, 84, 121, 48, 135, 2, 72, 51, 13, 0, 65, 64, 25, 72, 132, 91, 67, 121, 132, 99, 127, 59, 73, 28, 29, 140, 37, 15, 1, 364, 75, 295, 218, 146, 91, 75, 71, 29, 105, 176, 328, 39, 55, 46, 151, 68, 3, 61, 95, 66, 234, 86, 44, 127, 25, 91, 32, 63, 27, 9, 141, 66, 83, 1, 246, 141, 101, 108, 181, 95, 29, 141, 98, 135, 2, 129, 61, 214, 184, 17, 61, 111, 52, 28, 91, 62, 212, 27, 59, 198, 66, 53, 254, 195, 45, 1, 83, 2, 59, 164, 137, 5, 83, 99, 53, 151, 45, 0, 4, 158, 55, 248, 109, 164, 81, 6, 360, 90, 147, 73, 86, 129, 484, 40, 33, 136, 382, 142, 65, 51, 101, 41, 5, 17, 177, 409, 194, 112, 45, 71, 99, 122, 23, 29, 69, 366, 29, 46, 72, 73, 153, 31, 72, 53, 47, 13, 19, 25, 135, 11, 147, 19, 65, 202, 31, 28, 102, 156, 171, 115, 61, 86, 253, 122, 140, 261, 119, 19, 157, 27, 84, 126, 15, 23, 112, 250, 28, 61, 101, 175, 3, 128, 28, 4, 119, 61, 175, 53, 146, 23, 157, 169, 39, 75, 546, 136, 42, 157, 45, 68, 193, 90, 35, 65, 129, 227, 6, 16, 155, 51, 440, 517, 23, 219, 22, 297, 48, 16, 103, 77, 211, 101, 82, 62, 107, 293, 28, 84, 132, 66, 27, 206, 0, 19, 136, 242, 28, 469, 142, 15, 77, 46, 139, 238, 76, 231, 77, 269, 116, 123, 66, 154, 147, 123, 118, 79, 18, 126, 245, 164, 14, 68, 31, 17, 23, 215, 112, 163, 92, 31, 72, 299, 93, 379, 134, 152, 67, 121, 62, 181, 110, 6, 493, 102, 236, 79, 65, 113, 63, 46, 0, 8, 447, 160, 122, 63, 164, 127, 59, 19, 8, 0, 77, 13, 58, 91, 160, 230, 130, 137, 113, 327, 13, 47, 105, 80, 58, 122, 375, 130, 29, 135, 65, 30, 320, 121, 169, 39, 52, 31, 316, 44, 160, 66, 126, 57, 122, 45, 28, 45, 281, 264, 525, 377, 79, 28, 214, 25, 17, 136, 367, 63, 84, 65, 84, 52, 114, 147, 65, 0, 6, 101, 56, 238, 94, 129, 169, 139, 274, 77, 6, 57, 325, 75, 242, 68, 101, 205, 254, 133, 99, 220, 200, 0, 150, 42, 107, 81, 367, 151, 79, 137, 8, 372, 232, 99, 4, 253, 272, 57, 106, 91, 131, 30, 4, 49, 250, 25, 36, 25, 35, 194, 105, 176, 102, 131, 151, 72, 129, 282, 48, 144, 55, 221, 127, 26, 128, 103, 12, 304, 90, 171, 58, 3, 40, 104, 99, 135, 98, 138, 174, 101, 118, 143, 44, 55, 132, 57, 8, 250, 157, 45, 79, 188, 141, 40, 42, 79, 40, 99, 161, 110, 66, 79, 93, 37, 98, 176, 130, 99, 177, 23, 95, 35, 108, 39, 453, 93, 4, 190, 42, 55, 261, 90, 93, 68, 8, 122, 402, 243, 208, 97, 146, 174, 91, 250, 124, 49, 66, 58, 115, 170, 283, 36, 24, 39, 343, 47, 276, 123, 2, 5, 53, 352, 151, 66, 173, 112, 378, 98, 51, 35, 36, 72, 64, 71, 304, 164, 62, 134, 57, 204, 24, 284, 151, 259, 82, 175, 28, 39, 73, 71, 61, 130, 232, 250, 262, 142, 65, 28, 77, 114, 112, 12, 6, 79, 258, 199, 65, 74, 150, 110, 14, 99, 163, 299, 69, 14, 36, 273, 17, 2, 39, 45, 36, 128, 0, 156, 64, 175, 140, 127, 39, 232, 317, 38, 37, 25, 6, 53, 90, 244, 86, 366, 91, 95, 114, 147, 132, 6, 256, 97, 52, 20, 151, 88, 65, 26, 141, 32, 114, 58, 37, 41, 92, 161, 111, 26, 23, 97, 8, 89, 169, 31, 2, 65, 361, 15, 163, 21, 86, 210, 117, 94, 164, 186, 150, 143, 68, 352, 131, 69, 119, 59, 148, 131, 16, 25, 61, 118, 84, 29, 82, 46, 71, 40, 84, 237, 121, 28, 158, 103, 29, 79, 48, 61, 141, 202, 189, 39, 135, 45, 140, 182, 153, 309, 194, 104, 35, 75, 2, 68, 67, 216, 232, 45, 108, 209, 101, 8, 219, 45, 95, 91, 62, 307, 135, 196, 128, 254, 545, 104, 14, 15, 217, 245, 23, 71, 44, 4, 4, 164, 48, 90, 46, 110, 98, 107, 164, 188, 163, 101, 117, 122, 84, 308, 84, 26, 61, 84, 2, 84, 108, 99, 91, 23, 249, 15, 9, 84, 103, 40, 122, 67, 81, 113, 66, 6, 99, 0, 23, 159, 68, 423, 115, 86, 108, 44, 95, 131, 143, 141, 44, 217, 357, 127, 130, 138, 100, 223, 69, 37, 232, 84, 0, 123, 108, 130, 46, 36, 23, 116, 145, 111, 316, 91, 37, 1, 308, 102, 116, 89, 60, 45, 230, 99, 166, 129, 129, 105, 92, 2, 5, 79, 155, 159, 123, 135, 48, 1, 61, 107, 59, 177, 146, 159, 36, 18, 83, 69, 20, 349, 30, 344, 99, 131, 5, 266, 185, 86, 152, 35, 26, 163, 102, 35, 19, 48, 151, 166, 210, 63, 111, 557, 169, 53, 90, 70, 47, 179, 127, 112, 119, 193, 313, 35, 23, 215, 128, 208, 28, 31, 41, 53, 84, 75, 91, 20, 0, 6, 168, 150, 39, 268, 143, 147, 4, 44, 312, 16, 28, 8, 6, 100, 98, 89, 170, 3, 36, 205, 214, 13, 237, 730, 16, 155, 121, 25, 105, 78, 507, 125, 65, 86, 99, 94, 20, 44, 103, 71, 114, 114, 31, 158, 103, 75, 15, 91, 80, 47, 177, 32, 132, 98, 118, 97, 66, 163, 104, 23, 97, 138, 61, 62]
---------------------------------时间消耗对比--------------------------------
0.0
0.00399994850159
0.0169999599457
1.55599999428
结果可以看出：
时间消耗还是很低的，在大规模图中Prim算法也是很理想的。
好了，关于Prim就说这么多了，如有问题欢迎讨论！