Changing some stuff to Kruskal's Algorithm

Question

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] 
Kruskal[G]

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}];
   vpairs=Sort[Flatten[
    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]]