如下图是个带权值的网结构图。要用最小的成本将所有元素连接起来，即n个顶点，用n-1条边把连通图连接起来，并且使得权值的和最小。定义：把构造连通网的最小代价生成树称为最小生成树。这里介绍两种经典算法。
1. 普里姆（Prim）算法
假设N=(V,E)是连通图，TE是N上的最小生成树中边的集合。
U={u0}(u0∈V)， TE={ }。
在所有u∈U，v∈V-U的边(u，v)∈E 中找一条代价(权值)最小的边(u0，v0) 并入集合TE，同时v0并入U。
重复2，直至U=V为止。
此时TE中必有n-1条边，则T= (V,{TE}) 为N的最小生成树。
python代码实现：
class MGraph(): def __init__(self): self.vertex = [] self.matrix = [] self.numNodes = 0 self.numEdges = 0 def createMGraph(self): """创建无向网图的邻接矩阵表示""" INFINITY = 65535 self.numNodes = int(input("请输入顶点数：")) self.numEdges = int(input("请输入边数：")) for i in range(self.numNodes): self.vertex.append(input("请输入一个顶点：")) for i in range(self.numNodes): self.matrix.append([]) for j in range(self.numNodes): if i == j: self.matrix[i].append(0) # 初始化邻接矩阵 else: self.matrix[i].append(INFINITY) # 初始化邻接矩阵 for k in range(self.numEdges): # 读入numEdges条边，建立邻接矩阵 i = int(input("请输入边(vi,vj)上的下标i:")) j = int(input("请输入边(vi,vj)上的下标j:")) w = int(input("请输入边(vi,vj)上的权w:")) self.matrix[i][j] = w self.matrix[j][i] = self.matrix[i][j] # 因为是无向网图，矩阵对称 def viewMGraphStruct(self): print(self.matrix)def MiniSpanTree_Prim(G): INFINITY = 65535 # 用一个极大值代替∞ adjvex = [] # 保存相关顶点间边的权值点下标 lowcost = [] # 保存相关顶点间边的权值 adjvex.append(0) # 初始化第一个权值为0，即v0加入生成树 lowcost.append(0) # 初始化第一个顶点下标为0，表示从v0开始 for i in range(1, G.numNodes): # 循环除下标为0外的所有顶点 lowcost.append(G.matrix[0][i]) # 将v0顶点与之有边的权值存入列表 adjvex.append(0) # 初始化都为v0的下标 for i in range(1, G.numNodes): min_w = INFINITY # 初始化最小权值为∞ j, k = 1, 0 while j < G.numNodes: # 循环全部顶点 if lowcost[j] != 0 and lowcost[j] < min_w: # 如果权值不为0且权值小于min_w min_w = lowcost[j] # 让当前值成为最小值 k = j # 记录最小值的下表，存入k j += 1 print("({},{})".format(adjvex[k], k)) # 打印当前顶点边中权值最小的边 lowcost[k] = 0 # 将当前顶点权值设为0，此顶点已完成任务 for j in range(1,G.numNodes): # 循环所有顶点 if lowcost[j] != 0 and G.matrix[k][j] < lowcost[j]: # 如果下标为k的顶点的各边权值小于此前这些顶点未被加入生成树的权值 lowcost[j] = G.matrix[k][j] # 将较小的权值存入lowcost相应位置 adjvex[j] = k # 将下标为k的顶点存入adjvexif __name__ == '__main__': G = MGraph() G.createMGraph() G.viewMGraphStruct() MiniSpanTree_Prim(G)以下图网图为例：
输入图的信息后生成的邻接矩阵和最小生成树如下所示：
[[0, 10, 65535, 65535, 65535, 11, 65535, 65535, 65535],[10, 0, 18, 65535, 65535, 65535, 16, 65535, 12],[65535, 18, 0, 22, 65535, 65535, 65535, 65535, 8], [65535, 65535, 22, 0, 20, 65535, 24, 16, 21],[65535, 65535, 65535, 20, 0, 26, 65535, 7, 65535], [11, 65535, 65535, 65535, 26, 0, 17, 65535, 65535],[65535, 16, 65535, 24, 65535, 17, 0, 19, 65535], [65535, 65535, 65535, 16, 7, 65535, 19, 0, 65535], [65535, 12, 8, 21, 65535, 65535, 65535, 65535, 0]](0,1)(0,5)(1,8)(8,2)(1,6)(6,7)(7,4)(7,3)2. 克鲁斯卡尔(Kruskal)算法
假设连通网N=(V,E),将N中的边按权值从小到大的顺序排列。
初始状态为只有n个顶点而无边的非连通图T={V，{ }}，图中每个顶点自成一个连通分量。
在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中(即不形成回路)，否则舍去此边而选择下一条代价最小的边。
重复2，直至T中所有顶点都在同一个连通分量上为止。
算法的实现要先将邻接矩阵的存储方式转换为边集数组的存储方式。
算法步骤：
- 将邻接矩阵的存储方式转换为边集数组的存储方式。
- 将边集数组Edge中的元素按权值从小到大排序。
- 依次查看数组Edge中的边，循环执行以下操作：
- 依次从排序好的数组Edge中选出一条边（U1,U2）
- 在Vexset中分别查找v1和v2 所在的连通分量vs1 和vs2，并进行判断：
*如果vs1 和vs2不等，表明所选的两个顶点分属不同的连通分量，输出此边，并合并vs1 和vs2两个连通分量。
*如果vs1 和vs2相等，表明所选的两个顶点属于同一个连通分量，舍去此边而选择下一条权值最小的边。
python实现：
class MGraph(): def __init__(self): self.vertex = [] self.matrix = [] self.numNodes = 0 self.numEdges = 0 def createMGraph(self): """创建无向网图的邻接矩阵表示""" INFINITY = 65535 self.numNodes = int(input("请输入顶点数：")) self.numEdges = int(input("请输入边数：")) for i in range(self.numNodes): self.vertex.append(input("请输入一个顶点：")) for i in range(self.numNodes): self.matrix.append([]) for j in range(self.numNodes): if i == j: self.matrix[i].append(0) # 初始化邻接矩阵 else: self.matrix[i].append(INFINITY) # 初始化邻接矩阵 for k in range(self.numEdges): # 读入numEdges条边，建立邻接矩阵 i = int(input("请输入边(vi,vj)上的下标i:")) j = int(input("请输入边(vi,vj)上的下标j:")) w = int(input("请输入边(vi,vj)上的权w:")) self.matrix[i][j] = w self.matrix[j][i] = self.matrix[i][j] # 因为是无向网图，矩阵对称 def viewMGraphStruct(self): print(self.matrix)class EdgeNode(): """边节点""" def __init__(self): self.begin = None self.end = None self.weight = Nonedef TransEdge(G): """将邻接矩阵转换为边集数组""" INFINITY = 65535 # 极大值 k = 0 edges = [] # 边集数组 for i in range(G.numEdges): # 注意这里千万不要用列表推导式，初始化边集数组，不然会出现列表越界错误 e = EdgeNode() # 实例化边节点 edges.append(e) for i in range(G.numNodes - 1): for j in range(i + 1, G.numNodes): if 0 < G.matrix[i][j] edges[j].weight: edges[i], edges[j] = edges[j], edges[i] print("权排序后的为：") for i in range(G.numEdges): print("({},{}) {}".format(edges[i].begin, edges[i].end, edges[i].weight)) return edgesdef Find(parent, f): """查找连线顶点的尾部下标""" while parent[f] > 0: f = parent[f] return fdef MiniSpanTree_Kruskal(G): parent = [0 for _ in range(G.numNodes)] # 定义并初始化一个列表用来判断边与边是否形成环路 edges = TransEdge(G) # 由邻接矩阵转换来的边集数组 print("打印最小生成树：") for i in range(G.numEdges): # 循环每一条边 n = Find(parent, edges[i].begin) m = Find(parent, edges[i].end) if n != m: # 如果n与m不相等，说明此边没有与现有的生成树形成环路 parent[n] = m # 将此边的结尾顶点放入下标为起点的的parent中，表示此顶点已经在生成树集合中 print("({},{}) {}".format(edges[i].begin, edges[i].end, edges[i].weight))if __name__ == '__main__': G = MGraph() G.createMGraph() G.viewMGraphStruct() MiniSpanTree_Kruskal(G)以下图网图为例：
输入图的信息后生成的邻接矩阵和最小生成树如下所示：
[[0, 10, 65535, 65535, 65535, 11, 65535, 65535, 65535], [10, 0, 18, 65535, 65535, 65535, 16, 65535, 12], [65535, 18, 0, 22, 65535, 65535, 65535, 65535, 8],[65535, 65535, 22, 0, 20, 65535, 24, 16, 21], [65535, 65535, 65535, 20, 0, 26, 65535, 7, 65535], [11, 65535, 65535, 65535, 26, 0, 17, 65535, 65535],[65535, 16, 65535, 24, 65535, 17, 0, 19, 65535], [65535, 65535, 65535, 16, 7, 65535, 19, 0, 65535],[65535, 12, 8, 21, 65535, 65535, 65535, 65535, 0]]打印最小生成树：(4,7) 7(2,8) 8(0,1) 10(0,5) 11(1,8) 12(3,7) 16(1,6) 16(6,7) 19本文部分概念和图片来自：https://www.jianshu.com/p/d9ca383e2bd8