# 1 普里姆算法(prim算法)

## 1 算法简单描述

1).输入：一个加权连通图，其中顶点集合为V，边集合为E； 2).初始化：P = {x}，其中x为集合V中的任一节点（起始点），Q = {},为空； 3).重复下列操作，直到P = V： a.在集合E中选取权值最小的边

## 3 简单证明prim算法

• 1).设prim生成的树为G0
• 2).假设存在Gmin使得cost(Gmin)

## 4 prim算法的python实现

```'''
#file:py_prim.py
#最小生成树 prim算法的python实现
'''
debug = 0
MAX_NUM = 10000
v_num = 6

grapharr = [[0, 6, 1, 5, MAX_NUM, MAX_NUM],
[6, 0, 5, MAX_NUM, 3, MAX_NUM],
[1, 5, 0, 5, 5, 4],
[5, MAX_NUM, 5, 0, MAX_NUM, 2],
[MAX_NUM, 3, 6, MAX_NUM, 0, 6],
[MAX_NUM, MAX_NUM, 4, 2, 6, 0],
]

######################################
# U放已经匹配好的顶点:
U = []
# V初始化为所有顶点的集合:
V = []
# T放各个边:
T = []

def init():
if (debug):
print("grapharr=", end="")
print(grapharr)
i = 0
while i < v_num:
V.append(i + 1)
i = i + 1

def prim_start_vertex(start):
if (start < 1):
print("ERROR:start=", start)
print("ERROR:change start to 1 by default!")
start = 1

U.append(start)
del V[start - 1]

def list_sort(l):
if (len(l) < 1):
print("ERROR:len of l =", len(l))
exit

index = 0
i = 0
min_val = l[0]
while i < len(l):
if min_val > l[i]:
min_val = l[i]
index = i

i = i + 1
if (debug):
print("[list_sort]:l=", l, ";index=", index)
return index

def min_wui():
m = MAX_NUM
close_edge = {'u': -1, 'v': -1}
edge_list = []
vertex_list = []
i = 0
j = 0
# 算出U和V之间所有边的长度:
lu = len(U)
lv = len(V)
if (debug):
print("##############entry min_wui###########")
print("lu=", lu, ";lv=", lv)
while i < len(U):
while j < len(V):
if (debug):
print("i=", i, ";j=", j)
print("U[i]=", U[i], ";V[j]=", V[j])
temp = grapharr[U[i] - 1][V[j] - 1]
if (temp > 0):
if (temp < MAX_NUM):
close_edge = {'u': U[i], 'v': V[j]}
if (debug):
print("close_edge=", close_edge)
vertex_list.append(close_edge)
edge_list.append(temp)

j = j + 1
# for i:
i = i + 1
j = 0
# end of :for while i
if (debug):
print("vertex_list=", vertex_list)
print("edge_list=", edge_list)
min_index = list_sort(edge_list)
close_edge = vertex_list[min_index]
U.append(close_edge['v'])
del V[V.index(close_edge['v'])]
if (debug):
print("U=", U)
print("V=", V)
return close_edge

def py_prim(start):
init()
prim_start_vertex(start)
print("init values:")
print("U=", U)
print("V=", V)
print("T=", T)
while (len(U) != v_num):
if (debug):
print("len(U)=", len(U))
our_edge = min_wui()
T.append(our_edge)

print("========RESULT============")
print("U=", U)
print("V=", V)
print("T=", T)

######################################
if (__name__ == "__main__"):
# 开始主程序:
debug = 0
py_prim(1)

init values:
U= [1]
V= [2, 3, 4, 5, 6]
T= []
========RESULT============
U= [1, 3, 6, 4, 2, 5]
V= []
T= [{'v': 3, 'u': 1}, {'v': 6, 'u': 3}, {'v': 4, 'u': 6}, {'v': 2, 'u': 3}, {'v': 5, 'u': 2}]```

# 二 kruskal算法

Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

## 1 kruskal算法的精髓在于：每次选取一条边，该边同时满足：

1、在当前未选边中权值最小； 2、与已选边不构成回路。直到选取n-1条表是算法结束。找到MST活判断不存在MST。

## 2.算法简单描述

1).记Graph中有v个顶点，e个边 2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边 3).将原图Graph中所有e个边按权值从小到大排序 4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中 if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中 添加这条边到图Graphnew中

## 3 图片描述

