## 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

### 6 Responses to “Minimum Spanning Tree: Kruskal’s Algorithm”

1. Stanley said

-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

2. Mike said

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:

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)]

```
3. […] 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 […]