# Cost of the minimal spanning tree

I can create a grid graph with a random weights of edges and compute its minimal spanning tree by:

nx = 3; ny = 5;
G = GridGraph[{nx, ny}];
w = RandomInteger[{1, 6}, EdgeCount[G]];
GG = Graph[EdgeList[G], EdgeWeight -> w, VertexLabels -> "Name",
VertexLabelStyle -> Directive[Blue, Italic, 10],
EdgeLabels -> "EdgeWeight",
EdgeStyle -> Directive[Opacity[0.65], Blue],
EdgeLabelStyle -> Directive[Black, Italic, 10]];
k = FindSpanningTree[GG];
HighlightGraph[GG, k, GraphHighlightStyle -> "Thick"]


Is there a way to compute the cost of the minimal spanning tree without adding the weights manually?

Up to FindSpanningTree, the following does the job:

size[g_] :=With[{edges = EdgeList[FindSpanningTree[{g, 1}]]},  Total[PropertyValue[{g, #}, EdgeWeight] & /@ edges]]
size[GG]


30

• Thank you so much, it works perfectly! Feb 2 '17 at 14:25

With the current IGraph/M prerelease, you can simply use

Total@IGEdgeProp[EdgeWeight]@IGSpanningTree[GG]


IGSpanningTree preserves the edge weights in the tree. IGEdgeProp[EdgeWeight]` is an operator that extracts the edge weights into a list.