3.简单证明Kruskal算法 对图的顶点数n做归纳，证明Kruskal算法对任意n阶图适用。 归纳基础： n=1，显然能够找到最小生成树。 归纳过程： 假设Kruskal算法对n≤k阶图适用，那么，在k+1阶图G中，我们把最短边的两个端点a和b做一个合并操作，即把u与v合为一个点v’，把原来接在u和v的边都接到v’上去，这样就能够得到一个k阶图G’(u,v的合并是k+1少一条边)，G’最小生成树T’可以用Kruskal算法得到。 我们证明T’+{

## 4.代码算法实现

```from pylab import *

INFINITY = 65535                        #代表无穷大
vexs = array([[0,10,INFINITY,INFINITY,INFINITY,11,INFINITY,INFINITY,INFINITY],#邻接矩阵
[10,0,18,INFINITY,INFINITY,INFINITY,16,INFINITY,12],
[INFINITY,18,0,22,INFINITY,INFINITY,INFINITY,INFINITY,8],
[INFINITY,INFINITY,22,0,20,INFINITY,INFINITY,16,21],
[INFINITY,INFINITY,INFINITY,20,0,26,INFINITY,7,INFINITY],
[11,INFINITY,INFINITY,INFINITY,26,0,17,INFINITY,INFINITY],
[INFINITY,16,INFINITY,24,INFINITY,17,0,19,INFINITY],
[INFINITY,INFINITY,INFINITY,16,7,INFINITY,19,0,INFINITY],
[INFINITY,12,8,21,INFINITY,INFINITY,INFINITY,INFINITY,0]])

lengthVex = len(vexs)                   #邻接矩阵大小
beginEdge = []
endEdge = []
weight = []
group = []
for i in arange(lengthVex):             #生成边集数组
group.append([i])
for j in arange(i+1,lengthVex):
if(vexs[i, j]>0 and vexs[i, j]<INFINITY):
beginEdge.append(i)         #每条边的起点
endEdge.append(j)           #每条边的终点
weight.append(vexs[i, j])   #每条边的权值

lengthEdge = len(weight)                #边的条数
sum = 0
for i in arange(lengthEdge):            #遍历每条边
I = (argsort(weight))[0]
for j in arange(lengthVex):
if(beginEdge[I]) in group[j]:
m = j
if(endEdge[I]) in group[j]:
n = j
if m != n:                          #判断当前这条边是否属于不同的连通分量，如果是，将其合并
group[m] = group[m] + group[n]
group[n] = []
sum = sum + weight[I]
print(weight[I])
del weight[I]                       #删除遍历过的边以及顶点
del beginEdge[I]
del endEdge[I]
print("The length of the minimum cost spanning tree is: ",sum)```

## 5 时间复杂度：elog2e e为图中的边数

0 条评论

• ### python学习笔记7.5-内建模块struct

Python中变量的类型只有列表、元祖、字典、集合等高级抽象类型，并没有像c中定义了位、字节、整型等底层初级类型。因为Python本来就是高级解释性语言，运行的...

• ### python学习笔记2.6-集合（set）

一般来说，python中常用的数据结构是：列表（list）、字典（Dict）、元组（tuple）。但是我们常常还会看到另外一种结构：集合（set）。 个人认...

• ### 课程笔记4--图像K空间理解

K空间的数据分布实际上是图像空间中数据的二维傅立叶变换结果。 K空间中的数据点和图像空间中的数据点并不是一一对应的。一个K空间中的数据点对应了图像空间中所有...

• ### 编程小知识 之 序列 rotate

本篇文章中所说的 序列 rotate(旋转) 可能跟我们平常理解的 图像 rotate(旋转) 不太相同,所谓 序列 rotate,其实就是一种调整序列元素顺序...

• ### 从生物学的角度浅谈前端工程化

? 导语：看过《人类简史》一书的人都知道，该书从物理学，化学，生物学，政治学等学科角度，对整个人类历史做出了全方位的考察和预测，总结归纳出超越历史层面的规律和...

• ### 【web开发】HTML5(目前)无法帮你实现的五件事

人都专注于HTML5能够实现什么（或者是如何将各种方法连接起来，实现一个更加优雅的解决方案）。而现在，也不少人想将目光投向那些HTML5无法实现的事情。MSDN...

• ### php 使用html5 XHR2实现上传文件与进度显示功能示例

本文实例讲述了php 使用html5 XHR2实现上传文件与进度显示功能。分享给大家供大家参考，具体如下：

• ### 深度学习笔记

该数据库有：10类标签，50000个训练数据，10000个测试数据，大小均为32*32。