## 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.

Pages: 1 2

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

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.

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