MIN_SPANNING_TREE
A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
This is a classic optimization problem with applications in designing networks (e.g., telecommunications, transportation, water supply) where you want to connect all points with the minimum total length of cable or pipe.
The function returns an Excel Data Type where the primary value is the total weight of the MST. The set of edges included in the MST is available as an ‘Edges’ property.
Excel Usage
=MIN_SPANNING_TREE(edges)edges(list[list], required): 2D array of edges [source, target, weight].
Returns (dict): Data type containing the total MST weight (basicValue) and the list of edges.
Example 1: Simple MST
Inputs:
| edges | ||
|---|---|---|
| A | B | 1 |
| B | C | 2 |
| A | C | 3 |
Excel formula:
=MIN_SPANNING_TREE({"A","B",1;"B","C",2;"A","C",3})Expected output:
{"type":"Double","basicValue":3,"properties":{"Total Weight":{"type":"Double","basicValue":3},"Edges":{"type":"Array","elements":[[{"type":"String","basicValue":"A"},{"type":"String","basicValue":"B"},{"type":"Double","basicValue":1}],[{"type":"String","basicValue":"B"},{"type":"String","basicValue":"C"},{"type":"Double","basicValue":2}]]}}}
Example 2: Multiple paths MST
Inputs:
| edges | ||
|---|---|---|
| A | B | 10 |
| B | C | 1 |
| A | C | 5 |
| C | D | 1 |
Excel formula:
=MIN_SPANNING_TREE({"A","B",10;"B","C",1;"A","C",5;"C","D",1})Expected output:
{"type":"Double","basicValue":7,"properties":{"Total Weight":{"type":"Double","basicValue":7},"Edges":{"type":"Array","elements":[[{"type":"String","basicValue":"A"},{"type":"String","basicValue":"C"},{"type":"Double","basicValue":5}],[{"type":"String","basicValue":"B"},{"type":"String","basicValue":"C"},{"type":"Double","basicValue":1}],[{"type":"String","basicValue":"C"},{"type":"String","basicValue":"D"},{"type":"Double","basicValue":1}]]}}}
Example 3: Disconnected graph (Spanning Forest)
Inputs:
| edges | ||
|---|---|---|
| A | B | 1 |
| C | D | 1 |
Excel formula:
=MIN_SPANNING_TREE({"A","B",1;"C","D",1})Expected output:
{"type":"Double","basicValue":2,"properties":{"Total Weight":{"type":"Double","basicValue":2},"Edges":{"type":"Array","elements":[[{"type":"String","basicValue":"A"},{"type":"String","basicValue":"B"},{"type":"Double","basicValue":1}],[{"type":"String","basicValue":"C"},{"type":"String","basicValue":"D"},{"type":"Double","basicValue":1}]]}}}
Example 4: Numeric IDs MST
Inputs:
| edges | ||
|---|---|---|
| 1 | 2 | 100 |
| 2 | 3 | 50 |
| 1 | 3 | 10 |
Excel formula:
=MIN_SPANNING_TREE({1,2,100;2,3,50;1,3,10})Expected output:
{"type":"Double","basicValue":60,"properties":{"Total Weight":{"type":"Double","basicValue":60},"Edges":{"type":"Array","elements":[[{"type":"String","basicValue":"1"},{"type":"String","basicValue":"3"},{"type":"Double","basicValue":10}],[{"type":"String","basicValue":"2"},{"type":"String","basicValue":"3"},{"type":"Double","basicValue":50}]]}}}
Python Code
import networkx as nx
def min_spanning_tree(edges):
"""
Find the minimum spanning tree (MST) of an undirected graph.
See: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_tree.html
This example function is provided as-is without any representation of accuracy.
Args:
edges (list[list]): 2D array of edges [source, target, weight].
Returns:
dict: Data type containing the total MST weight (basicValue) and the list of edges.
"""
try:
def to2d(x):
return [[x]] if not isinstance(x, list) else x
edges = to2d(edges)
if not isinstance(edges, list) or not edges:
return "Error: edges must be a non-empty 2D list"
G = nx.Graph()
processed_edges = []
for row in edges:
if isinstance(row, list) and len(row) >= 2:
u, v = str(row[0]), str(row[1])
if len(row) >= 3 and row[2] not in (None, ""):
try:
w = float(row[2])
except (TypeError, ValueError):
return f"Error: Invalid edge weight '{row[2]}'"
else:
w = 1.0
processed_edges.append((u, v, w))
if not processed_edges:
return "Error: No valid edges found in input"
G.add_weighted_edges_from(processed_edges)
T = nx.minimum_spanning_tree(G, weight='weight')
total_weight = T.size(weight='weight')
mst_edges = []
for u, v, d in T.edges(data=True):
weight = d.get('weight', 1.0)
mst_edges.append([
{"type": "String", "basicValue": str(u)},
{"type": "String", "basicValue": str(v)},
{"type": "Double", "basicValue": float(weight)}
])
return {
"type": "Double",
"basicValue": float(total_weight),
"properties": {
"Total Weight": { "type": "Double", "basicValue": float(total_weight) },
"Edges": {
"type": "Array",
"elements": mst_edges
}
}
}
except Exception as e:
return f"Error: {str(e)}"