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.

About these ads

Pages: 1 2

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

  1. Stanley said

    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

  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:
            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)]
    
    
  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 [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: