# Prim’s algorithm

We have seen that a spanning tree of a connected

graph G is a subgraph T that includes all vertices of G and some or all edges of G such

that all vertices are connected and there are no cycles. Example for this Graph G, these all are spanning

trees. These are the weights of these spanning trees. These weights are the sum of weights of edges

included in the tree. Example for this tree weight is equal to six

plus 3 plus 4 equal to 13. Now a minimum spanning tree of graph G is

a spanning tree whose weight is minimum among all the spanning trees of G. For example for this graph, this is the minimum

spanning tree as its weight is minimum. If the graph contains some edges with equal

weights then more than one minimum spanning tree is possible. While if all the edges of the graph have unique

weights then there will be only one minimum spanning tree for the graph. Finding minimum spanning tree can be useful

as it gives us the most economical way of connecting all the vertices of a graph. In this course we will learn about these two

algorithms for finding minimum spanning tree of a graph. Both of these algorithms use the greedy approach. In this video we will learn about prim’s

algorithm which is used for creating a minimum spanning tree. The procedure of prim’s algorithm is somewhat

like that of Dijkstra’s algorithm. We will give each vertex a status. If a vertex is temporary it means that it

is not been included in the spanning tree and if a vertex is permanent it means that

it has been included in the spanning tree. Initially all vertices will be temporary and

at each step of the algorithm we will make the temporary vertex permanent. And the process stops when all the vertices

become permanent. That is when all the vertices are included

in the spanning tree. Each vertex is given two values length and

predecessor. Length of a vertex represents weight of the

shortest edge connecting the vertex to a permanent vertex and predecessor represents that permanent

vertex. Now when the algorithm starts the length of

all vertices is initialize to infinity which is a very large number and predecessor is

initialize to NIL which is taken as -1 since our vertices starts from zero. Now a temporary vertex can be relabelled that

is its length and predecessor value can be changed. But once a vertex is made permanent it can’t

be relabelled. For making the vertex permanent in each step

the greedy approach is used. The vertex which is minimum length is made

permanent. Now let’s see the whole stepwise procedure

of the algorithm. Initially for all the vertices length is equal

to infinity, predecessor is NIL and status is temporary. We will select any vertex of the graph as

root vertex and make its length equal to zero. Now from all the temporary vertices of the

graph we will select the temporary vertex that is minimum length and will make it permanent

and now it becomes the current vertex. At the start of the algorithm root vertex

is minimum length. So root vertex will be the first one to become

permanent. Now in second step we will examine all the

temporary vertices adjacent to the current vertex and relabel them if required. Now let’s see what’s the condition in which

we need to relabel any vertex adjacent to current vertex. Suppose v is a temporary vertex adjacent to

the current vertex that we are examining. If weight of this edge is less than length

of v then length of v becomes equal to weight of this edge and current becomes predecessor

of v. Otherwise no relabeling is required. Now these steps 1 and 2 are repeated till

either there are no temporary vertices left or all the temporary vertices that are left

have length equal to infinity. If the graph is connected then all vertices

of the graph will become permanent at the end of the algorithm. If the graph is not connected then vertices

which are not reachable from the root vertex will remain temporary with path length infinity. In this case there is no spanning tree

possible for the graph. From the next video will will understand the

whole procedure with the help of an example. In this video we will understand the procedure

of Prim’s algorithm with the help of this graph. Initially all vertices are temporary, length

of all vertices is infinity and predecessor is nil. We will take vertex 0 is the root vertex. Now the first step is to make length of root

vertex 0. So we will make length of this vertex 0 equal

to 0. Now from all the temporary vertices we have

to select temporary vertex with minimum length. This is the vertex with minimum length, so

we will make it permanent and now this is a current vertex. So we will examine all temporary vertices

adjacent to this vertex 0. First we take this vertex 1, this 19 is less

than infinity so we will relabel it. Next we take

this vertex 3, this 14 is less than infinity so we will relabel it. Next we take this vertex 4, this 12 is less

than infinity so we will relabel this also. Now from all the temporary vertices this vertex

4 has the minimum value of length so we will make it permanent. Now predecessor of 4 is 0, so this edge 0-4

is included in the minimum spanning tree. Now 4 is a current vertex so we will examine

all temporary vertices adjacent to this vertex 4. First we take this vertex 1, this 18 is less

than 19 so we will relabel it. Next we take this vertex 2, this 17 is less

than infinity so we will relabel it. Next we take this vertex 3, this 13 is less

than 14 so we will relabel this vertex 3. Next we take this vertex 5, this 16 is less

than infinity so we will relabel this vertex 5. Next we take this vertex 6, this 21 is less

than infinity so we will relabel this vertex 6. Next we take this vertex 7, this 22 is less

than infinity so we will relabel this vertex 7. Next we

take this vertex 8, this 24 is less than infinity so we will relabel this vertex 8 also. Now from all the temporary vertices this vertex

3 has the minimum value of length so we will make it permanent. Now predecessor of 3 is vertex 4 so this edge

4-3 is included in the minimum spanning tree. Now vertex 3 is a current vertex so now we

will examine this vertex 6 which is adjacent to 3 and is temporary. The 28 is greater that 21 so we will not relabel

this vertex 6. Now from all the temporary vertices this vertex

5 has a minimum value of length so we will make it permanent. Now predecessor of 5 is 4 so this edge 4-5

is included in the minimum spanning tree. Now this vertex 5 is a current vertex so we

will examine these vertices 2, 8 and 9 which are adjacent to vertex 5 and are temporary. First we take

this vertex 2, this 15 is less than 17 so we will relabel this vertex 2. Next we take this vertex 8, this 26 is greater

than 24 so we will not relabel this vertex 8. Next we take this vertex 9, this 27 is less

than infinity so we will relabel this vertex 9. Now from all the temporary vertices, this

vertex 2 has a minimum value of length so we will make vertex 2 permanent and now this

vertex 2 is a current vertex. So we will examine these vertices 1 and 9

which are adjacent to vertex 2 and are temporary. First we take this vertex 1, this 20 is greater

than 18 so we will not relabel this vertex 1. Next we take this vertex 9, this 29 is greater

than 27 so we will not relabel this vertex 9. Now from all the temporary vertices left we

have this vertex 1 which is minimum value of length so we will make this vertex 1 permanent. Now this vertex 1 is a current vertex, now

there is no temporary vertex that is adjacent to this vertex 1. So now from all the temporary vertices left

we have this vertex 6 which has minimum value of length so we will make vertex 6 permanent. Now 6 is a current vertex and this vertex

7 is adjacent to 6 and is temporary so we will examine this vertex 7. This 23 is greater than 22 so we will not

relabel this vertex 7. Now from these three temporary vertices left,

this vertex 7 has the minimum value of length so we will make it permanent and now this

vertex 7 is a current vertex and we will examine this vertex 8 which is adjacent

to this vertex 7 and is temporary. This 30 is greater than 24 so we will not

relabel this vertex 8. Now we have these two temporary vertices left

and this vertex 8 has a minimum value of length so we will make this vertex 8 permanent. Now this 8 is a current vertex and we will

examine this vertex 9 which is adjacent to vertex 8 and is temporary. Now this 35 is greater than 27 so we will

not relabel this vertex 9. Now this is the only vertex that is temporary

so we will make it permanent. Now all the vertices are permanent and we

have got a minimum spanning tree.