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.

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 635 other followers

%d bloggers like this: