Prim's algorithm Assignment Help

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for any connected weighted undirected graph. This means it finds a subset of the edges that forms a tree which includes each and every vertex, in which the complete weight of all the edges in the tree is minimized. It's also known as the DJP algorithm, the Jarník algorithm, or even the Prim-Jarník algorithm.

Pseudocode for the Prim Algorithm

  • INPUT : n, c[ e(ij) ], i, j belonging to 1,...,n.
  • OUTPUT : p(j) j = 2,...,n (pointer of peaks j father in the T tree).

Prim Algorithm STEPS

    1. : ( initializations ).
    O = {1}  ( V(1) root of the T tree ).
    P =  2,...,n 
    For each j belonging to P : e(j): = c[ e(j1) ] , p(j) = 1

( All peaks connected to the root. Through description from the cost function: e(j) = infinite if V(j) doesn't connect to V(1).).

    2. Select a k for which e(k)  e(j) for each j belong to P. 
    In case of tight select the smaller one.
    Exchange the O set with the set produced by the union of the O set and {k}.
    Exchange the P set with the set produced by the difference of the P set and {k{.
    ( P- P- k )
     If P = 0 then stop. 
    3. For every j belong to P compare e(j) with c[ e(kj) ].
    If e(j)  c[ e(kj) ] exchange e(j) - c( e(kj) ). 
    Return to Step 1. 

Prim's algorithm Example

CPS 542 Prim’s algorithm Assignment 5