Python完成最小生成树–Prim算法和Kruskal算法
前言
最小生成树涉及到在互联网中网游规划者和网络收音机所面临的问题：信息传达问题。其间最简略的解法是由播送源维护一个收听者的列表，将每条信息向每个收听者发送一次，即单播解法。而单播解法的问题也很显着：路由器网络中，有一些路由器会发送相同的信息，给互联网络增加负担，发生额定流量。另一种办法是洪水解法，每条音讯只发送一次，给一切的路由器，每个路由器再尽可能的发送给相连的主机或路由器。洪水解法假如没有约束的话，许多路由器和主机将不断的接收到重复的音讯，所以洪水解法一般会给每条音讯设置TTL值，以此对信息传达进行约束。
而经过剖析和研讨，信息播送问题的最优解法，依赖于路由器联系图上选取具有最小权重的生成树。沿着最小生成树的途径层次传达，到达每个路由器只需要处理1次音讯，同时总费用最小。
处理最小生成树问题常用的有Prim算法和Kruskal算法，二者均根据贪心算法。Prim算法思维很简略，即每步都沿着最小权重的边向前查找，找到一条权重最小的能够安全增加的边，将边增加到树中。Kruskal算法是对一切的权重进行排序，再次表现贪心算法的思维。经过对权重排序，将权重最小的边开端遍历，直至图中的一切节点都连在同一个树上，此刻即为最小生成树。
规划
需求剖析
运用python，经过Prim算法和Kruskal算法完成图的最小生成树，输入数据以存放二维数组办法的逗号分隔值文件进行输入，比方txt文件或许csv文件，输出时依照Prim算法和Kruskal算法分别输出最小生成树的二维数组。同时运用networkx模块，制作出相应的有权图。
首要输入存放图数据的txt文件途径，然后体系显现菜单：
请挑选相应功用模块：
- 1: 显现原始联系图及数据
- 2：查看prim算法演示
- 3：查看kruskal算法演示
- 4: 更改源文件
- 0：退出此次运转
正确的输入规模为0-3，并完成菜单中的相应功用，其输出办法以相应的联系图和二维数组的办法进行输出。
当输入内容不契合标准或致使程序运转呈现过错时，会有相应提示并重新显现体系菜单。
体系规划
本程序所用数据为存储在逗号分隔值文件中的二维数组，格局为：“首节点，尾节点，权重”。与一般的图结构程序比较，本程序选用的数据格局只取到程序的必要特点，即“首节点，尾节点，权重”，比较于通常的邻接矩阵或稀疏矩阵，三列元素的优势十分显着：易于剖析，直观便利，输入快捷，纠错直接。
此外在main函数中增加try……except语句，就在承认函数无逻辑过错的状况下，节约了在对各个函数的反常判别，提高了代码的简洁性。
体系完成
处理最小生成树问题常用的有Prim算法和Kruskal算法，二者均根据贪心算法。
Prim算法
Prim算法思维很简略，即每步都沿着最小权重的边向前查找，找到一条权重最小的能够安全增加的边，将边增加到树中。
如以下图例（如图5）：
-
Step1：首要从图中选取一个极点，这一步是随机的，本程序中仍协助用户做出了挑选。
-
Step2：由当时极点向未选节点进行遍历，找出最小的边，图中选取D作极点，参加至已选节点，剩余的悉数为未选节点，从极点开端遍历到的边有DA、DB、DE、DF，最小边为DA无异，将A增加至已选节点中，并从未选节点中删去，进入下一步循环。
-
Step3：遍历到相连的边有DB、DE、DF、AB，最小边为AB，将B增加至已选节点中，并从未选节点中删去，进入下一步循环。
-
Step4：遍历到相连的边有DE、DF、BC、BE，最小边为DF，将F增加至已选节点中，并从未选节点中删去，进入下一步循环。
-
Step5：遍历到相连的边有DE、BC、BE、FG，最小边为BE，将E增加至已选节点中，并从未选节点中删去，进入下一步循环。
-
Step6：遍历到相连的边有BC、EC、FG、EG，最小边为EC，将C增加至已选节点中，并从未选节点中删去，进入下一步循环。
-
Step7：遍历到相连的边有FG、EG，最小边为EG，将G增加至已选节点中，并从未选节点中删去，此刻未选节点列表为空，契合完毕条件，程序完毕。
prim算法是沿着节点去找边，所以以未选取的节点的数量为约束条件进行查找，在一个最小生成树结构中，假如有某一个节点与其他任一节点都不存在联系，这个数据便是无效数据，当发现不再有这种数据时，也便是得到了一个完好的最小生成树。程序中，我将i界说为首节点，j界说为尾节点，在现已选取的节点中遍历i，遍历i的同时在预选取节点中遍历j，这样就能够将一切的节点状况一一遍历。而寻觅最小的边时，首要经过“if (li[0] == i and li[1] == j) or (li[0] == j and li[1] == i) :”进行判别，假如i节点和j节点相连，就将‘ij’作为key，权值作为value，参加字典edge_weight中，这儿巧妙的运用了字典的key是一个字符串的不会乱序的特征，经过lambda表达式进行排序，很简单依照key的索引和权重巨细，找到契合条件的——最短的边，以及与之相对应的ij首位节点。这儿已选节点和预选节点都运用了列表的格局，所以只要再依次把契合条件的尾节点从预选节点中remove掉，再append至已选节点列表中即可。代码截图如（图13）。
Kruskal算法
Kruskal算法是对一切的权重进行排序，再次表现贪心算法的思维。经过对权重排序，将权重最小的边开端遍历，直至图中的一切节点都连在同一个树上，此刻即为最小生成树。
如以下图例（如图14，同图5）：
-
Step1：遍历一切边，最小边是AD或CE，排序中除权重外还会以ASCII码排序，选AD为最小边，参加到最小生成树中，A、D增加至已选节点，剩余的为未选节点。
-
Step2：持续遍历剩余的边，CE为最小边，参加到最小生成树中，C、E增加至已选节点，剩余的为未选节点。
-
Step3：持续遍历剩余的边，契合条件的最小边依次为：DF、AB、BE，参加到最小生成树中，将B、F增加至已选节点，剩余的为未选节点。
-
Step4：同上，虽然BC比EG更小，但点BC现现已过E点连通，所以增加第二最小边EG，此刻一切节点在同一个树中，程序完毕。
prim算法中将未增加节点作为约束条件，但是很快发现逻辑的遗漏：倘若有A、B、C、D四个节点，按最小边AB和CD增加至最小生成树之后，ABCD四个点并不连通，归于两个树，模型如下图（图19）：
边数 = 节点数 – 1”， 所以以最小生成树的边与总节点数的联系作为约束条件，判别下一条最小边的首尾节点与已选节点的联系。这儿因为每次涉及到两个节点、重复节点的增加和去除，所以已选节点和未选节点以调集的办法进行运算，处理了增加节点的重复问题，在从预选节点中去除时，也只需挑选在悉数节点调集中，而不在已选节点调集中的调集，即“candidate_node = candidate - selected_node”。
判别逻辑如上述，首要选取最小边，判别最小边的首尾节点是否现已被选，假如方针最小边的首尾节点任有一个节点不在已选节点傍边，或许都不在已选节点傍边，那么能够直接增加该最小边，并将首尾节点去重增加到已选节点调集傍边；假如方针最小边的首尾节点均在已选节点傍边，而且此刻已连接的最小生成树的边数小于已选节点数减一，那么因为首尾节点均在已选节点调集傍边，此刻只需要将该最小边增加到最小生成树傍边即可。代码截图如（图20）。
功用介绍
本程序运用python3.7.3版别进行编程，如有运转报错，请更换python版别为3.7.3或其他适配版别进行测试。
运转程序后会显现体系称号及作者信息。
测试数据及代码
测试数据
| 首节点 | 尾节点 | 权重 |
|---|---|---|
| A | B | 2 |
| A | C | 3 |
| B | C | 1 |
| B | D | 1 |
| B | E | 4 |
| E | F | 1 |
| C | F | 5 |
| F | G | 1 |
| D | E | 1 |
完好代码
import networkx as nx
import matplotlib.pyplot as plt
import sys
import os
G = nx.Graph() #原始有权图
P = nx.Graph() #画prim生成的最小生成树有权图
K = nx.Graph() #画Kruskal生成的最小生成树有权图
nodedict={} #节点的字典集，这儿挑选字典，既保证了数据不会重复，也能够排序，挑选初始极点，对于挑选纠结症的人十分有用
edgelist=[] #边的列表
labels={} #标签，即一切的节点称号，画节点信息时运用
edges={}
def read_file(fileroute):
with open(fileroute,"r") as f:
for line in f:
l=line.strip().split("\t")
l[2] = float(l[2])
edgelist.append(l)
nodedict[l[0]]=l[0]
nodedict[l[1]]=l[1]
# 对字典进行排序，以便选取图的极点，防止挑选纠结症，便利制作节点信息
for i in sorted(nodedict):
labels[i]=nodedict[i]
return (nodedict,edgelist,labels)
def origin(fileroute):
# 从存储图数据的文件中读取数据
# nodedict=read_file(fileroute)[0]
edgelist=read_file(fileroute)[1]
labels=read_file(fileroute)[2]
# print(edgelist)
G.add_weighted_edges_from(edgelist)
# 完成图原始数据的读取
edge_labels = nx.get_edge_attributes(G,'weight')
# 生成节点方位
pos = nx.spring_layout(G)
# 把节点画出来
nx.draw_networkx_nodes(G, pos, node_color='g', node_size=500, alpha=0.8)
# 把边画出来
nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5)
# # 把节点的标签画出来
nx.draw_networkx_labels(G, pos, labels, font_size=16)
# # 把边权重画出来
nx.draw_networkx_edge_labels(G, pos, edge_labels)
plt.title("origin")
plt.show()
"""
完成prim算法的函数
"""
def prim_tree(fileroute):
# 从存储图数据的文件中读取数据
nodedict = read_file(fileroute)[0]
edgelist = read_file(fileroute)[1]
labels = read_file(fileroute)[2]
res=[] # 运用prim算法时最小生成树的边列表
prim_candidate_node=[] # 预选节点
prim_selected_node=[] # 已选节点
for key in labels: # 初始时，一切节点均为预选节点
prim_candidate_node.append(key)
prim_selected_node.append(prim_candidate_node[0])
prim_candidate_node.remove(prim_selected_node[0])
"""
完成prim算法的逻辑代码
"""
while len(prim_candidate_node) > 0 : # prim算法是沿着节点去找边，所以已未选取的节点为约束条件进行查找
edge_weight={}
beginnode=''
endnode=''
weight=0
for i in prim_selected_node: # 将i界说为首节点
for j in prim_candidate_node: # 将j界说为尾节点
for li in edgelist:
if (li[0] == i and li[1] == j) or (li[0] == j and li[1] == i) :
# 假如i节点和j节点相连，就将‘ij’作为key，权值作为value，参加字典edge_weight中
edge_weight[i+j]=li[2]
for key in sorted(edge_weight.items(),key=lambda kv:(kv[1], kv[0])):
# 将edge_weight字典从小到大排序，第一个值是最小值，根据key的ij摆放次序，很简单判别出首尾节点
endnode=key[0][1]
weight=float(key[1])
beginnode=key[0][0]
break
res.append([beginnode,endnode,weight]) # 然后将选取的最小权值的边参加到最小生成树中即可
prim_selected_node.append(endnode)
prim_candidate_node.remove(endnode)
print(res)
P.add_weighted_edges_from(res)
edge_labels = nx.get_edge_attributes(P, 'weight')
# 生成节点方位
pos = nx.spring_layout(P)
# 把节点画出来
nx.draw_networkx_nodes(P, pos, node_color='g', node_size=500, alpha=0.8)
# 把边画出来
nx.draw_networkx_edges(P, pos, width=1.0, alpha=0.5, edge_color='r')
# 把节点的标签画出来
nx.draw_networkx_labels(P, pos, labels, font_size=16)
# 把边权重画出来
nx.draw_networkx_edge_labels(P, pos, edge_labels)
plt.title("prim")
plt.show()
"""
完成kruskal算法的函数
"""
def kruskal_tree(fileroute):
edgelist = read_file(fileroute)[1]
labels = read_file(fileroute)[2]
nodenum = len(labels) # 节点数
candidate = set() # 悉数节点
selected_node = set() # 已选节点
for key in labels:
candidate.add(key)
candidate_node = set(candidate) # 预选节点，这儿设置预选节点，便利之后去重判别
edgesorted = sorted(edgelist, key=lambda weight: weight[2]) # 依照权值对一切边进行排序，表现贪心算法思维
"""
完成kruskal算法的逻辑代码
"""
edge_node = {}
edgelist_chosed = []
while len(edgelist_chosed) < nodenum - 1:
for li in edgesorted:
if li[0] not in selected_node or li[1] not in selected_node:
edgelist_chosed.append(li)
selected_node.add(li[0])
selected_node.add(li[1])
candidate_node = candidate - selected_node
elif li[0] in selected_node and li[1] in selected_node and len(edgelist_chosed) < len(selected_node) - 1:
edgelist_chosed.append(li)
else:
continue
print(edgelist_chosed)
K.add_weighted_edges_from(edgelist_chosed)
edge_labels = nx.get_edge_attributes(K, 'weight')
# 生成节点方位
pos = nx.spring_layout(K)
# 把节点画出来
nx.draw_networkx_nodes(K, pos, node_color='g', node_size=500, alpha=0.8)
# 把边画出来
nx.draw_networkx_edges(K, pos, width=1.0, alpha=0.5, edge_color='r')
# # 把节点的标签画出来
nx.draw_networkx_labels(K, pos, labels, font_size=16)
# # 把边权重画出来
nx.draw_networkx_edge_labels(K, pos, edge_labels)
plt.title("kruskal")
plt.show()
def menu():
print("""
请挑选相应功用模块：
1: 生成原始联系图
2：查看prim算法演示
3：查看kruskal算法演示
4: 更改源文件
0：退出此次运转
""")
def filein():
fileroute = ''
flag = True
while flag:
fileroute = input('请输入正确的图数据的完好途径：')
if os.path.isfile(fileroute):
flag = False
return fileroute
def main():
print("----Python完成最小生成树的两种办法----")
print("----作者：Mxdon----")
fileroute=filein()
menu()
while True:
try:
chose = input("您的输入是数字：")
if chose=="1":
print("原始有权图已制作")
origin(fileroute)
menu()
elif chose=="2":
print("prim算法时的最小生成树的图已制作")
print("---prim算法最小生成树边数据如下：---")
prim_tree(fileroute)
menu()
elif chose=="3":
print("kruskal算法时的最小生成树的图已制作")
print("---kruskal算法最小生成树边数据如下：---")
kruskal_tree(fileroute)
menu()
elif chose=="4":
fileroute = filein()
menu()
elif chose=="0":
print("---再会---")
sys.exit(0)
else:
print("无此选项")
menu()
except Exception as e:
print("\033[31m请查看文件内容是否契合“节点-节点-权重”的格局!\033[0m")
main()
参阅文章
数据结构（十）：最小生成树
python最小生成树kruskal与prim算法
最小生成树的两种办法（Kruskal算法和Prim算法）
最小生成树-Prim算法和Kruskal算法
数据结构根底概念篇
数据结构：八大数据结构分类
数据结构与算法Python版-陈斌
NetworkX系列教程(10)-算法之二:最小/大生成树问题
Python 3 教程
最后，点个重视不走失
大众号：孟游先生的旅行笔记
