Topological Sorting Overview

Hey everyone, welcome back to the channel. I hope you guys are doing extremely well. So, in this video we are going to learn about topological sorting and we are going to solve this using the DFS algorithm which is the depth first search. Now what is topological sorting? In order to define it, I can say it only exists on DAG which is directed acyclic graph that means any directed graph which does not have a cycle. Why? I will tell you that. So basically the definition states any linear ordering of vertices means these nodes, any of the linear ordering such that if there is an edge between u and v, such that there is an edge between u and v, u always appears v in that ordering. U always appears before v in that ordering. So this is the particular DAG. So let me write down the edges that we have. I think we have an edge from 5 to 0. we have an edge from four to zero we have an edge from five to two we have an edge from two to three we have an edge from three to one and we have an edge from four to one so one two three four five six we have all the six edges so this can be a possible linear ordering why let me tell you that five to zero five appears before zero four to zero four appears before zero five to two 5 appears before 2. 2 to 3. 2 appears. before three three two one three appears before one four to one four appears before one so thereby this is a valid linear ordering similarly this can also be a valid linear ordering so if you see five appears before zero five appears before zero four appears before zero yes five appears before two yes two appears before three yes three appears before one yes four appears before one yes So this is also a valid ordering. There can be multiple valid orderings, but we just need to figure out one of the topological sortings and that should be good enough. Now coming across, we will understand how to find it. But why only in directed a cyclic graph? Why? So let's understand why in directed graph. So what does the definition state? if there is an edge between u and v u appears before v so if you take undirected graph and you see that there is an edge between 1 to 2 it actually means there is an edge between 1 to 2 and there is an edge between 2 to 1 so how can you write the ordering such that 1 is before 2 and 2 is also before 1 that is not practically possible thereby the line thereby the directed graphs are only possible now why a cyclic means means no cycle. Why is that? Now imagine if you have a cycle in a directed graph 1 to 2, 2 to 3, 3 to 1. Okay so what I'm stating is 1 is having a edge to 2 which means 1 should be before 2 in that ordering. 2 to 3 is an edge which means 2 should be before 3 in that ordering. 3 to 1 has an edge which means 3 should be before 1 in that ordering. That is not possible why because there is a cyclic dependency happening because there is a cyclic dependency happening thereby if there is a cycle you cannot have an ordering such that everyone follows that so thereby a cyclic and graph yes so i hope you got the reason why is topological sorting valid or why can you just write a linear ordering for a directed a cyclic graph which is nothing but a dag okay so the reason is clear now let's quickly jump up to the algorithm so we have this particular dag and we have the corresponding adjacency list for this particular tag so what does this particular topological sort algorithm in dfs states now what we will always do is you know that right we always have this particular stuff for components and that is the same thing we will be following over here as well so over here how many nodes do we have we have five nodes so run till five and we will say if not visited yes very very important if not visited of i then we will call the dfs for i yes that is how we will do it and i'll explain you slowly so this is what we will take and we will always declare a visited array so let's quickly declare the visited array so probably we can do that over here so we have declared the visited array and make sure everything is marked as zero initially. Marked as zero initially. Now let's quickly start off. What is the value of i? The value of i is 0 initially. Is that visited? No. So what you do is you start the dfs call from zero remember this you start the dfs call from zero at the same time just declare a stack yes declare a stack now what is a stack it is a last in first out operation uh data structure last in first out operation data structure if you don't know please read about stack so dfs of zero is there so what you do is you say okay this guy is visited does zero have any adjacent nodes no so the DFS will not call any further DFS And it will go back. But remember, before going back, take this 0 and put it into the stack. Before going back, take the 0 and put it into the stack. Done. So the DFS for 0 is completed. Next. I'll tell you the intuition going forward. Don't worry. Next is 1. So again, you write the same thing. DFS of 1. The first thing you do is you mark it as visited. Does 1 have any adjacent nodes? No. So there will be no further DFS calls. No further DFS calls. So before going back. put this into the stack so you put this into the stack and now you will go back so the dfs is completed next it comes for two so what happens is you call the dfs for two you mark it as visited now two has an adjacent node so you go and call it for three now what you do is you mark for three as visited as well now does three have an adjacent node it checks that three has an adjacent node one But if we carefully see, we cannot call for DFS of 1. Why? because it is already visited yes because it is already visited so thereby what we will do is we will be like okay it has already visited so let's quickly just uh not call any further dfs calls and go back but if we're going back take that three and put it in now we go over here no for the dfs calls go back before going back put that into the stack so we have put that into the stack and we are now done right now the value will be three three is already visited next value will be before. and that is not visited so what we will do is we will go and check out for four now for four we will mark it as visited and we will check if there are adjacent nodes zero is visited one is visited so both of the adjacent nodes are visited so there will be no further dfs calls so you go back now what you do is you take this four and you put it into the stack you take this four and you put it into the stack right so next it will be five and now next the dfs call will be happening for five sale market has visited Does 5 have any adjacent nodes? Yes. 0, already visited. 2, already visited. So, thereby, no further DFS calls for 5 and you put 5 into the stack. Done. Now, I can say that the DFS call is over. Once the DFS call is over, whatever you stored in the stack, take it one by one. The first thing that you take out is 5. Next thing you take out is 4. Next thing, 2. Next thing, 3. Next thing, 1. Next thing, 0. This is one of the linear orderings, yes. This is one of the linear orderings that you can get. Very, very important. This is one of the linear orderings that you can get. And this is what is known as topological sort of this particular graph. I hope that does make sense. Now, you must be thinking about, hey, Striper, but what is the intuition behind this algorithm? The algorithm looks pretty simple, but what is the intuition? I'll tell you the intuition, but let's first write the code. absorb the code absorb the logic and then i'll tell you the intuition the intuition is very small don't worry about that so guys as usual i'll write the c++ code on the right and you can find the java code on the left so given the v and the adjacency matrix we will be declaring the visited guy so let's quickly declare the visited guy and mark everyone as zero done next we need a stack so please go and declare a stack what's the next thing that we do we iterate from zero till v next we say hey listen not visited of i then we call the dfs with this particular node and the visited and the stack perfect at the end of the day we know that we have to store the answer in a vector so vector of int answer and we need to uh just do uh keep on doing till the stack is not empty so answer dot push back stack dot top and you can do stack dot pop perfect and at the end end of the day you can return the answer now what you just need to write is the dfs function so you can go over here and say hey listen void dfs int node int visited and we also need the stack so stack by the way visited is an array we need the stack so stack of int stack and we need this particular adjacency matrix as well so adjacency matrix now what we will do is we will say visited node equal to one and over here we will say auto of id adjacency node and we will plain call the dfs nothing fancy call the dfs for this particular node with this visited stack and the adjacency so make sure you pass on the adjacency over here as well and right at the end of the day when the dfs is over you do not have any further dfs calls to me take on the stack and say hey can you please to the node so that's how you will do it and now let's quickly compile this and see if it is running fine it says there is some issue with it let's quickly check it out okay now if you read the question find any topological sorting you can find any topological sorting and it will work fine So it does run Now, if I discuss about the space complexity, we are using a visited and a stack. So we go off and plus we go off and what about the time complexity similar to DFS algorithm, which is V plus E for directed graphs. So the time complexity is V plus E for directed graphs at the worst case. Now, coming back to the intuition, what is the intuition of this particular stuff? Now, if I give you a simple enough directed graph like one, two. three four five and six okay so what will you do you know if i ask you to write the linear ordering you'll be like the linear ordering is very simple one two three four you can either write five or you can either write six vice versa you can do either of them like you can write one two you can either write one two three four five sorry one two three four five six or you can write one two three four six five both of the linear ordering are two true so how did you get this very simple you call the dfs from here then you went here then you went here then you went here if you went here i was uh five was coming first or if you went here six was coming first now when you come back what i did was i just stored the six in a stack and then from four when i went to five and when i came back from five i stored it here and i went from four i stored the four here then for three i stored it here then for two I stored it here then for one i stored it yeah so what i did was the people whose dfs was complete i just stored it i just stored it i just stored it i just stored it now what happens is i know the dfs of three is completed which means this entire portion has been visited which means this entire portion has been visited so everything would have been here and the linear ordering will be followed 3 is before 4, 4 is before 6, 6 is before 5. Just because I know if I have done the DFS for 3, then everything would have been done. Everything would have been done. Thereby, whenever I complete the DFS, then only I put it. Because I know everything would have been done. So if everything would have been done, everything would have been stacked below. If I get it back, I'll get the linear ordering. That's a simple intuition. Nothing special. Whenever the DFS is completed, everyone is touched. They just picketed. And the next guy would have called it. you will be now coming in so simple intuition so guys i hope i was able to explain you this particular algorithm so just in case i was please make sure you like this video and if you're new to our channel what are you waiting for hit that subscribe button right away and if you haven't checked out our dpcds and the hd sheet the links are in the description please make sure to check it out with this i'll be wrapping up this video let's meet in the next one until then bye bye take care

