Finding the Cheapest Layout with NetworkX's Minimum Spanning Tree

The problem: connect every city at the lowest cost

You have a list of cities and the cost of running a direct wire between each pair. You need a set of wires that reaches every city, forms no cycles, and keeps total cost as low as possible. That is the classic minimum spanning tree (MST) problem, and NetworkX solves it in one line.

Building the weighted graph

NetworkX represents an undirected weighted graph with nx.Graph(), storing costs in the weight edge attribute. This helper converts a symmetric cost matrix into a graph (run it in any Python environment with networkx>=2.0 installed; no special permissions needed):

import networkx as nx

def build_graph_from_cost_matrix(cost_matrix, cities):
    """Create an undirected graph where cost_matrix[i][j] is the wiring cost."""
    G = nx.Graph()
    G.add_nodes_from(cities)
    for i, u in enumerate(cities):
        for j, v in enumerate(cities):
            if i < j:  # skip duplicates and self-loops
                w = cost_matrix[i][j]
                if w is not None and w >= 0:
                    G.add_edge(u, v, weight=w)
    return G

Computing the MST

NetworkX wraps Kruskal's algorithm in a single call:

mst = nx.minimum_spanning_tree(G, weight='weight')

It returns a new Graph containing only the MST edges. Confirm the algorithm and return type yourself with help(nx.minimum_spanning_tree).

Worked example: five cities

Take cities A–E with this symmetric cost matrix (∞ means no direct link):

cities = ['A', 'B', 'C', 'D', 'E']
cost = [
    [None, 4, 2, 5, None],
    [4, None, 3, None, 1],
    [2, 3, None, 4, 2],
    [5, None, 4, None, 3],
    [None, 1, 2, 3, None],
]

G = build_graph_from_cost_matrix(cost, cities)
mst = nx.minimum_spanning_tree(G, weight='weight')

print('MST edges:', list(mst.edges(data=True)))
total = sum(d['weight'] for u, v, d in mst.edges(data=True))
print('Total weight:', total)

Working through Kruskal's algorithm by hand: it picks B–E (1), A–C (2), C–E (2), and D–E (3), skipping edges that would close a cycle. The expected total is 8. Verify the result two ways: nx.is_tree(mst) should return True (connected and acyclic), and the printed total should equal 8.

Trade-offs and limitations

• Memory copy: the function builds a new graph, duplicating edge data. For very large sparse networks this can be prohibitive; consider implementing Kruskal directly over an edge list with a union-find structure instead.
• Parallel edges: on a multigraph, parallel edges collapse to the smallest weight, which may not match your intended model.
• Weight assumptions: the routine assumes numeric, non-negative weights; negative values can produce unexpected results.
• Version: minimum_spanning_tree exists from NetworkX 2.0 onward; 1.x releases require a manual implementation.

Make it reusable and testable

Wrap the logic in a typed helper and guard it with a unit test:

def minimum_wiring_plan(cost_matrix, cities):
    G = build_graph_from_cost_matrix(cost_matrix, cities)
    mst = nx.minimum_spanning_tree(G, weight='weight')
    edges = [(u, v, d['weight']) for u, v, d in mst.edges(data=True)]
    return edges, sum(w for _, _, w in edges)

def test_example():
    edges, total = minimum_wiring_plan(cost, cities)
    assert total == 8
    assert nx.is_tree(nx.Graph(edges))

Run the test with pytest (or adapt it to unittest) to catch regressions. Then feed updated cost matrices into minimum_wiring_plan inside your network-planning pipeline and use the returned edge list to generate the final wiring diagram. NetworkX's well-tested MST routine gives you a readable prototype today, with a clear path to a custom Kruskal implementation if memory ever becomes the bottleneck.