## Minimum Spanning Tree: Kruskal’s Algorithm

### April 6, 2010

Here is our solution, which follows the pseudo-code precisely:

`(define (kruskal vs es)`

(let ((f (make-disjoint-set string-hash string=? #f 19))

(n (- (length vs) 1))

(es (sort (lambda (x y) (< (car x) (car y))) es)))

(do ((vs vs (cdr vs))) ((null? vs))

(f 'make-set (car vs)))

(let loop ((es es) (zs '()) (n n))

(cond ((zero? n) zs)

((string=? (f 'find (cadar es)) (f 'find (caddar es)))

(loop (cdr es) zs n))

(else (f 'union (cadar es) (caddar es))

(loop (cdr es) (cons (car es) zs) (- n 1)))))))

Here is the computation of the minimum spanning tree for the sample graph shown on the previous page:

`> (define vertices '("A" "B" "C" "D" "E" "F" "G"))`

> (define edges '((5 "A" "D") (7 "A" "B") (9 "B" "D")

(8 "B" "C") (5 "C" "E") (7 "B" "E") (15 "D" "E")

(6 "D" "F") (8 "E" "F") (9 "E" "G") (11 "F" "G")))

> (kruskal vertices edges)

((9 "E" "G") (7 "B" "E") (7 "A" "B") (6 "D" "F") (5 "C" "E")

(5 "A" "D"))

We used disjoint sets from the previous exercise and hash tables and sort from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/HCnZJoTE.

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 […]