Tutorials 
Minimum Spanning Trees with NetworkX
A spanning tree of a connected graph touches every node exactly once with no cycles. A *minimum* spanning tree (MST) does this using edges with the smallest possible total weight. MSTs have many practical uses: designing minimum-cost road or pipeline networks, clustering data points, approximating the travelling salesman problem, or building efficient communication networks. NetworkX implements Kruskal's and Prim's algorithms under the hood, both accessible through a single function call. ### Computing a Minimum Spanning Tree `nx.minimum_spanning_tree` finds the MST of any weighted undirected graph. The result is itself a NetworkX graph containing only the MST edges.
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_weighted_edges_from([
(0, 1, 4), (0, 2, 2), (0, 3, 7),
(1, 2, 1), (1, 4, 5),
(2, 3, 3), (2, 4, 8),
(3, 4, 6), (3, 5, 9),
(4, 5, 2),
])
T = nx.minimum_spanning_tree(G)
total_weight = T.size(weight="weight")
print(f"MST edges ({T.number_of_edges()} edges, total weight = {total_weight}):")
for u, v, w in sorted(T.edges(data="weight")):
print(f" {u}—{v} weight={w}")- `add_weighted_edges_from` takes (u, v, weight) triples and stores the weight as the `"weight"` edge attribute. - `nx.minimum_spanning_tree(G)` uses Kruskal's algorithm by default; pass `algorithm="prim"` for Prim's. - `T.size(weight="weight")` sums all edge weights in the tree — for this graph the MST cost is the sum of the selected edges. ### Visualizing Original Graph vs MST Drawing the MST edges in a different color on top of the full graph makes it easy to see which edges were selected.
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_weighted_edges_from([
(0, 1, 4), (0, 2, 2), (0, 3, 7),
(1, 2, 1), (1, 4, 5),
(2, 3, 3), (2, 4, 8),
(3, 4, 6), (3, 5, 9),
(4, 5, 2),
])
T = nx.minimum_spanning_tree(G)
mst_edges = set(T.edges())
pos = nx.spring_layout(G, seed=7)
edge_colors = ["crimson" if (u, v) in mst_edges or (v, u) in mst_edges
else "lightgray" for u, v in G.edges()]
edge_widths = [3 if (u, v) in mst_edges or (v, u) in mst_edges
else 1 for u, v in G.edges()]
labels = nx.get_edge_attributes(G, "weight")
plt.figure(figsize=(7, 6))
nx.draw(G, pos, with_labels=True, node_color="steelblue", node_size=600,
font_color="white", font_size=10, edge_color=edge_colors, width=edge_widths)
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_size=8)
plt.title(f"MST highlighted (red, total weight={T.size(weight='weight')})")
plt.tight_layout()
plt.show()/var/folders/8l/xyy39wqj1c71tdcxq7vndwvr0000gn/T/ipykernel_68562/3968162840.py:27: UserWarning: This figure includes Axes that are not compatible with tight_layout, so results might be incorrect. plt.tight_layout()
- MST edges are colored red and drawn wider (`width=3`) to stand out from the non-MST gray edges. - `set(T.edges())` makes membership checks O(1); we check both orderings `(u, v)` and `(v, u)` because edge direction in undirected graphs is not guaranteed. - `nx.draw_networkx_edge_labels` overlays the weight values on each edge. ### Kruskal vs Prim: Comparing Algorithms NetworkX supports both Kruskal's (sorts all edges by weight and adds greedily) and Prim's (grows the tree from a starting node). Both always produce an MST; they differ in efficiency for dense vs sparse graphs.
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([
(0, 1, 4), (0, 2, 2), (0, 3, 7),
(1, 2, 1), (1, 4, 5),
(2, 3, 3), (2, 4, 8),
(3, 4, 6), (3, 5, 9),
(4, 5, 2),
])
T_kruskal = nx.minimum_spanning_tree(G, algorithm="kruskal")
T_prim = nx.minimum_spanning_tree(G, algorithm="prim")
print("Kruskal MST edges:", sorted(T_kruskal.edges()))
print("Prim MST edges:", sorted(T_prim.edges()))
print("Same total weight:", T_kruskal.size(weight="weight") == T_prim.size(weight="weight"))- Both algorithms return the same total weight (they both find an MST), but may pick different edges when multiple MSTs have the same cost. - Kruskal's runs in O(m log m) — it dominates for sparse graphs. Prim's with a priority queue runs in O(m + n log n) — better for dense graphs. - The `sorted` call normalizes edge ordering so the outputs are easy to compare. ### Maximum Spanning Tree Sometimes you want the *maximum* spanning tree — for example, to find the most reliable communication network or the highest-weight set of connections. Simply negate all edge weights and compute the MST.
import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_weighted_edges_from([
(0, 1, 4), (0, 2, 2), (0, 3, 7),
(1, 2, 1), (1, 4, 5),
(2, 3, 3), (2, 4, 8),
(3, 4, 6), (3, 5, 9),
(4, 5, 2),
])
T_max = nx.maximum_spanning_tree(G)
pos = nx.spring_layout(G, seed=7)
max_edges = set(T_max.edges())
colors = ["crimson" if (u,v) in max_edges or (v,u) in max_edges else "lightgray"
for u, v in G.edges()]
widths = [3 if (u,v) in max_edges or (v,u) in max_edges else 1
for u, v in G.edges()]
labels = nx.get_edge_attributes(G, "weight")
plt.figure(figsize=(7, 6))
nx.draw(G, pos, with_labels=True, node_color="steelblue", node_size=600,
font_color="white", font_size=10, edge_color=colors, width=widths)
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_size=8)
plt.title(f"Maximum Spanning Tree (red, total weight={T_max.size(weight='weight')})")
plt.tight_layout()
plt.show()/var/folders/8l/xyy39wqj1c71tdcxq7vndwvr0000gn/T/ipykernel_68562/2906610124.py:28: UserWarning: This figure includes Axes that are not compatible with tight_layout, so results might be incorrect. plt.tight_layout()
- `nx.maximum_spanning_tree(G)` is a convenience wrapper that negates weights internally and runs the standard MST algorithm. - The maximum spanning tree selects the heaviest edges that still form a spanning tree — it prefers edges with weight 9, 8, 7 over 1, 2, 3. - Maximum spanning trees are used in clustering (Kruskal's single-linkage) and in building maximum bottleneck paths between node pairs. Next, explore [shortest path analysis with NetworkX](/tutorials/shortest-path-analysis-in-networkx) to find optimal routes through weighted graphs.