In order to define it, I can say it only exists on DAG which is directed acyclic graph that means any directed graph which does not have a cycle. Why? I will tell you that.

So basically the definition states any linear ordering of vertices means these nodes, any of the linear ordering such that if there is an edge between u and v, such that there is an edge between u and v, u always appears v in that ordering. U always appears before v in that ordering. So this is the particular DAG. So let me write down the edges that we have.

I think we have an edge from 5 to 0. we have an edge from four to zero we have an edge from five to two we have an edge from two to three we have an edge from three to one and we have an edge from four to one so one two three four five six we have all the six edges so this can be a possible linear ordering why let me tell you that five to zero five appears before zero four to zero four appears before zero five to two 5 appears before 2. 2 to 3. 2 appears. before three three two one three appears before one four to one four appears before one so thereby this is a valid linear ordering similarly this can also be a valid linear ordering so if you see five appears before zero five appears before zero four appears before zero yes five appears before two yes two appears before three yes three appears before one yes four appears before one yes So this is also a valid ordering. There can be multiple valid orderings, but we just need to figure out one of the topological sortings and that should be good enough.

Now coming across, we will understand how to find it. But why only in directed a cyclic graph? Why?

So let's understand why in directed graph. So what does the definition state? if there is an edge between u and v u appears before v so if you take undirected graph and you see that there is an edge between 1 to 2 it actually means there is an edge between 1 to 2 and there is an edge between 2 to 1 so how can you write the ordering such that 1 is before 2 and 2 is also before 1 that is not practically possible thereby the line thereby the directed graphs are only possible now why a cyclic means means no cycle. Why is that?

