【课后作业06】图及最小生成树 隐藏答案 | 返回首页

作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：Python3.11
运行环境：Intel Core i7-7700K CPU 4.2GHz, nVidia GeForce GTX 1080 Ti
本教案所涉及的数据集仅用于教学和交流使用，请勿用作商用。

最后更新：2024年2月27日

---

【知识点】

图论基础、最小生成树

【作业要求】

使用word文档或Markdown文档进行作答，使用Python编写程序，最终结果合并为一个word文档或Markdown文档，并另存为PDF格式进行提交。

注意：可以使用手机拍照文档进行提交，但请不要使用word文档直接进行提交。

【问题描述】

[习题6.1*-P182] 用Python分别画出下图中的三个图形，并计算图（b）中最小生成树的长度。

要求使用Python进行求解。

【答案及解析】

import networkx as nx
import matplotlib.pyplot as plt

# 1. 绘制图1非赋权图
L1 = [(1,2), (1,3), (1,4), (2,3), (2,6), (3,4), (4,5), (5,6)]
G1 = nx.Graph();
G1.add_nodes_from(range(1,7))
G1.add_edges_from(L1)
pos1 = nx.shell_layout(G1)
plt.figure(figsize=(12,6))
plt.subplot(2,3,1)
nx.draw(G1, pos1, with_labels=True, font_weight='bold')
plt.title('(a)')

# 2. 绘制图2赋权图
L2 = [(1,2,7), (1,3,3), (1,4,12), (2,3,1), (2,6,1), (3,4,8), (4,5,9), (5,6,3)]
G2 = nx.Graph();
G2.add_nodes_from(range(1,7))
G2.add_weighted_edges_from(L2)
pos2 = nx.shell_layout(G2)
plt.subplot(2,3,2)
nx.draw(G2, pos2, with_labels=True, font_weight='bold')
w2 = nx.get_edge_attributes(G2,'weight')
nx.draw_networkx_edge_labels(G2, pos2, edge_labels=w2)
plt.title('(b)')


# 3. 绘制图3有向赋权图
L3 = [(1,3,3), (2,1,7), (2,3,1), (3,4,8), (4,1,12), (5,4,9), (5,6,3), (6,2,1)]
G3 = nx.DiGraph()
G3.add_nodes_from(range(1,7))
G3.add_weighted_edges_from(L3)
pos3 = nx.shell_layout(G3)
plt.subplot(2,3,3)
nx.draw(G3, pos3, with_labels=True, font_weight='bold')
w3 = nx.get_edge_attributes(G3,'weight')
nx.draw_networkx_edge_labels(G3, pos3, edge_labels=w3)
plt.title('(c)')

# 4. 绘制图2的最小生成树
T2 = nx.minimum_spanning_tree(G2)
w = nx.get_edge_attributes(T2,'weight')
T2L = sum(w.values())
pos = nx.shell_layout(T2)
s = ['v' + str(i) for i in range(1, 7)]
s = dict(zip(range(1, 7), s))
plt.subplot(2,3,4)
nx.draw(T2, pos, labels=s, with_labels=True, font_weight='bold')
nx.draw_networkx_edge_labels(T2, pos, edge_labels=w)
plt.title('The spanning tree of Graph(b)')
plt.show()

print('图(b)的最小生成树长度为：', T2L)