1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
"""
=====================
Minimum Spanning Tree
=====================
A minimum spanning tree (MST) is a subset of edges in a weighted,
connected graph that connects all vertices together with the
minimum possible total edge weight. The `minimum_spanning_tree`
function is used to compare the original graph with its MST.
"""
import networkx as nx
import matplotlib.pyplot as plt
# Create a graph
G = nx.Graph()
G.add_edges_from(
[
(0, 1, {"weight": 4}),
(0, 7, {"weight": 8}),
(1, 7, {"weight": 11}),
(1, 2, {"weight": 8}),
(2, 8, {"weight": 2}),
(2, 5, {"weight": 4}),
(2, 3, {"weight": 7}),
(3, 4, {"weight": 9}),
(3, 5, {"weight": 14}),
(4, 5, {"weight": 10}),
(5, 6, {"weight": 2}),
(6, 8, {"weight": 6}),
(7, 8, {"weight": 7}),
]
)
# Find the minimum spanning tree
T = nx.minimum_spanning_tree(G)
# Visualize the graph and the minimum spanning tree
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, node_color="lightblue", node_size=500)
nx.draw_networkx_edges(G, pos, edge_color="grey")
nx.draw_networkx_labels(G, pos, font_size=12, font_family="sans-serif")
nx.draw_networkx_edge_labels(
G, pos, edge_labels={(u, v): d["weight"] for u, v, d in G.edges(data=True)}
)
nx.draw_networkx_edges(T, pos, edge_color="green", width=2)
plt.axis("off")
plt.show()
|