Now imagine if you have a cycle in a directed graph 1 to 2, 2 to 3, 3 to 1. Okay so what I'm stating is 1 is having a edge to 2 which means 1 should be before 2 in that ordering. 2 to 3 is an edge which means 2 should be before 3 in that ordering. 3 to 1 has an edge which means 3 should be before 1 in that ordering. That is not possible why because there is a cyclic dependency happening because there is a cyclic dependency happening thereby if there is a cycle you cannot have an ordering such that everyone follows that so thereby a cyclic and graph yes so i hope you got the reason why is topological sorting valid or why can you just write a linear ordering for a directed a cyclic graph which is nothing but a dag okay so the reason is clear now let's quickly jump up to the algorithm so we have this particular dag and we have the corresponding adjacency list for this particular tag so what does this particular topological sort algorithm in dfs states now what we will always do is you know that right we always have this particular stuff for components and that is the same thing we will be following over here as well so over here how many nodes do we have we have five nodes so run till five and we will say if not visited yes very very important if not visited of i then we will call the dfs for i yes that is how we will do it and i'll explain you slowly so this is what we will take and we will always declare a visited array so let's quickly declare the visited array so probably we can do that over here so we have declared the visited array and make sure everything is marked as zero initially.

Marked as zero initially. Now let's quickly start off. What is the value of i?

The value of i is 0 initially. Is that visited? No.

So what you do is you start the dfs call from zero remember this you start the dfs call from zero at the same time just declare a stack yes declare a stack now what is a stack it is a last in first out operation uh data structure last in first out operation data structure if you don't know please read about stack so dfs of zero is there so what you do is you say okay this guy is visited does zero have any adjacent nodes no so the DFS will not call any further DFS And it will go back. But remember, before going back, take this 0 and put it into the stack. Before going back, take the 0 and put it into the stack.

Done. So the DFS for 0 is completed. Next. I'll tell you the intuition going forward.

Don't worry. Next is 1. So again, you write the same thing. DFS of 1. The first thing you do is you mark it as visited.

Does 1 have any adjacent nodes? No. So there will be no further DFS calls. No further DFS calls. So before going back.

put this into the stack so you put this into the stack and now you will go back so the dfs is completed next it comes for two so what happens is you call the dfs for two you mark it as visited now two has an adjacent node so you go and call it for three now what you do is you mark for three as visited as well now does three have an adjacent node it checks that three has an adjacent node one But if we carefully see, we cannot call for DFS of 1. Why? because it is already visited yes because it is already visited so thereby what we will do is we will be like okay it has already visited so let's quickly just uh not call any further dfs calls and go back but if we're going back take that three and put it in now we go over here no for the dfs calls go back before going back put that into the stack so we have put that into the stack and we are now done right now the value will be three three is already visited next value will be before. and that is not visited so what we will do is we will go and check out for four now for four we will mark it as visited and we will check if there are adjacent nodes zero is visited one is visited so both of the adjacent nodes are visited so there will be no further dfs calls so you go back now what you do is you take this four and you put it into the stack you take this four and you put it into the stack right so next it will be five and now next the dfs call will be happening for five sale market has visited Does 5 have any adjacent nodes? Yes.

