Minimum Spanning Tree: Prim’s Algorithm

April 9, 2010

In the previous exercise we studied Kruskal’s algorithm for computing the minimum spanning tree of a weighted graph. Today we study an algorithm developed in 1930 by the Czech mathematician Vojtěch Jarník and rediscovered by Robert Prim in 1957.

Kruskal’s algorithm works by creating a singleton tree for each vertex and merging the trees by taking at each step the minimum-weight edge that joins two trees. Prim’s algorithm is the opposite; it starts with a single vertex and repeatedly joins the minimum-weight edge that joins the tree to a non-tree vertex. At each step the tree is a minimum spanning tree of the vertices that have been processed thus far.

Your task is to write a program to find the minimum spanning tree of a graph using Prim’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.

Pages: 1 2

5 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[0] ][:]
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