Page 294 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 14: Network Flows

14.3.2 Prim’s Algorithm Notes

Prim’s algorithm is an algorithm in graph theory that finds a minimum spanning tree for a

connected weighted graph. This means it finds a subset of the edges that forms a tree that includes
every vertex, where the total weight of all the edges in the tree is minimized.
The algorithm was discovered in 1930 by mathematician Vojtìch Jarník and later independently by
computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore
it is sometimes called the DJP algorithm, the Jarník algorithm, or the Prim-Jarník algorithm.

Figure 14.13: Diagrammatic Representation of Prim’s Algorithm
v v v v
0 2 1 0 2 1
0 2 5 0 1 5

1 6 1 d v 2 1 6 1 3 v 2
3 3
1 1 1 1 1
v v v 1 v
4 3 4 3
Algorithm

Let G = (V, E) which is represented by an adjacency list Adj. Some support data structures:
1. d is an array of size |V|. Each d[i] contains the shortest distance for vertex i
2. Q is a priority queue of UNKNOWN vertices.
3. p is an array of size |V|. Each P[i] contains the parent of vertex i.
4. s is the source vertex.

PRIM(G, s)

1. Initialize d[s] with 0, P[s] with 0, and
all other d[i] (i!=s) with a positive infi nity and
p[i] (i!=s) with 0.
2. Q <- V // initialize Q with all vertices as UNKNOWN
3. while Q not empty do

4. begin
5. u <- ExtractMin(Q) // Q is modifi ed
6. Mark u as KNOWN // Dequeing u is the same as marking it as KNOWN
7. for each vertex v in Adj[u] do
8. begin
9. if v is UNKNOWN and d[v] > weight(u, v), then do
10. begin
11. d[v] = weight(u, v) // update with shorter weight
12. p[v] = u // update v’s parent as v

LOVELY PROFESSIONAL UNIVERSITY 289