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

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

```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 ][:]
heapify( usable_edges )

while usable_edges:
cost, n1, n2 = heappop( usable_edges )
if n2 not in used:
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] )” to be safe?

7. ji said

Ye… This isn’t working perfectly.

8. Lars van gemerden said

i think:

used = set( nodes[ 0 ] )

must be:

used = set( [nodes[ 0 ]] )

or:

used = {nodes[ 0 ]}

9. Lars van gemerden said

(as lasso said ;-) ; replacement also then works for other nodes)