0, already visited. 2, already visited. So, thereby, no further DFS calls for 5 and you put 5 into the stack. Done. Now, I can say that the DFS call is over.

Once the DFS call is over, whatever you stored in the stack, take it one by one. The first thing that you take out is 5. Next thing you take out is 4. Next thing, 2. Next thing, 3. Next thing, 1. Next thing, 0. This is one of the linear orderings, yes. This is one of the linear orderings that you can get.

Very, very important. This is one of the linear orderings that you can get. And this is what is known as topological sort of this particular graph. I hope that does make sense.

Now, you must be thinking about, hey, Striper, but what is the intuition behind this algorithm? The algorithm looks pretty simple, but what is the intuition? I'll tell you the intuition, but let's first write the code. absorb the code absorb the logic and then i'll tell you the intuition the intuition is very small don't worry about that so guys as usual i'll write the c++ code on the right and you can find the java code on the left so given the v and the adjacency matrix we will be declaring the visited guy so let's quickly declare the visited guy and mark everyone as zero done next we need a stack so please go and declare a stack what's the next thing that we do we iterate from zero till v next we say hey listen not visited of i then we call the dfs with this particular node and the visited and the stack perfect at the end of the day we know that we have to store the answer in a vector so vector of int answer and we need to uh just do uh keep on doing till the stack is not empty so answer dot push back stack dot top and you can do stack dot pop perfect and at the end end of the day you can return the answer now what you just need to write is the dfs function so you can go over here and say hey listen void dfs int node int visited and we also need the stack so stack by the way visited is an array we need the stack so stack of int stack and we need this particular adjacency matrix as well so adjacency matrix now what we will do is we will say visited node equal to one and over here we will say auto of id adjacency node and we will plain call the dfs nothing fancy call the dfs for this particular node with this visited stack and the adjacency so make sure you pass on the adjacency over here as well and right at the end of the day when the dfs is over you do not have any further dfs calls to me take on the stack and say hey can you please to the node so that's how you will do it and now let's quickly compile this and see if it is running fine it says there is some issue with it let's quickly check it out okay now if you read the question find any topological sorting you can find any topological sorting and it will work fine So it does run Now, if I discuss about the space complexity, we are using a visited and a stack.

So we go off and plus we go off and what about the time complexity similar to DFS algorithm, which is V plus E for directed graphs. So the time complexity is V plus E for directed graphs at the worst case. Now, coming back to the intuition, what is the intuition of this particular stuff?

Now, if I give you a simple enough directed graph like one, two. three four five and six okay so what will you do you know if i ask you to write the linear ordering you'll be like the linear ordering is very simple one two three four you can either write five or you can either write six vice versa you can do either of them like you can write one two you can either write one two three four five sorry one two three four five six or you can write one two three four six five both of the linear ordering are two true so how did you get this very simple you call the dfs from here then you went here then you went here then you went here if you went here i was uh five was coming first or if you went here six was coming first now when you come back what i did was i just stored the six in a stack and then from four when i went to five and when i came back from five i stored it here and i went from four i stored the four here then for three i stored it here then for two I stored it here then for one i stored it yeah so what i did was the people whose dfs was complete i just stored it i just stored it i just stored it i just stored it now what happens is i know the dfs of three is completed which means this entire portion has been visited which means this entire portion has been visited so everything would have been here and the linear ordering will be followed 3 is before 4, 4 is before 6, 6 is before 5. Just because I know if I have done the DFS for 3, then everything would have been done. Everything would have been done.

Thereby, whenever I complete the DFS, then only I put it. Because I know everything would have been done. So if everything would have been done, everything would have been stacked below.

If I get it back, I'll get the linear ordering. That's a simple intuition. Nothing special.

Whenever the DFS is completed, everyone is touched. They just picketed. And the next guy would have called it. you will be now coming in so simple intuition so guys i hope i was able to explain you this particular algorithm so just in case i was please make sure you like this video and if you're new to our channel what are you waiting for hit that subscribe button right away and if you haven't checked out our dpcds and the hd sheet the links are in the description please make sure to check it out with this i'll be wrapping up this video let's meet in the next one until then bye bye take care

Transcript for:Topological Sorting Overview

Transcript for:
Topological Sorting Overview