In this method, minimum spanning tree is constructed in successive stages. One node is picked as a root and an edge is added (i.e) an associated vertex is added to the tree, until all the vertices are present in the tree with |V| - 1 edges.

__PRIMâ€™S
ALGORITHM__

In this method, minimum spanning tree is
constructed in successive stages. One node is picked as a root and an edge is
added (i.e) an associated vertex is added to the tree, until all the vertices
are present in the tree with |V| - 1 edges.

**The Strategy**

i.
One node is picked as a root node (u) from the
given connected graph.

ii.
At each stage choose a new vertex v from u, by
considering an edge (u,v) with minimum cost among all edges from u, where u is
already in the tree ad v is not in the tree.

iii.
The prims algorithm table is constructed with three
parameters. They are

^{Ã˜ }known â€“
known vertex i.e., processed vertex is indicated by 1. Unknown vertex is
indicated by zero.^{}

^{ }

^{Ã˜ }d_{v} - Weight of the shortest arc connecting v to
the known vertex.^{}

^{ }

^{Ã˜ }p_{v} - It contains last vertex (i.e.,) current
vertex to cause a change in d_{v.}^{}

^{ }

iv.
After selecting the vertex v, the update rule is
applied for each unknown w adjacent to v. The
rule is d_{w} = min (d_{w} , C_{w,v}), that is more
than one path exist between v to w then d_{w} is updated with minimum
cost.

**Example:**

i.
v_{1} is selected as initial node in the
spanning tree and construct initial configuration of the table.

ii.
v1 is declared as known vertex. Then its adjacent
vertices v2, v3, v4 are updated.

T[v_{2}].dist
= min(T[v_{2}].dist, Cv_{1},v_{2}) = min (âˆž ,2) = 2

T[v_{3}].dist
= min(T[v_{3}].dist, Cv_{1},v_{3}) = min (âˆž ,4) = 2

T[v_{4}].dist
= min(T[v_{4}].dist, Cv_{1},v_{4}) = min (âˆž ,1) = 2

iii.
Among all adjacent vertices V_{2,} V_{3,}
V_{4.} V_{1} -> V_{4} distance is small. So V_{4}
is selected and declared as known vertex. Its adjacent vertices distance are
updated.

^{Ã¼ }V_{1} is not examined because it is known vertex.^{}

^{ }

^{Ã¼ }No change
in V_{2} , because it has dv = 2 and the edge cost from V_{4}
-> V_{2} = 3.^{}

T[v_{3}].dist
= min(T[v3].dist, Cv_{4},v_{3}) = min (4 ,2) = 2

T[v_{5}].dist
= min(T[v_{5}].dist, Cv_{4},v_{5}) = min (âˆž ,7) = 7

T[v_{6}].dist
= min(T[v_{6}].dist, Cv_{4},v_{6} ) = min (âˆž ,8) = 8

T[v_{7}].dist
= min(T[v_{7}].dist, Cv_{4},v_{7} ) = min (âˆž ,4) = 4

iv.
Among all either we can select v_{2,} or v_{3}
whose d_{v} = 2, smallest among
v_{5,} v_{6} and v_{7.}

^{Ã¼ }v_{2}
is declared as known vertex.^{}

^{ }

^{Ã¼ }Its
adjacent vertices are v1, v4 and v5. v1, v4 are known vertex, no change in
their dv value.^{}

^{ }

T[v_{5}].dist
= min(T[v5].dist, Cv_{2},v_{5}) = min (7 ,10) = 7

v.
Among all vertices v3â€Ÿs dv value is lower so v3 is
selected. v3â€Ÿs adjacent vertices are v1, v4 and v6. No changes in v1 and v4.

T[v_{6}].dist
= min(T[v6].dist, Cv_{3},v_{6}) = min (8 ,5) = 5

vi. Among v5, v6, v7, v7â€Ÿs dv value is lesser,
so v7 is selected. Its adjacent vertices are v4,

v4, and
v6. No change in v4.

T[v5].dist
= min(T[v5].dist, Cv7,v5) = min (7,6) = 6 T[v6].dist = min(T[v6].dist, Cv7,v6)
= min (5,1) = 1

vii.
Among v5 and v6, v6 is declared as known vertex. v6â€Ÿs adjacent vertices are v3,
v4, and v7, no change in dv value, all are known vertices.

viii.
Finally v5 is declared as known vertex. Its adjacent vertices are v2, v4, and
v7, no change in dv value, all are known vertices.

**Algorithm Analysis**

The
runnig time is O(|V|^{2}) in case of adjacency list and O(|E| log |V|)
in case of binary

heap.

**Prims Algorithm**

i.
Consider any vertex in the graph.

ii.
Process the vertex and add the vertex to the tree.

iii.
Find the smallest edge from the graph connecting
the edge of the vertex in the tree, such that it does not form a cycle.

iv. Add the
vertex to the tree.

v. Repeat
step 3 until the tree contains all the vertices in the graph.

**Routine for prims Algorithm**

void
prims(Table T)

{

vertex v,
w;

for( i=1;
i<=Numvertex; i++)

{

T[i].
known = False;

T[i] .
Dist = Infinity;

T[i].
path = 0;

}

for(;;)

{

//let v
be the start vertex with the smallest distance T[v] . Dist = 0;

T[v].
known = true;

for each
w adjacent to v if(!T[w] . known)

{

T[w] .
Dist = Min(T[w]. Dist, C_{v,w});

T[w].
path = v;

}

}

}

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Graphs : Primâ€™s Algorithm |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.