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.

About these ads

Pages: 1 2

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

  1. [...] 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 [...]

  2. Remco Niemeijer said

    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) r
    
  3. Mike said

    Python 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)]
    
  4. lalit said

    this program is not working properly

  5. vishv said

    A good working code for Prim’s Algorithm in C++

    http://in.docsity.com/en-docs/Prim_Algorithm_-_C_plus_plus_Code

  6. Lasso said

    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?

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: