5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

Up to FindSpanningTree, the following does the job:

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

30

$\endgroup$
  • $\begingroup$ Thank you so much, it works perfectly! $\endgroup$ – Jan Valdman Feb 2 '17 at 14:25
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.