Prism Algorithm in Data Structure

Prism Algorithm is a type of greedy algorithm so finding the minimum spanning tree in this algorithm should have the property that edges in a set ($\pi$) always from a single tree that is a tree stats from arbitrary root vertex (R) and grows until the tree spans all the vertices (V).

Table of Contents

Algorithm With Explanation

for each u $\epsilon$ v[G]
do key [u] $\gets \infty$
$\pi$[u] $\gets$ NIL
key [r] $\gets \phi $
Q $ \gets $ v[G]
while Q $\neq \phi $
do u $\gets$ EXTRACT_MIN(Q)
for each v $\epsilon$ adjacent [u]
do if V $\epsilon$ Q and w(u,v) < key[v]
then $\pi$ [ v] $\gets$ u
key [v] $\gets$ w(u,v)

In this algorithm lines 1-5 set the key of each vertex to $\infty$, the parent of each u to NIL and the priority queue Q to certain all the vertices.
In lines 6-7, it identifies the vertex
In lines 8-11 for loop updates the key and $\pi$ field by every vertex [v] adjacent to u but not in the tree.

Prism Algorithm Based Problem with solution

Problem:

Solution:

Initialize all the vertex to infinity and the root vertex as 0

A	B	C	D	E	F	G	H	I	J
0	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$

Now visit vertex A and connect vertex B and D then the value of vertices will be as shown since AB = 4 and AD = 1 as given in the problem

A	B	C	D	E	F	G	H	I	J
0	4^A	$\infty$	1^A	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$

After this, the minimum span is between A and D.So, the solution will be

Now visit vertex D since AD is small than AB So, we will visit vertex D and its connecting vertex AD = 1, BD = 4, HD = 4, JD=4 as given in the problem

A	B	C	D	E	F	G	H	I	J
0	4^D	$\infty$	1^A	$\infty$	$\infty$	$\infty$	5^D	$\infty$	6^D

After this, the minimum span is between D and B. So, the solution will be

Now visit vertex B since DB is smaller. So, we will visit vertex B and its connecting vertex AB = 4, DB =4, JB=7, CB = 4

A	B	C	D	E	F	G	H	I	J
0	4^D	4^B	1^A	$\infty$	$\infty$	$\infty$	5^D	$\infty$	6^D

After this, the minimum span is between C and B. So, the solution will be

Now visit vertex C since CB is smaller. So, we will visit vertex C and its connecting vertex EC = 2, FC =1, CB = 4

A	B	C	D	E	F	G	H	I	J
0	4^D	4^B	1^A	2^C	1^C	$\infty$	5^D	$\infty$	6^D

After this, the minimum span is between F and C. So, the solution will be

Now visit vertex F since FC is smaller. So, we will visit vertex F and its connecting vertex CF =1, GF = 3, IF = 5

A	B	C	D	E	F	G	H	I	J
0	4^D	4^B	1^A	2^C	1^C	3^F	5^D	5^F	6^D

After this, the minimum span is between G and F. So, the solution will be

Now visit vertex G since FG is smaller. So, we will visit G and its connecting vertex EG=2, FG=3, IG=3, JG=4

A	B	C	D	E	F	G	H	I	J
0	4^D	4^B	1^A	2^G	1^C	3^F	5^D	3^G	4^G

After this, the minimum span is between E and G. So, the solution will be

Now visit vertex E since EG is smaller. So, we will visit vertex E and its connecting vertex EC = 2, EG = 2. But its connecting vertex is already visited so we visit vertex I since IG is second smaller and its connecting vertex IG = 3, IJ = 3