{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Minimum Spanning Tree\n\nA minimum spanning tree (MST) is a subset of edges in a weighted, \nconnected graph that connects all vertices together with the \nminimum possible total edge weight. The `minimum_spanning_tree`\nfunction is used to compare the original graph with its MST.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import networkx as nx\nimport matplotlib.pyplot as plt\n\n# Create a graph\nG = nx.Graph()\nG.add_edges_from(\n [\n (0, 1, {\"weight\": 4}),\n (0, 7, {\"weight\": 8}),\n (1, 7, {\"weight\": 11}),\n (1, 2, {\"weight\": 8}),\n (2, 8, {\"weight\": 2}),\n (2, 5, {\"weight\": 4}),\n (2, 3, {\"weight\": 7}),\n (3, 4, {\"weight\": 9}),\n (3, 5, {\"weight\": 14}),\n (4, 5, {\"weight\": 10}),\n (5, 6, {\"weight\": 2}),\n (6, 8, {\"weight\": 6}),\n (7, 8, {\"weight\": 7}),\n ]\n)\n\n# Find the minimum spanning tree\nT = nx.minimum_spanning_tree(G)\n\n# Visualize the graph and the minimum spanning tree\npos = nx.spring_layout(G)\nnx.draw_networkx_nodes(G, pos, node_color=\"lightblue\", node_size=500)\nnx.draw_networkx_edges(G, pos, edge_color=\"grey\")\nnx.draw_networkx_labels(G, pos, font_size=12, font_family=\"sans-serif\")\nnx.draw_networkx_edge_labels(\n G, pos, edge_labels={(u, v): d[\"weight\"] for u, v, d in G.edges(data=True)}\n)\nnx.draw_networkx_edges(T, pos, edge_color=\"green\", width=2)\nplt.axis(\"off\")\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.7"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Generated by dwww version 1.16 on Wed Apr 8 11:24:45 CEST 2026.