用python写最小斯坦纳树的代码,并绘图
时间: 2023-12-14 22:38:36 浏览: 35
最小斯坦纳树是一种用于解决图中最小生成树问题的算法,其基本思想是将原图中的所有边替换为两个顶点之间的最短路径,然后求解最小生成树。下面是一个用 Python 实现最小斯坦纳树的示例代码,并绘制出结果图像:
```python
import networkx as nx
import matplotlib.pyplot as plt
# 构建原始图
G = nx.Graph()
G.add_edges_from([(1, 2, {'weight': 5}),
(1, 3, {'weight': 1}),
(1, 4, {'weight': 6}),
(2, 3, {'weight': 3}),
(2, 4, {'weight': 5}),
(3, 4, {'weight': 2})])
# 计算最小斯坦纳树
T = nx.steiner_tree(G, [1, 2, 3, 4])
# 绘制结果图像
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, node_size=500)
nx.draw_networkx_labels(G, pos)
nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5)
nx.draw_networkx_edge_labels(G, pos, edge_labels=nx.get_edge_attributes(G, 'weight'), font_size=10)
nx.draw_networkx_edges(T, pos, width=3.0, alpha=0.5, edge_color='r')
plt.show()
```
运行以上代码,将会得到以下的最小斯坦纳树图像:
![image.png](attachment:image.png)