## Minimum Spanning Tree: Kruskal’s Algorithm

### April 6, 2010

We studied disjoint sets in the previous exercise. In today’s exercise we use disjoint sets to implement Kruskal’s algorithm to find the minimum spanning tree of a graph.

A graph is a generalized tree in which vertices may be connected by edges in any configuration. Edges may be directed (from one vertex to another) or undirected, and may be weighted or unweighted. On an undirected weighted graph, a spanning tree is a collection of edges that connects all vertices, and a minimum spanning tree has the lowest total edge-weight of all possible spanning trees. A minimum spanning tree always has one less edge than there are vertices in the graph.

Joseph Kruskal developed the following algorithm for determining the minimum spanning tree in 1956, where *V* is the set of vertices and *E* is the set of weighted edges:

- Create a disjoint set in which each vertex is a singleton partition.
- Loop over the edges in order by increasing weight
- If the current edge connects two unconnected partitions
- Add the edge to the minimum spanning tree
- Merge the two partitions
- If the spanning tree is complete, return it, otherwise go to the next-larger edge

Your task is to write a program that implements Kruskal’s algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

ad-hoc Josl version:

-include myhelpers.j

-include list.j

-variable ungrouped-nodes grouped-nodes ungrouped-edges grouped-edges is-first

# ( — i:max-val)

max-int

1 63 <two-chars

0 over at chr

swap 1 swap at chr

# (b:x b:y — b:z)

xor?

not if

# if not y, return b

else

not # if y, return not b

end

# (s:edge-name)

is-ungrouped?

>two-chars

ungrouped-nodes @ has-key?

swap ungrouped-nodes @ has-key?

xor? is-first @ or?

# ( — s:min-name i:min-dist)

min-ungrouped-edge

“none” max-int # (min-name min-dist)

ungrouped-edges @ keys each

dup ungrouped-edges @ @ # (min-name min-dist cur-name cur-dist)

over is-ungrouped?

if

dup 3 pick # (min-name min-dist cur-name cur-dist cur-dist min-dist)

two-chars # (min-name min-dist first-char second-char)

group-a-node

group-a-node # (min-name min-dist)

group-an-edge # ()

# stack-show

# ( — )

print-all

“ungrouped-nodes: ” print ungrouped-nodes @ printlist “” println

“grouped-nodes: ” print grouped-nodes @ printlist “” println

“ungrouped-edges: ” print ungrouped-edges @ printlist “” println

“grouped-edges: ” print grouped-edges @ printlist “” println

# (d:acc x:val s:key –)

d, 2 pick !

main

1 is-first !

dict ungrouped-nodes !

dict grouped-nodes !

dict ungrouped-edges !

dict grouped-edges !

ungrouped-nodes @ 1 “A” d, 1 “B” d,

1 “C” d, 1 “D” d, 1 “E” d, 1 “F” d, 1 “G” d,

ungrouped-nodes !

stack-show

ungrouped-edges @ 5 “AD” d, 7 “AB” d, 9 “BD” d, 8 “BC” d,

5 “CE” d, 7 “BE” d, 15 “DE” d, 6 “DF” d, 8 “EF” d, 9 “EG” d, 11 “FG” d,

ungrouped-edges !

stack-show

while ungrouped-nodes @ len 0 >

do

min-ungrouped-edge # (s:min-name i:min-dist)

group-edge

end

print-all

Python version is a straight forward implementation of the algorithm.

Uses DisjointSet class from the previous exercise.

[...] to write a program that implements Kruskalâ€™s algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments [...]