# Changing some stuff to Kruskal's Algorithm

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]

• 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? Oct 18, 2012 at 2:58
• And welcome! I think you're our first Tico around! Oct 18, 2012 at 3:00
• 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! Oct 18, 2012 at 3:05
• Have you seen this? Oct 18, 2012 at 3:47
• If you solve your own question, please remember to post the answer Oct 18, 2012 at 4:15

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[]], 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[]], hh[pair[]]};
If[c1 =!= c2, Sow[vpairs[[jj, 2]]];
c1c2 = Union[c1, c2];
Do[hh[c1c2[[k]]] = c1c2, {k, Length[c1c2]}];
If[Length[hh[pair[]]] == 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]]