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

where function IsAdjcent()

Want to learn Python from a wonderful python course

Enroll here – https://www.udemy.com/course/python-programming-in-depth/?couponCode=YOUTUBE10