ANALYSIS DESIGN OF ALGORITHM (ADA) | MINIMUM SPANNING TREE (MST) USING GREEDY APPROACH

 📌Highlights: Hi friends ! In this post I am going to explain about Minimum Spanning tree using greedy approach such Prim's and Kruskal's algorithm in Analysis Design of Algorithm.

Let we first understand , what is spanning tree ?

A sub graph suppose S of graph G having V vertices and E edges is said to be spanning tree if following properties must be satisfied.

1. S must contain all vertices of G.

2. S must contain (|V|-1) edges.

3. There is no close loop inside S.

Note:

🔰 For finding number of edges in any spanning tree.

     👉 (n-1) edges 

🔰 Find the number of weight of spanning tree = Sum of weight of edge of spanning tree.

🔰 For finding maximum path length between two vertices,

     👉(n-1)

🔰 There is only one path from one vertex to another.

🔰 If we remove the edge then the graph  become disconnect.

🔰 The spanning tree is unique with distinct weight of graph.

Now we can say that , Spanning tree is a sub graph having all vertices having (n-1) edges.

For example:

Above graph G ( V , E ) where V is set of vertices and E is set of edges.

V= {1, 2, 3, 4, 5}

E= {(1,2), (2,3), (3,4), (4,5), (5,1)}

One of the spanning tree from above graph is:

It does not contain any cycle.

In mathematical we can say that:

S is a subset of G

    S= (V' , E')

    V' = V 

    |E'| = |V| - 1

Now for a given graph how many spanning tree can be possible. Suppose if we have 5 edges so |E|=5.

For calculating number of spanning tree in a graph is:

For spanning tree we will take only 4 edges. So number of spanning trees are

    = 5-0 

    = 5

Now if we have some weighted graph.(That mean some weight is given in any graph than the graph is known as weighted graph.) such as:

The above graph contain weight so it is a weighted graph. Now how we want to  know that how  many trees are possible.

We will see some possible spanning trees:

Possibility-I

Here 4 vertex are there so we will take only 3 edges (i.e (4-1))

Now the cost of above spanning tree is (3+6+4) = 13

Possibility-II

Here 4 vertex are there so we will take only 3 edges (i.e (4-1))

Now the cost of above spanning tree is (5+6+4) = 15

Possibility-III

Here 4 vertex are there so we will take only 3 edges (i.e (4-1))

Now the cost of above spanning tree is (3+2+4) = 9

Possibility-IV

Here 4 vertex are there so we will take only 3 edges (i.e (4-1))

Now the cost of above spanning tree is (3+5+4) = 12

Possibility-V

Here 4 vertex are there so we will take only 3 edges (i.e (4-1))

Now the cost of above spanning tree is (3+5+6) = 14

Now from the above example we can say that if you have a weighted graph and if you have more than one spanning tree then the cost of spanning tree is varying, that mean we can get different cost of spanning tree.

Now the question is that can we find out the minimum cost spanning tree ? Can we find out minimum one ? the answer is 'yes '  we can find all possible spanning tree and choose minimum of them. This is one of the method.

But finding all possible spanning tree is not so easy task for a big graph it time consuming. and really a tough task.

By applying greedy approach we can find the minimum cost spanning tree. For doing this we have two method available.

    1. Prim's algorithm

    2. Kruskal's algorithm

1.  Prim's Algorithm:

Prim's says always select those edges which have no cycle or which does not form any cycle. But the edges must be connected.Disconnected edges are not allowed.

Let we understand the working of prim's by taking an example:

From the above graph first we find the minimum cost edge such as:

Now we find next minimum cost edges but they must be connected to edge(A,G) or vertex A and vertex G. such as

Now see the cost of (G,F) = 18 , cost of (A,B) = 20 . here on comparing both cost of (G,F) is minimum so we select edge(G,F).

Now we find next minimum cost from vertex F and vertex A. Cost of Edge(F,E) = 16 Edge(A,B)=20 and Edge(F,D)=24. So find which one is minimum i.e 16 means F to E so we select it.

Now we find next minimum cost from vertex F , vertex A , vertex E and compare which one is minimum.

here we get 

So from above we observe that the cost of E to B is minimum i.e 14 so we will select edge (A,B) and we get

Now we find next minimum cost from vertex F ,vertex B , vertex E and  compare which one is minimum.

here we get 

So from above we observe that the cost of B to C is minimum i.e 12 so we will select edge (B,C) and we get

Now we find next minimum cost from vertex F, E and C and compare which one is minimum.

here we get 

So from above we observe that the cost of E to D is minimum i.e 15 so we will select edge (E,D) and we get

Now we find next minimum cost from vertex F, D, A ,C  compare which one is minimum.

But here if we make any edge by using any vertex than a cycle is formed which is not allowed. So that is a final.

Now the total cost =10+18+16+14+12+15

                           =85

In prim's we select only those nodes / vertices which are connected means we always try to make a tree.

Prim's thinks if those node far away from selected node will not make a tree. So it must be suggested that always select those edge which has minimum cost and should be connected.

 

2. Kruskal's Algorithm:

Kruskal's says always select those edges which have no cycle or which does not form any cycle  and the edges can be disconnected. Disconnected edges are allowed here.

Let we understand the working of prim's by taking an example:

Before finding minimum cost edge first of all we will plot all the vertices in the plane such as:

First minimum cost edge from the graph is C(A,G)=10. Now the we get:

Second minimum cost edge from the graph is C(B,C)=12. Now the we get:

Third minimum cost edge from the graph is C(B,E)=14. Now the we get:

Fourth minimum cost edge from the graph is C(E,D)=15. Now the we get:

Fifth minimum cost edge from the graph is C(E,F)=16. Now the we get:

Sixth minimum cost edge from the graph is C(G,F)=18. But here cycle is created so we will not consider. Now choose next option. that is C(A,B)=20 , Now we get:

Now the seventh minimum costs are C(G,F)=18,C(F,D)=24,C(C,D)=25 But they all create a cycle. So we will not consider in a tree.

Now the total minimum cost  = 10+18+16+14+12+15

                                           = 85

Conclusion:

Now we see how time complexity of prim's is calculated:

|E|=|V|-1

Total time   =theta(|V| |E|)

                 =theta (n.e)

                 =theta(n.n)

                 =theta(n power 2)

But kruskal's can be improved , when we have always collect a minimum cost edge then this is one data structure which we call as min heap and min heap always gives min value.

so here the time complexity is theta (nlogn)

Note: Spanning tree is a minimization result so definitely there will be only one result or there may be only one optimal solution that means the minimum cost of any spanning tree will be one may be there edges may be change.

So Friends this is all about Minimum spanning Tree using Greedy Approach. Here I explain the methodology of both prim's and kruskal's algorithm with the help of example I hope it is some thing helpful for you. We will meet in next new post till continue reading.....