13
Sep

# 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.