8
Oct

Prim’s Algorithm In C# (Theory + Code Implementation)


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. In this video we will see how to implement
prim’s algorithm in C#. In this class Vertex we have taken these three
additional members status which can be permanent or temporary, predecessor and length. In this class UndirectedWeightedGrapph we
have taken these 4 constants. These 2 constants are used for specifying
the status of vertices. This constant NIL is used to initialized the
predecessor and this constant INFINITY is used to initialize the length of all vertices. Now in this method Prims we will apply prim’s
algorithm to find the minimum spanning tree. This method will display the edges that will
be included in the minimum spanning tree and it will also display the weight of that tree. Now this variable will store the
number of edges included in the minimum spanning tree and this variable will store the weight
of the minimum spanning tree. Now at the start of the algorithm all
vertices are temporary, length of each vertex is INFINITY and predecessor of each vertex
is NIL. We choose vertex 0 as the root vertex, any
other vertex can also be selected as a root vertex. Now first we make the length of root vertex
equal to 0. Now in this loop first we find the temporary
vertex with minimum length using this method. Now let’s see this method. This method will return the temporary vertex
with minimum length and it will return NIL if there is no temporary vertex left or all
the temporary vertices that are left have length INFINITY. Now if NIL is returned by this method and
n-1 edges have been included in the tree it means that there is no temporary vertex left
and we have got a minimum spanning tree. So we will display the weight of the minimum
spanning tree and return. Now if
NIL is returned by this method and the number of edges included in the tree is less than
n-1 it means that there are some temporary vertices left with length INFINITY. These are those vertices that are not reachable
from the root vertex. So this means that graph is not connected
and there is no spanning tree possible. Now if NIL is not returned by this method
then we come here and we make this vertex c permanent. Now vertex c is a current vertex. Now when we make vertex c permanent we will
include the edge that is in between predecessor of c and vertex c. So here we increment the value of this variable,
we display the edge that is included in the tree and we add the weight of the edge to
the weight of the spanning tree. This edge will be inserted only if current
vertex is not root vertex. Because for root vertex predecessor is NIL. Now c is a current vertex so in this loop
we are checking all vertices that are adjacent to c and are temporary and we will relabel
those vertices that satisfy this condition. Now this while loop is in infinite loop so
this process continues till this method returns NIL. Now this is the method main where we have
created the graph that we have seen in our example where we have called the method Prims. Now let’s run this program. These are the edges that are included in the
minimum spanning tree and this is the weight of the minimum spanning tree.

Tags: , , , , , , , , , , , , , ,

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *