Title: “6.10 Topological Sorting (with Examples) | How to find all Topological Orderings of a Graph”
Transcript
hi guys welcome back in this video I’m going to discuss with you what is topological sorting or you can also say topological ordering fine what is the topological ordering and how to find out topological altering of a given graph fine so first of all we’ll just discuss some key points of topological sorting what is topological sorting a topological ordering okay first point is to find out topological ordering that graph should be directed and acyclic that is the must condition graph should be dug that means directed and acyclic graph if graph is undirected you cannot find out topological sorting if graph is directed but it contains any cycle like this suppose we have 1 2 & 3 3 vertices this 1 2 2 3 & 3 to 1 1 to 2 2 to 3 and 3 to 1 the cycle is wrong now so such type of cycle contains if in graph then it is not possible to find out topological ordering of that graph so that graph should not contain any cycle not a single one fine that is must condition now what is topological sorting see topological sorting is basically a linear ordering linear ordering of the vertices in the graph such that for every directed edge UV so I see the edges from you to suppose u to V vertex u to V then in the or brain you must come before V fine I have written the definition here for vertex u 2 V u comes before vertex V in that ordering we will discuss it with the example then you will get it right and see one more point is for everyDirected_Acyclic_Graph if graph is directed in Si Si clique then at least one topological sorting would be there at least one but it is not compulsory that that graph will have only one topological sorting as Telegraph can have more than one topological sorting two three four five six fine any number of topological sorting now we’ll discuss the method how to find out topological sorting okay discuss it with the help of one example now suppose this one is our graph see this is directed graph sorry this was directed acyclic graph or not first of all check it out this is directed yes every edge is having some direction is there any cycle directed cycle this this no this is not coming like that this no there is no cycle fine so topological sorting or topological ordering on this graph is possible now how to find out topological sorting the first step is very first step find out the in degree of each vertex in the directed graph we have the concept of in-degree and out-degree fine in degree means the number of edges coming to that word X and how degree means the number of edges outgoing from that vertex now find out in degree of every vertex indicative of this one is is there any edge which is coming to one no there are two edges which are outgoing from this one no I just coming so in degree of this one is zero in degree of this 2 is there is only one edge that is coming one in degree of this four is one and two edges are coming to four to this edges like this right in degree of this five is one in degree of three is two edges are coming to three one two now we have finally found out the in degree of every vertex by first step is this second step is you will start by writing down the topological ordering or you can say the linear or drain from the vertex having in degree 0 find you and choose that vertex first that is having in degree 0 now find out which vertex is having in degree 0 1 so we will one okay now second step is we have selected this one fine so from this graph we will delete this one and all the edges which are outgoing from this one every edge so from this one how many edges are outgoing one into fine so we will delete this one and we will delete this this one also this one and this one now when we delete these edges then obviously the in degree of these vertices would be changed yes or no so the graph would be something like that we have only two we have four we have three we have fine fine two to four still we have four to three we have four to five we have this edge no we are not having one this edge we are not having this edge we have only two to three now in degree of this two will become what now you have to update the in degree of these vertices in degree of this two is now zero because first it was one this edge was deleted then it would be minus 1 1 minus 1 that is 0 it would be 2 - 1 - 1 edges had has been deleted now in degree of this 4s only this edge 1 5 is as it is 3 is in degrees - now we have this graph now again select the vertex having in degree 0 which one is having in degree 0 2 will write down to here next the same step we will delete this too.we will delete and will delete the every vertex out going from this to this also and this also fine and update the degree of these vertices you are supposed to update that what degree of those in degree of those vertices which are being affected because of because of deletion of this - and these edges now the graph would be is 2 has been deleted now we have only three we have four we have five yes four to five we have four to five million four to three we have do we have this edge no two has been deleted do we have this no this has also been deleted we have only two edges now now in degree of three would become first of all it was 2 minus 1 that is 1 only for e 1 3 1 minus 1 is because this one has been deleted so in degree C you can see this there is no issue in coming to that vertex that is 0 and here we have only one now again select the vertex having in degree 0 we have 4 write down this for the same step 4 would be deleted and also the outgoing edges would be deleted now the graph would be we have only vertex 3 and 5 now these two edges has been deleted is there any edge between these 3 and 5 no in degree of this 3 is now 0 in degree of this 5 is now zero now select again a vertex having in degree 0 now see here we have 2 what this is having in degree 0 3 & 5 so you can take this 3 also and you can take 5 suppose we are taking this three now three has been deleted now you can take this 5 or the second ordering is possible that is 1 2 4 yata cassity’s and after that first of all we will take this 5 and then we’ll take this 3 so 2 topological ordering of topological ordering is possible off for this graph alright we’ll take one more example suppose we have this kind of graph 1 2 3 and 5c now find out the topological ordering of this graph see the topological ordering of this graphs you’ll not be able to find out why so because this graph is having one directed cycle see this then this then this this is a cycle and we have already discussed in these properties that if a graph is having any cycle then you would not be able to find topological ordering for that graph so let us see is it possible is it true or not same step find out in degree of every vertex in degree of 1 is 1 in degree of this 2 is 2 1 & 2 2 edges are coming to that vertex 3 is 1 & 2 2 edges are coming for 5 in degree 0 for 4 in degree 0 select the vertex having in degree 0 you can select either 4 or 5 it’s up to you suppose we are selecting for case 1 is this 4 or case to me you can select fine that’s why I have told you for a graph directed acyclic graph many topological ordering are possible we are taking this case suppose we have choosen this for now after choosing this for delete this 4 and also this vertex now the graph would be 1 2 3 this one this one and this one now this one has been deleted but we have this 5 now in degree of this 5 is same in degree of 3 is still two in degree of 1 is still 1 but in degree of 2 is now 1 la too—they this has been deleted then 2 minus 1 that is 1 C 1 edge now again select a vertex I mean degree 0 we have 5 suppose we have taken this 5 now delete this 5 and this edge now the graph would be 1 2 & 3 this one this one and this one now 5 has been deleted now put 8 the in degree of every vertex 1 1 and still 2-1 deleted my one now is there any vertex having in degree zero no every vertex is having degree one one one so we cannot proceed further that is why I am saying if a graph contains a cycle then it would not be possible to find out topological ordering because if graph contains a cycle then at some point you will do it you will reach tonight some situations then at that time you will not have any vertex you will not find any vertex having in degree zero okay so that is the case you can take one more example suppose we are having this kind of graph now we are supposed to find out topological sorting of this graph find out first step in degree of every vertex in degree of is zero no I just coming in degree of D is one two three in degree of C is zero in degree of D is one to select a vertex having in degree zero you can select either C or you can select hey so case one is we have selected a and suppose case two we have selected C now case one we have selected a now after selection of a these would be deleted okay and the graph would be something like that we have B we have C we have D this one this one and this one and these edges has been related and update the in degree of every vertex sorry or you can see the update in degree of vertex which are being affected because of this deletion in degree of B now become 2 and B become 1 and C in degrees 0 now select a vertex having in degree 0 we have only C has been selected delayed this delayed this fine after deletion of Bees edges in degree of D would become 0 and in degree of B would become 1 then we would select in degree zero vertex having in degree 0 that is d after the selection of did this edge is also be deleted then we’ll select right or the next case was suppose you have selected this C then delete this and this and the graph would be a b and b we are having this edge we are having this edge we are having this one update in degree this is having zero same this will be having to 3 minus 1 this will be having 1 now we will select a because in vertex a is having in degree 0 now delete this this one and this one you have selected this a nor delete the outgoing edges of the say also and this vertex also now in degree of this would be updated to 0 after this deletion by an integral of this B would be updated to 1 now you can select after that you can select B and you can select now D so these are 2 topological ordering possible of this graph right so for every directed acyclic graph more than one topological ordering is possible okay I’ll say in the next video till then bye bye take care”