3.5 Prims and Kruskals Algorithms - Greedy Method

the topic is minimum cost spanning tree so for that first of all we'll understand what does it mean by a spanning tree here I have an example graphs graph is represented as G and V E V is the set of vertices 1 2 3 4 5 6 and E is the set of edges the set of edges are from 1 to 2 and 2 to 3 3 to 4 and so on graphs are represented as set of vertices and edges now what is the spanning tree spanning tree is a sub graph of a graph since I should take the subset of this so subset of what what is says an edges both the subsets or only one subset so I should take the subset of edges vertices must be as it is so I should take all were distance six spanning tree means I should take all what Isis then how many edges how many words I have number of vertices are n 36 so I should take number of what is this minus one that is only five edges span three is a sub graph of a graph having all vertices but only n minus one edges so all of these edges I should take only 5 so 1 2 3 4 5 I did not take this one so the spanning tree see a tree will not have a cycle so there is no cycle here yes there is no cycle here if I this you can say it's a cycle if you start from one vertex you can again reach back to that vertex but here there is no cycle sure is it possible that I will take this one but I will not take this yes there's also a spanning tree I will this but I will not take this yes this is also a chance planning page so which adjective salad that is a choice that's a choice for a spanning tree so I can say that s is a sub graph of a graph where s is a define as set of vertices and a set of edges where set of vertices are same as the vertices of a graph and edges are number of vertices minus 1 so the number of edges are number of vertices minus 1 this how formally we can divide in mathematics we can define like this knowledge thing for a given graph how many different spanning trees can be generated I want to know that how many different spanning trees are possible so see number of edges are hominid 6 1 2 3 4 5 6 I have an aspiring tree I should only 5 I should take only five so 6c 5 out of 6 edges out of 6 edges I have to select 5 how many ways I can do that so 6 5 the Seavey's so if it's 6 5 see is how much 6 only so I can have six different spanning trees just now you can see it is a simple one that I have skipped this edge like this I can leave one one edge right and you can form a spanning tree right I can take all except this take all except this take all these six are possible suppose if I have one more edge now now I have seven edges and I want to select five now how many spanning trees are possible see a I'd have this esperen tree also or I can have this is a spanning tree also the possibilities are more of the 7c v 7c 5 but this edge it will form cycle so how many cycles it is forming this is one cycle and this is another cycle so this edge is forming two cycles often number of word he says less than six so if it is forming number of vertices less than six then you suffer B 7 C 5-2 so that's it so what's the formula to know how many different spanning trees are possible from a given graph so whatever the number of edges you have you should take all those and see of how many are just you need you need five so five years what number of vertices minus one so this is not a vertices minus 1 and minus number of cycles you have to subtract number of cycles I have a graph where the edges are having weights so this is a weighted graph there's a weighted graph I want to know what are the possible spanning tree is possible so I'll draw a few spanning trees let us draw one spanning tree this is vertex 1 & 2 & 3 & 4 so 4 what is this are there then how many edges I should take 4 minus 1 only 3 so I'll select this one 1 2 3 so what is the weight of this one 5 3 & 6 so what is the cost of the spanning tree cost of this spanning tree is 14 I take one more spanning tree 1 2 3 4 and I'll take these edges let us see what is the cost of this 4 6 3 then what is the cost of this one 13 I take one more spanning tree 1 2 3 4 and I take these edges this one and this one and this one 4 2 & 3 so this is cost us how much 9 now from this example some observation we can understand something if you have a weighted graph and you get different spanning trees the cause of the spanning trees may be varying you can get a different cost of spanning trees now the problem is can I find out the minimum cost spanning tree can I find out the minimum one which gives me a minimum yes you can find out how you can try all possible spanning trees and then from that you can check whichever is minimum you can pick up that answer and this is one method trying all possible spanning trees will be too lengthy is there any greedy met hurt yes the greedy methods are available for finding the minimum cost spanning tree if a weighted graph is given you can find out the minimum cost spanning tree by following the method without finding out all possible spanning trees so what are those methods one method is Prince algorithm and the second method is kruskal's algorithm there are two algorithms for finding minimum cost spanning tree I have a weighted graph here and I have to find a minimum cost spanning tree by following Ben's algorithm let us see how prims algorithm works through an example the asper prims algorithm he says that from a graph first of all you select a minimum cause edge so the smallest edge in the entire graph is this one then this is the initial one now for the rest of the procedure always select a minimum cause edge from the graph but make sure that it should be connected to all the riesling vertices now the next minimum is switch 1 3 2 4 don't take that it will not be connected to 1 or 6 so take only those which are connected to 1 or 6 means what he is trying to do is always maintain a tree thinks that if some father away edge is selected then it may not be forming a tree finally so that is the reason he suggested that always select a minimum edge we should be connected so let us see what is the next one so for this connected one are this one and this one so this twenty five and twenty twenty five is minimum so select this twenty five then this twenty eight and five connected to five or twenty two and twenty four sort of this 28 24 and 22 so from one and six and five am checking so already six is over so one and five so out of those this is smallest one so four is selected now from one six and five four who is smallest the connected one so this is 24 and 18 and 12 so to L is smaller so we will take two n then not of all these which collected as a smallest so here I have 24 18 and 16 so 16 is a smaller so take that 16 then an out of all these who is next connected so from 2 to 7 there is an edge which is connected so this is 7 that's it there are 7 vertices so 1 2 3 4 5 6 6 edges are selected and this how we got a minimum cost cost spanning tree and and this is how we got a minimum cost spanning tree what is the cost of a tree the cost of a tree is if I add all these if I add all these it is 99 so the approach of premises initially select the smallest one then always select the connected smallest one of it so this is the method of prims algorithm next if I have a graph 1 2 3 4 5 6 seven if I have a graph like this which is not a connect data there are total seven vertices but there are two pieces in a graph can prim find out the minimum cost spanning tree for this one no no algorithm can find out because we cannot find a tree for this one spanning tree for this one in a spanning tree it must be connected so for non connected graph we cannot find spanning page at all but if I start prints on this one starting from vertex one if it is starting then it may find the spanning tree for only one component not the other component next method for finding minimum cost spanning tree is kruskal's meth hurt this also follows a greedy approach instead of trying out all possible spanning trees it shows a procedure by following which we can get a minimum cost spanning tree it says that always select a minimum cause edge always select a minimum cause edge let us follow this one select smallest edge one to six that is ten this one is the smallest and the next is smallest rest is three to four so the second edge and selecting is three to four and its cost is 2n next minimum is two to seven select two to seven and this is 14 the next minimum is two to three that is 16 and after this the next minimum edge is seven before but that is 18 if I select that it will form a cycle yes crystal method say is that always select a minimum cause edge but if it is forming a cycle don't tuns include it in the solution discard that edge don't include attach so it means always select such that it is not forming a cycle so if I include 4 to 7 it will form a cycle so next one you check so the next one is 22 so this is from 5 to 4 or 4 to 5 so this is 22 next minimum is 34 so that is 7 and 5 if I include this also it will form a cycle don't include that one then the next minimum one is 25 that is from 5 to 6 so this is 25 and the cost of this one is if you add all these waves it's 99 so he also got the same result just how I got in prims algorithm so the Prince algorithm and critical algorithm has given the same result on this particular graph now find hidden by kruskal's algorithm how much time it takes see it has to always select a minimum cost H from the set of edges so let us say there are a number of edges so out of these edges it will find out the minimum one and how many such edges it will be selecting it will be selecting V minus 1 yet this number of vertices minus 1 like we know in a spanning tree if there are 7 vertices we need 6 adjusts for forming a spanning tree so that is 7 minus 1 so as many vertices we have minus 1 number of edges we have to selects so the total time will be theta of V into e the e V is number of vertices and E is number of edges so it is n into e n is the number of vertices and E is the number of edges we should also be written as n square if we say both are n then it is n square so the time taken by kruskal's algorithm is n square but crystal algorithm can be improved when we have to always select a minimum cause edge then there is one data structure which will always give you a minimum value that is min heap if min heap is used then min heap will always give you a minimum value whenever you delete a value you get a minimum value so if all these edges are kept in a min heap whenever you delete getting an X minimum at so you don't have to search so from many games whenever you delete the time taken is login so how much time it will take for finding a minimum cause edge login time so how many times you have to do that that is n time number of vertices minus one time so n so by using min-heap the time come time capacity of kruskal's algorithm will be n log n so that's how critical algorithm can be made faster now if there is a draft given that is not connected graph it is having two components for vertices on this side five vertices on that side can we find a spanning tree on a non connected graph no spanning tree is not possible but what happens if I run a school skills algorithm so critical algorithm will try to find out total number of edges that is nine minus one so it will try to select eight edges and it will not be forming a spanning tree for entire graph but it may be finding the spanning tree for each component let us say is the first minimum da one it will select us this one then the next minimum it is having more than one edges let us say it selects next minimum and the next minimum it will select this next minimum it selects this and this is the next minimum so in this way it is selecting the minimum right just from both the components or it will be selecting from all the components so it may be finding spanning trees for all the components but not for the entire terms so critical algorithm may work for non connected graphs also but it may give spanning tree for those components let us take a problem here our graph is given and the weights of the edges are also given but here two edges are not having their weights if I take only these edges which are having a weight they are forming a spanning tree of a graph just hide these two edges it becomes a spanning tree now the question is what could be the minimum values of these two axes what could be the minimum possible value it can be anything but at least what could be the value see as this is included in the spanning tree this is included in a spanning tree this is not included because it is forming a cycle so it is forming a cycle if it is included this will form a cycle so it will be considered after selecting these true after selecting these two so the weight of this could be four right first this is selected then this is selected then this is not selected once definitely it is four if it is less than four then that would have been selected first right so it came later so it is forming a cycle so it is not taken that this four is taken then this force is taken this 5 is taken so then what could be the minimum weight of this one so it is not selected at last it is left over means minimum weight of this one could be 6 so this is 4 and that is 6 so if any missing edges are there you can find out this type of problems we find in examinations so some missing edges you can find out so if you know spanning tree you can answer this type of question let us take this example and let us find out spanning tree for this one minimum cost spanning tree so if I follow crystals method so first I will select the minimum cause edge this edge I have selected then the next minimum is this 3 and that tree so I can select any one so I will select this one first just selected next I will select this one so is it forming a cycle inclusion of this one no so I will select that one then which other just 4 and 4 these two are there so I can select any one so I will select this one but if this will form any cycle no so total how many edges I have selected 1 2 3 4 and total how many vertices are there 5 vertices are there so 4 edges are selected that's all I got a spanning tree so what is the cost of the spanning tree 2 plus 3 plus 3 plus 4 and this is two ends spanning tree is a minimization result so definitely there will be only one result so for a problem there can be only one de Mille solutions so we should have exactly one spanning-tree only there cannot be more than one spanning tree right but in this example you can see instead of taking this fool this edge I can take this fool also now also it's forming a spanning tree yes so I can select one more but what is the cost cost is 12 so cost is only one the optimal cost is 2l only you will get definitely only one answered in the minimization or maximization problem but for that answer the set of input may be changing so either you can include this for or this for so total how many spanning trees are trees are possible to spanning these are possible but what is the minimum cause that is true it

Channel: Abdul Bari

Views: 1,447,335

Keywords: algorithm, algorithms, greedy method, spanning tree, minimum cost spanning tree, prims, prims algorithm, kruskal, kruskals algorithm

Id: 4ZlRH0eK-qQ

Length: 20min 12sec (1212 seconds)

Published: Thu Feb 08 2018