假设需要在A、B、C、D、E五座城市间修建公路（五座城市间距离不同），如下示意图所示。
为节省资金，需要将公路修得尽可能短，但又要保证从任何一个城市可以到达另外一个城市。
首先我们讨论环路问题，像B到E，可以经过A再到达，B到E的直连就没必要。因此可以得出，方案中是不可以有环的。不带环的回路其实是一个树结构，此树称为生成树，如下图所示。
以上这些修路方案（生成树）肯定有一条路径是最短的，也就是最省钱的方案，这条权重和最小的方案（生成树）称为最小生成树。那么，如何用程序来找出这棵最小生成树呢？常用的算法有两种：Prim算法和Kruskal算法。下面以Prim算法为例求取上述最小生成树。
Prim算法是从图的一个初始顶点开始，寻找触达其他顶点权值最小的边，并把该顶点加入已触达顶点的集合中。当全部顶点都加入集合时，求最小生成树的工作就完成了。Prim算法的本质是基于贪心算法思想（不从全局考虑，把每一步做到最佳。可查阅百度。）。
本例中的最小生成树采用两个一维数组表示：一个一维数组负责存储已触达顶点；另一个负责存储每个已触达顶点对应的父顶点。求取最小生成树的算法图解如下图所示。
在实现Prim之前，显然需要图类（附录１到３）和最小生成树类（附录４）。
邻接矩阵有向实现代码（文本附录５）：
运行结果：
邻接矩阵无向实现代码：
把
改为
运行结果：
邻接表有向实现代码（文本附录６）：
运行结果：
邻接表无向实现代码：
把
改为
运行结果：
图的极小连接子图不能有回路（因为有回路就不是极小连接），而是一个树形结构，所以称为最小生成树，图的最小生成树不一定是唯一的，同一个图有可能对应多个最小生成树。
最小生成树在实际中的应用非常广泛，比如，城市间的光纤通信、铁路系统、水暖电气系统和路线选择等。
练习题１：修改上例的无向图Prim算法，使其返回全部起点的最小生成树，看看这些树是不是一样的？
练习题２：为何上例无向图的最小生成树与有向的不一样？
学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：
Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。
更多课程请打开“学思营”同步网站：
http://www.5xstar.com/doc.html
参考资料：
１、《Python算法图解》何韬编著 清华大学出版社
附录１：图结构.py
#图结构抽象类
class Graph:
#构造方法
def __init__(self, direct=False):
self.direct = direct #是否有向
'''图结构子类需要实现下面三种方法
#添加顶点
def addVertex(self,key):
@key顶点的字符（键）
pass
#添加边
def addLine(self,start,ends):
@start起点字符@终点[字符,权值]的列表
pass
#打印
def display(self):
pass'''
附录２：图结构_邻接矩阵.py
#创建带权重的图邻接矩阵
from 图结构 import Graph
class GraphMatrix(Graph):
def __init__(self, direct=False):
Graph.__init__(self, direct) #调用超类构造函数
self.dict = {} #节点对应矩阵下标的字典
self.length = 0 #矩阵长宽，即节点数
self.matrix = [] #图邻接矩阵
#添加顶点
def addVertex(self,key):
self.dict[key]=self.length #键（顶点名称）: 值（矩阵中的长宽下标）
self.dict[self.length]=key #键（矩阵中的长宽下标）: 值（顶点名称）
self.length += 1 #矩阵长宽加１
lst = [0 for i in range(self.length)] #创建一行长度为self.length的全0列表
self.matrix.append(lst) #向矩阵中添加全是0的一行
for i in range(self.length-1): #向已有的行添加添加一个0
self.matrix[i].append(0)
#添加边
def addLine(self,start,ends):
'''@start起点字符@终点（字符＋权值）数组@noDirect是否无向'''
startIndex = self.dict[start] #起点在二维矩阵中的下标
for row in ends:
endKey = row[0] #另一节点值
endIndex = self.dict[endKey] #另一节点在二维矩阵中的下标
lineV = row[1] #起点到另一节点权值
self.matrix[startIndex][endIndex]=lineV
if not self.direct:
self.matrix[endIndex][startIndex]=lineV
#打印矩阵
def display(self):
lst = [self.dict[idx] for idx in range(self.length)]
print(" \t" + "\t".join(lst))
for i in range(self.length):
print(lst[i] + "\t" + "\t".join([str(lineV) for lineV in self.matrix[i]]))
#测试 激发《五行星学编程》使用idle运行 input()
if __name__ == "__main__":
lst = ['北京','天津','郑州','青岛']
start1 = '北京'
ends1 = [['天津',138],['郑州',689]]
start2 = '天津'
ends2 = [['郑州',700],['青岛',597]] #与北京的连接已设置
start3 = '郑州'
ends3 = [['青岛',725]] #与北京和天津的连接已设置
gMat = GraphMatrix() #创建一个空邻接矩阵
for city in lst: #加入顶点，创建全0矩阵
gMat.addVertex(city)
gMat.addLine(start1,ends1) #加入以北京为起点的边
gMat.addLine(start2,ends2) #加入以天津为起点，不含北京的边
gMat.addLine(start3,ends3) #加入以郑州为起点，不含北京和天津的边
#打印矩阵
gMat.display()
附录３：图结构_邻接表.py
#邻接表方式创建图
from 图结构 import Graph
class GraphList(Graph):
def __init__(self, direct=False):
Graph.__init__(self, direct) #调用超类构造函数
self.dict = {} #顶点名为键，边链表为值，链表中存储其他节点的名称和权值
def addVertex(self,key): #添加新节点
self.dict[key]=[] #用列表代替链表
#添加边
def addLine(self,start,ends):
'''@start起点字符@终点（字符＋权值）数组'''
for row in ends:
key = row[0] #另一节点值
#在start的邻接表中追加新的边和权值
lst = self.dict[start] #start的邻接表
for kv in lst:
if kv[0] == key: #如果链表中有这个主键，不进行添加
break
else: #如果链表中有这个主键，进行添加(顶点名，权值)元组
self.dict[start].append(row)
if not self.direct: #无向，在start顶点对应的邻接表中追加边和权值
lst = self.dict[key]
for kv in lst:
if kv[0] == start:
break
else:
lst.append([start,row[1]]) #列表追加记录
#打印
def display(self):
for key in self.dict:
print(key,'=>',self.dict[key])
#测试 激发《五行星学编程》使用idle运行 input()
if __name__ == "__main__":
lst = ['北京','天津','郑州','青岛']
start1 = '北京'
ends1 = [['天津',138],['郑州',689]]
start2 = '天津'
ends2 = [['郑州',700],['青岛',597]] #与北京的连接已设置
start3 = '郑州'
ends3 = [['青岛',725]] #与北京和天津的连接已设置
gList = GraphList(True) #创建空邻接表
for city in lst: #添加顶点，每个顶点有一个空列表
gList.addVertex(city)
gList.addLine(start1,ends1) #加入以北京为起点的边
gList.addLine(start2,ends2) #加入以天津为起点，不含北京的边
gList.addLine(start3,ends3) #加入以郑州为起点，不含北京和天津的边
#打印邻接表
gList.display()
附录４：最小生成树.py
#最小生成树
#最小生成树节点类
class MGTNode:
def __init__(self, key=None, value=None):
'''@key顶点键@value权值'''
self.key = key
self.value = value
self.pointers = [] #子节点指针集合
#最小生成树类
class MinGraphTree:
def __init__(self, reachedVertexList, parents):
'''@reachedVertexList触达(顶点键,权值)顺序列表@parents父顶点键列表'''
self.length = len(reachedVertexList) #树的节点数
(key0, value0) = reachedVertexList[0] #解包根顶点
self.root = MGTNode(key0, value0) #数的根节点
ps = {key0 : self.root} #顶点键与节点字典
for i in range(1, self.length): #填充树节点
(key, value) = reachedVertexList[i] #顶点键
parentKey = parents[i] #顶点父顶点键
parent = ps[parentKey] #顶点父节点
node = MGTNode(key,value) #节点
ps[key] = node #加顶点入字典
parent.pointers.append(node) #把节点加入树中
def display(self): #遍历
self.__display(self.root, "", 0)
def __display(self, node, path, sumValue): #递归遍历
'''@node当前节点＠path路径@sumValue权值和'''
path += "-"+node.key
sumValue += node.value
print("路径:", path, "权值合计:", sumValue) #打印上级节点
if len(node.pointers) > 0: #下级指针集合中有记录
lst = node.pointers #获取下级集合
dlen = len(lst)
print("序号\t键\t值\t下级集合")
for i in range(dlen):
nd = lst[i]
dw = "有" if len(nd.pointers) > 0 else "无" #是否有下级集合
print("%d\t%s\t%s\t%s" % (i, nd.key,str(nd.value),dw)) #打印一行
dnum = input("请输入下级序号：")
if dnum != None and dnum != "":
dnum = int(dnum)
if dnum>-1 and dnum < dlen:
self.__display(lst[dnum], path, sumValue)
#测试
if __name__ == "__main__":
__lst = [('A',0),('B',3),('C',1),('E',4),('D',7)]
__ps = [None, 'A', 'B', 'A', 'E']
__tree = MinGraphTree(__lst,__ps)
__tree.display()
附录５：邻接矩阵Prim.py
#邻接矩阵Prim最小生成树
from 最小生成树 import MinGraphTree
from 图结构_邻接矩阵 import GraphMatrix
#Prim算法
def matrixPrim(gMat):
'''@gMat邻接矩阵图'''
result = None
for index in range(gMat.length): #从0开始扫描起点
reachedVertexList, parents, sumValue = __matrixPrim(gMat, index) #尝试一次
if reachedVertexList != None: #找到一个解决方案
print(index,reachedVertexList, parents, sumValue) #测试
if result == None or sumValue < result[2]:
result = (reachedVertexList, parents, sumValue)
if result == None:
return None
else:
return MinGraphTree(result[0],result[1])
def __matrixPrim(gMat, index): #尝试index开始的最小树
reachedVertexList = [index] #已加的索引
parents = [None] #父顶点索引
values = [0] #权值
__matrixPrimRecursion(gMat, reachedVertexList, parents, values) #递归计算
if len(reachedVertexList) == gMat.length: #最小树生成成功
for i in range(gMat.length): #转换触达表
reachedVertexList[i] = (gMat.dict[reachedVertexList[i]],values[i])
for i in range(1,gMat.length): #转换parents， 第0个不用转换
parents[i] = gMat.dict[parents[i]]
return reachedVertexList, parents, sum(values) #返回方案
else:
return None,None,None
def __matrixPrimRecursion(gMat, reachedVertexList, parents, values):
minWeight = 0 #最小权重值
minIndex = None #最小权重值对应的节点
pIndex = None #最小权重值对应的节点的父节点
for rindex in reachedVertexList: #遍历已触达顶点列表
for i in range(gMat.length): #横向扫描矩阵
if i in reachedVertexList: #跳过已触达顶点
continue
v = gMat.matrix[rindex][i] #获取已触达顶点到此顶点的权值
if v>0 and (minWeight==0 or minWeight>v): #有连接并且是第一个或比最小值小
minWeight = v
minIndex = i
pIndex = rindex #最小权值对应的父节点
if minIndex!=None: #找到最小出路
reachedVertexList.append(minIndex) #把最小权值边对应的顶点放入已触达顶点集
parents.append(pIndex) #把新的已触达顶点的父顶点的下标放入parents
values.append(minWeight) #把新的已触达顶点的权值加入
__matrixPrimRecursion(gMat, reachedVertexList, parents, values) #递归找下级
#测试 激发《五行星学编程》使用idle运行 input()
if __name__ == "__main__":
lst = ['A','B','C','D','E']
lstA = [['B',3],['E',4]] #A连接B、E
lstB = [['C',1],['E',8]] #B连接C、E
lstC = [['D',9]] #C连接D
lstD = [['E',7]] #D连接E
gMat = GraphMatrix(True)
for key in lst:
gMat.addVertex(key)
gMat.addLine(lst[0],lstA)
gMat.addLine(lst[1],lstB)
gMat.addLine(lst[2],lstC)
gMat.addLine(lst[3],lstD)
gMat.display()
print('------------------------')
mgTree = matrixPrim(gMat) #转为最小生成树
if mgTree != None:
mgTree.display()
附录６：邻接表Prim.py
#邻接表Prim最小生成树
from 最小生成树 import MinGraphTree
from 图结构_邻接表 import GraphList
#Prim算法
def listPrim(gList):
'''@gList邻接表'''
result = None
for startKey in gList.dict: #扫描所有键作为起点
if len(gList.dict[startKey]) == 0: #跳过无连接出的顶点
continue
reachedVertexList, parents, sumValue = __listPrim(gList, startKey) #尝试一次
if reachedVertexList != None: #找到一个解决方案
print(startKey,reachedVertexList, parents, sumValue) #测试
if result == None or sumValue < result[2]:
result = (reachedVertexList, parents, sumValue)
if result == None:
return None
else:
return MinGraphTree(result[0],result[1])
def __listPrim(gList, startKey): #尝试startKey开始的最小树
reachedVertexList = [startKey] #已加的索引
parents = [None] #父顶点索引
values = [0] #权值
__listPrimRecursion(gList, reachedVertexList, parents, values) #递归计算
length = len(gList.dict) #顶点数
if len(reachedVertexList) == length: #最小树生成成功
for i in range(length): #转换触达表
reachedVertexList[i] = (reachedVertexList[i],values[i])
return reachedVertexList, parents, sum(values) #返回方案
else:
return None,None,None
def __listPrimRecursion(gList, reachedVertexList, parents, values):
minWeight = 0 #最小权重值
minKey = None #最小权重值对应的节点
pKey = None #最小权重值对应的节点的父节点
for rKey in reachedVertexList: #遍历已触达顶点列表
row = gList.dict[rKey] #获取键的行
if len(row) == 0: #跳过无连出的顶点
continue
for [otherKey, v] in row: #扫描行，获取已触达顶点到此顶点的权值
if otherKey not in reachedVertexList and \
(minWeight == 0 or minWeight>v): #未触达有连接并且是第一个或比最小值小
minWeight = v
minKey = otherKey
pKey = rKey #最小权值对应的父节点
if minKey!=None: #找到最小出路
reachedVertexList.append(minKey) #把最小权值边对应的顶点放入已触达顶点集
parents.append(pKey) #把新的已触达顶点的父顶点的下标放入parents
values.append(minWeight) #把新的已触达顶点的权值加入
__listPrimRecursion(gList, reachedVertexList, parents, values) #递归找下级
#测试 激发《五行星学编程》使用idle运行 input()
if __name__ == "__main__":
lst = ['A','B','C','D','E']
lstA = [['B',3],['E',4]] #A连接B、E
lstB = [['C',1],['E',8]] #B连接C、E
lstC = [['D',9]] #C连接D
lstD = [['E',7]] #D连接E
gList = GraphList(True)
for key in lst:
gList.addVertex(key)
gList.addLine(lst[0],lstA)
gList.addLine(lst[1],lstB)
gList.addLine(lst[2],lstC)
gList.addLine(lst[3],lstD)
gList.display()
print('------------------------')
mgTree = listPrim(gList) #转为最小生成树
if mgTree != None:
mgTree.display()