I'm trying to modify this algorithm: http://demonstrations.wolfram.com/ConnectingTownsUsingKruskalsAlgorithm/

The thing is that I want to receive a Graph (declared outside, with all its vertex, edges and weights) in the Kruskal's function and start from there, using maybe a WeightedAdjacencyMatrix[G] and sort the weights and returning them. It's just a practice I want to do, because I'm learning Mathematica, so I'm still a noob with this. To be more specific with my question, I just want to know where and how I can replace parts from the code, with the things I mentioned above. This is my idea, of course without the Kruskal's implementation:

G = Graph[{a \[UndirectedEdge] b, a \[UndirectedEdge] d, 
a \[UndirectedEdge] f, b \[UndirectedEdge] c, 
b \[UndirectedEdge] d, b \[UndirectedEdge] e, 
c \[UndirectedEdge] e, c \[UndirectedEdge] g, 
d \[UndirectedEdge] e, d \[UndirectedEdge] f, 
d \[UndirectedEdge] g, e \[UndirectedEdge] g, 
f \[UndirectedEdge] g}, 
EdgeWeight -> {5, 6, 7, 5, 5, 4, 3, 3, 2, 2, 3, 1, 2}, 
VertexLabels -> "Name", ImagePadding -> 10] 
  • $\begingroup$ Sorry José, but I can't understand "I just want to know where and how I can replace parts from the code" Can you explain that further? $\endgroup$ Oct 18, 2012 at 2:58
  • 1
    $\begingroup$ And welcome! I think you're our first Tico around! $\endgroup$ Oct 18, 2012 at 3:00
  • $\begingroup$ Yeah sorry for not explaining it well, and thanks for your welcome. I think I did a mess actually. I want to change the implementation of the function, I want it to receive the Graph, with its vertex, edges, and weights. And find the MinimumSpanningTree. It's like implementing the MinimumSpanningTree function actually, step by step. I was looking for the Combinatorica implemntation but I need to have it into one same function. Sorry if I'm not explaining it well! Thanks for your time! $\endgroup$ Oct 18, 2012 at 3:05
  • 1
    $\begingroup$ Have you seen this? $\endgroup$ Oct 18, 2012 at 3:47
  • 1
    $\begingroup$ If you solve your own question, please remember to post the answer $\endgroup$ Oct 18, 2012 at 4:15

1 Answer 1


I don't exactly know that I understand you correctly. You have some graph G in structure Graph. Then you want to use MST (Prim/Kruskal) algorithm to obtain changed G which is MST graph. I tried that but it didn't work in M8.

Here is how I did that the other way:

  1. I prepared graph in nested list graph (matrix nxn), where graph[[i,j]] are weights between i and j vertices. Of course that matrix, in principle, should be symmetric and weights graph[[i,i]] should be 0.
  2. I use MST algorithm on that matrix, for example Kruskal:

     kruskal[pts_] := 
      Module[{n = Length[pts[[2]]], vpairs, jj = 0, hh, pair, dist, c1, c2,
    c1c2}, Do[hh[k] = {k}, {k, n}];
     Table[{pts[[k, l]], {k, l}}, {k, 1, n - 1}, {l, k + 1, n}], 1]];
     First[Last[Reap[While[jj < Length[vpairs], jj++;
      {dist, pair} = vpairs[[jj]];
      {c1, c2} = {hh[pair[[1]]], hh[pair[[2]]]};
      If[c1 =!= c2, Sow[vpairs[[jj, 2]]];
       c1c2 = Union[c1, c2];
       Do[hh[c1c2[[k]]] = c1c2, {k, Length[c1c2]}];
       If[Length[hh[pair[[1]]]] == n, Break[]];];]]]]]
  3. Use that Kruskal function on your matrix: kruskal@graph. Function return list of pairs, something like: {{2,5},{5,7},...}

  4. Then you must change that list to object that can be understand by Graph function in Mathematica. Use that function:

    mstListToEdge[mstList_] := mstList /. {x_, y_} :> x \[UndirectedEdge] y
  5. In the end use list from 4. and graph matrix to generate Graph. You will obtain MST graph picture with weights.

    graphMst[edges_, graph_] :=
     Graph[edges, VertexLabels -> "Name", ImagePadding -> 10, 
      GraphLayout -> "SpringElectricalEmbedding",
      EdgeWeight -> 
       Array[graph[[edges[[#, 1]], 
          edges[[#, 2]]]] & (*mstWeights *), Length@edges]]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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