# 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()
[
(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()
```

Total running time of the script: ( 0 minutes 0.086 seconds)

Gallery generated by Sphinx-Gallery