Minimum Spanning Tree: Prim’s Algorithm
April 9, 2010
We gather the vertices that are part of the tree in a list t and the rest of the vertices in a list r and loop until r is null, adding a vertex at each step; the initial vertex is just the first vertex on the input list. E is the minimum-weight edge to be joined, and v is the new vertex being added:
(define (prim vs es)
(let loop ((t (list (car vs))) (r (cdr vs)) (mst '()))
(if (null? r) mst
(let* ((e (min es t r))
(v (if (member (cadr e) t) (caddr e) (cadr e))))
(loop (cons v t) (remove v r) (cons e mst))))))
Min loops through the edges, comparing each edge that connects a vertex in t to a vertex in r to the current minimum, and returns the minimum-weight edge:
(define (min es t r)
(let loop ((es es) (min-e #f) (min-c #f))
(cond ((null? es) min-e)
((or (and (member (cadar es) r) (member (caddar es) r))
(and (member (cadar es) t) (member (caddar es) t)))
(loop (cdr es) min-e min-c))
((or (not min-c) (< (caar es) min-c))
(loop (cdr es) (car es) (caar es)))
(else (loop (cdr es) min-e min-c)))))
Most implementations of Prim’s algorithm are more complicated that this one, because they use some kind of priority queue to order the edges by weight, making the implementation more efficient. On large graphs that can pay off, but we won’t bother to make that improvement.
We used remove from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/mgrPcZel.
Programming Praxis 
[…] Praxis – Minimum Spanning Tree: Prim’s Algorithm By Remco Niemeijer In today’s Programming Praxis exercise we have to implement an algorithm for finding the minimum spanning tree […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/04/09/programming-praxis-minimum-spanning-tree-prims-algorithm/ for a version with comments):
import Data.List import qualified Data.List.Key as K prim :: (Eq a, Ord b) => [(a, a, b)] -> [(a, a, b)] prim es = f [(\(v,_,_) -> v) $ head es] [] where f vs t = if null r then t else f (union vs [x,y]) (m:t) where r = filter (\(a,b,_) -> elem a vs /= elem b vs) es m@(x,y,_) = K.minimum (\(_,_,c) -> c) rPython version:
usable_edges is a heap of edges having the first vertex in the MSP and the second vertex might not be in the MSP.
conn is a dictionary mapping verticies to edges. The tuples (c, n1, n2) in the dictionary have the cost first so that the heap operations will return the edges in order of increasing cost.
from collections import defaultdict from heapq import * def prim( nodes, edges ): conn = defaultdict( list ) for n1,n2,c in edges: conn[ n1 ].append( (c, n1, n2) ) conn[ n2 ].append( (c, n2, n1) ) mst = [] used = set( nodes[ 0 ] ) usable_edges = conn[ nodes[0] ][:] heapify( usable_edges ) while usable_edges: cost, n1, n2 = heappop( usable_edges ) if n2 not in used: used.add( n2 ) mst.append( ( n1, n2, cost ) ) for e in conn[ n2 ]: if e[ 2 ] not in used: heappush( usable_edges, e ) return mst #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 "prim:", prim( nodes, edges ) #output #prim: [('A', 'D', 5), ('D', 'F', 6), ('A', 'B', 7), ('B', 'E', 7), ('E', 'C', 5), ('E', 'G', 9)]this program is not working properly
A good working code for Prim’s Algorithm in C++
http://in.docsity.com/en-docs/Prim_Algorithm_-_C_plus_plus_Code
The code works perfectly fr the example. But line#11 may cause problem if the first node name has two or more characters. “used = set( [nodes[0]] )” to be safe?
Ye… This isn’t working perfectly.
i think:
used = set( nodes[ 0 ] )
must be:
used = set( [nodes[ 0 ]] )
or:
used = {nodes[ 0 ]}
(as lasso said ;-) ; replacement also then works for other nodes)