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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you so much, it works perfectly! $\endgroup$ Commented Feb 2, 2017 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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.