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.
Programming Praxis 
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.
from operator import itemgetter def kruskal( nodes, edges ): forest = DisjointSet() mst = [] for n in nodes: forest.add( n ) sz = len(nodes) - 1 for e in sorted( edges, key=itemgetter( 2 ) ): n1, n2, _ = e t1 = forest.find(n1) t2 = forest.find(n2) if t1 != t2: mst.append(e) sz -= 1 if sz == 0: return mst forest.union(t1, t2) #test nodes = list( "ABCDEFG" ) edges = [ ("A", "B", 7), ("A", "D", 5), ("B", "C", 8), ("B", "D", 9), ("B", "E", 7), ("C", "E", 5), ("D", "E", 15), ("D", "F", 6), ("E", "F", 8), ("E", "G", 9), ("F", "G", 11)] print kruskal( nodes, edges ) #output: [('A', 'D', 5), ('C', 'E', 5), ('D', 'F', 6), ('A', 'B', 7), ('B', 'E', 7), ('E', 'G', 9)][…] 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 […]
where is DisjointSet() class. please provide the link.
In the previous exercise, as given in the link in the first sentence.
i get an error on print kruskal(nodes,edges)
it says invalid syntax… what’s wrong?