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.

Posted by programmingpraxis

Filed in Exercises

6 Comments »

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

Stanley said
April 7, 2010 at 4:13 AM
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

Mike said

May 12, 2010 at 8:58 PM

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

Assignment in CS312 « chrisjemiekitsei said
August 7, 2012 at 4:06 AM
[…] 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 […]
Samar Yadav said
June 23, 2016 at 8:21 AM
where is DisjointSet() class. please provide the link.
programmingpraxis said
June 23, 2016 at 12:37 PM
In the previous exercise, as given in the link in the first sentence.
ivan said
June 12, 2018 at 6:58 AM
i get an error on print kruskal(nodes,edges)
it says invalid syntax… what’s wrong?

Programming Praxis