Topological Sorting with examples | Topological Sorting using DFS | Imp For Placements & Comp. Exams
Topological Sorting with examples | Topological Sorting using DFS | Imp For Placements & Comp. Exams
👉Subscribe to our new channel:   / @varunainashots Â
👉Links for DAA Notes:
đź”—File-1: https://rb.gy/2byrg
🧑‍🎓Contributed by: Junaid Gazi
đź”—File-2: https://rb.gy/gibu5
🧑‍🎓Contributed by: Mannu Garg
Topological Sort or Topological Ordering:
* It is linear ordering of graph vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
* Applicable on DAG (Direct Acyclic Graph).
* Linear running time complexity.
* Topological sort is not unique.
â–şDesign and Analysis of algorithms (DAA) (Complete Playlist):
   • Design and Analysis of algorithms (DAA) Â
Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
â–ş Operating System :
   • Operating System (Complete Playlist) Â
â–şDatabase Management System:
   • DBMS (Database Management system) Com… Â
â–ş Theory of Computation
   • TOC(Theory of Computation) Â
â–şArtificial Intelligence:
   • Artificial Intelligence (Complete Pla… Â
â–şComputer Networks (Complete Playlist):
   • Computer Networks (Complete Playlist) Â
â–şComputer Architecture (Complete Playlist):
   • Computer Organization and Architectur… Â
â–şStructured Query Language (SQL):
   • Structured Query Language (SQL) Â
â–şDiscrete Mathematics:
   • Discrete Mathematics Â
â–şCompiler Design:
   • Compiler Design (Complete Playlist) Â
â–şNumber System:
   • Number system Â
â–şCloud Computing \u0026 BIG Data:
   • Cloud Computing \u0026 BIG Data Â
â–şSoftware Engineering:
   • Software Engineering Â
â–şData Structure:
   • Data Structure Â
â–şGraph Theory:
   • Graph Theory Â
â–şProgramming in C:
   • C Programming Â
â–şDigital Logic:
   • Digital Logic(Complete Playlist) Â
---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
â–ş Subscribe to us on YouTube:    / gatesmashers Â
â–şSubscribe to our new channel:    / @varunainashots Â
â–ş Like our page on Facebook: https://www.facebook.com/gatesmashers
â–ş Follow us on Instagram: https://www.instagram.com/gate.smashers
â–ş Follow us on Instagram: https://www.instagram.com/varunainashots
â–ş Follow us on Telegram: https://t.me/gatesmashersofficial
â–ş Follow us on Threads: https://www.threads.net/@gate.smashers
--------------------------------------------------------------------------------------------------------------------------------------
â–şFor Any Query, Suggestion or notes contribution:
Email us at: [email protected]
Content
0 -> Dear students, welcome to Gate Smashers
2.02 -> In today's video I am going to explain
topological sorting or topological ordering
7.04 -> So whenever we talk about graph based algorithm
10.06 -> that which algorithms are important
in your graph data structure
14.08 -> in your competitive exams and especially
from your placements point of view
18.844 -> So in those three algorithms are asked the most
22.066 -> BFS, DFS and topological sorting or topological ordering
26.12 -> So all the placements exam or interviews
30.14 -> So these three algorithms are asked the most graph based
35.177 -> So let's start
36.18 -> I will tell you with example about how it actually works
40.938 -> So first of all if we talk about topological sorting
44.049 -> It is a linear ordering of graph vertices such that
48.049 -> for every directed edge u, v
50.805 -> from vertex u to v comes before v
54.26 -> Means u comes before v in the ordering
57.049 -> See, you may not be able to understand this line
59.3 -> But the simple thing is that whenever we talk about graph
63.32 -> So in graph let's say I have a graph like this
68.34 -> And there is an edge u, v
71.36 -> Means it is going from u to v
73.38 -> So whenever we write its order, whenever we write its sorting
77.4 -> So remember in that order u should always come before v
83.4 -> It's just a simple thing and when is it always applicable
87.42 -> When we use direct acyclic graph
90.44 -> See, if I make the edge like this
94.46 -> Without any direction
96.48 -> So you can go from u to v
98.5 -> You can also go from v to u
100.52 -> So then in this case you can't say that u
should come first or v should come first
104.54 -> Anyone can come first
106.56 -> But when we make a directed
108.56 -> So I can see a clear cut in that that v is dependent on u
113.58 -> Means you can also say that u will be completed first
116.6 -> If we talk about a task
118.62 -> So this is also a task, this is also a task
120.64 -> So what does it mean?
121.66 -> That u should be finished first
123.68 -> Then you can go and do v
126.7 -> Means you will go in the second year
when you have completed the first year
131.966 -> Kind of this way you can understand it
134.544 -> And second, we know about direct
136.74 -> But what is the funda of acyclic?
139.56 -> If you take a graph and make a cycle in it
144.58 -> See, if you didn't take any directed edge
147.6 -> Then it's clear to you
148.62 -> But let's say I make a direction here
152.64 -> But the direction is also made in
such a way that it becomes a cycle
156.66 -> Can you see this?
157.68 -> This is the cycle
158.7 -> Can you see?
159.72 -> Now this cycle is made
160.74 -> Now there is a problem in this cycle too
162.76 -> How?
163.78 -> If you start from here
165.78 -> So you must be thinking that u
is coming first and v is coming here
169.8 -> But if you walk like this
171.82 -> Then you will know that u is coming after v again
176.84 -> Means there is a problem here again
178.86 -> Because the cycle is made here
179.88 -> Means there should be direction
181.9 -> And there should be acyclic graph
183.92 -> Only then this topological sorting is done
186.44 -> Okay?
187.46 -> Then it is a linear time complexity algorithm
190.48 -> It's a simple algorithm
192 -> In linear time, the order of v plus e
195 -> All the vertices, all the edges, just total them
198.02 -> That is a simple thing
199.54 -> Then topological sorting is not unique
202.06 -> What does unique mean?
203.58 -> It means if you give a graph
205.08 -> Then only one sorting order will be made in it
208.1 -> No, multiple can also be made in it
211.12 -> This was the theory part
212.64 -> Now you come to the main concept
214.66 -> Let's say I have a graph here
216.68 -> And you can see clearly that it is directed and acyclic too
221.2 -> There is no cycle in this
222.7 -> It is going from here to here, can't come back
225.22 -> If I make this edge like this
226.739 -> Then this cycle is made
227.76 -> But in this way, it is acyclic
229.78 -> Now look, in this I have written the topological order
232.799 -> BADC
235.82 -> Now look here, you can see clearly
238.839 -> Pick any two sets
240.359 -> Let's say I picked B and A
241.88 -> Now what is this?
242.899 -> U, what is this? V
244.42 -> Now you can see clearly according to the definition
247.44 -> That u should come first, v should come later
250.44 -> So look, B is coming first, A is coming later
252.76 -> Why? Because the edge is going like this
254.78 -> Now pick any set, pick B and D
257.8 -> So look, B is coming first, D is going from B to D
260.82 -> So look, B is coming first, D is coming later
263.34 -> So it is absolutely fine
264.56 -> Look at DC like this, D is coming first, C is coming later
267.28 -> So yes, the edge is also like this
269 -> So this is our valid topological order
272.02 -> Okay, then ABCD
274.04 -> Now look, ABCD
275.06 -> Now this is a mess here
276.58 -> There is no edge here between A and B
279.58 -> There is an edge between B and A
280.9 -> But you wrote B from A
283.419 -> Means this was U, this was V
286.44 -> In this, V came first, U came later
288.96 -> So this is not valid
291.979 -> Now look, the same unique, non-unique thing was talking
295 -> So you know, BADC is a valid topological sorting
300.52 -> But after B, I went to A
303.539 -> Can I go to D?
305.56 -> Yes, you can go to D after B
307.56 -> After D, you will go to C
310.58 -> And after C, you will go to A
312.6 -> If you make an order like this, then look now BD
315.62 -> So look, B is first, D is later
317.14 -> Absolutely fine, DC, D is first, C is later
320.16 -> According to the sequence
321.18 -> And look at A, A to D
323.2 -> If we talk about A to D, then look here D came first
326.72 -> And A came later
328.24 -> Look, D came first and A is later
330.26 -> But A should come first and D later
332.78 -> So this is also a wrong sequence
335.28 -> So you have to simply check in this way
338.299 -> That your order should be valid
341.32 -> Now how do we write this?
343.34 -> How we actually write it?
344.859 -> So there are multiple methods for this
346.38 -> You can use DFS, BFS algorithm
349.9 -> There are many Kahn's algorithms
351.919 -> But the most important thing is your DFS
354.94 -> Depth First Search
356.46 -> So how do we start in that?
358.479 -> In simple depth first search
360 -> We are unwhistled from any node
362.02 -> Now all are unwhistled
364.02 -> So you can start from anyone
366.039 -> Whoever is unwhistled
367.06 -> So let's say we start from B
369.08 -> So first of all we will run DFS on B
372.599 -> Okay? So we have run this method
374.62 -> DFS on B
375.64 -> So means first of all what happened to my V?
377.659 -> What happened to B? It got whistled in a way
379.18 -> So I write it as whistled
381.2 -> Or let's say I simply tick it
383.219 -> That it got whistled
384.24 -> Now where do I have the option to go after B?
386.76 -> After B I can go to A
388.78 -> So after B I went to A
390.799 -> Okay?
391.82 -> What happens in DFS?
393.32 -> That till you get the path
395.34 -> Till then you don't have to backtrack
397.36 -> Just keep searching, keep going in depth
399.38 -> So after B I went to A
400.9 -> You can also go to D, no problem
402.92 -> So we went to A
403.94 -> After A I went to D
406.46 -> So after A I went to D
408.98 -> Is there any other path from D?
410.5 -> Yes, there is C and E too
412.02 -> You can go to any of them
413.539 -> Let's say I went to C
415.56 -> You can go to any of them
416.58 -> But I went to C
417.6 -> There is no one to choose
419.12 -> So in this way I keep going
420.64 -> Now I stop at C
422.14 -> Because after C I have no path
424.159 -> C is a dead end
426.18 -> What is C? It is a dead end
427.7 -> So now what you have to do
429.219 -> It's a simple story
430.74 -> That when you reach dead end
432.76 -> Then you put it inside the stack
434.78 -> We have taken a stack
436.8 -> Whose size is equal to the number of nodes
438.82 -> It is equal to the number of vertices
440.84 -> So let's say C is the first one
442.86 -> Put it inside the stack
444.38 -> Okay?
445.4 -> C is the first one put inside the stack
447.419 -> You put a tip on my whistled
449.44 -> A got ticked, D got ticked
450.94 -> And C got whistled too
452.46 -> Now who did we put C in?
454.48 -> We put it in the stack
455.5 -> So C got deleted in a way
457.02 -> We went back to D
458.54 -> We backtracked
459.56 -> Because there is no path from C
461.08 -> So we went back to D from C
462.6 -> Is there any other option after D?
464.62 -> Yes, there is one more option
466.64 -> After D I can go to E
468.659 -> I have one option
470.68 -> So this too got whistled
472.2 -> Now there is no other option after E
473.72 -> This edge is like this
474.74 -> So there is no option after E
476.76 -> So this is also independent
478.78 -> It is not dependent on anyone
480.28 -> So I put E in the stack too
482.299 -> I put it in the stack
483.82 -> So what happened to E?
484.84 -> It got whistled and finished
486.059 -> I went back to D again
487.88 -> Is there any other path from D?
489.4 -> No, there was C and E
490.419 -> Both got whistled
491.44 -> So now what happened to D?
493.46 -> It got finished
494.679 -> So I went back to A from D again
497.2 -> I went back to A from D again
499.219 -> Backtracked
500.239 -> Was there any other option from A?
501.76 -> No, there was no other option from A
503.28 -> So A got deleted from here too
505.299 -> And A got put inside my stack
507.32 -> Because what is this too?
508.82 -> Now it is independent, there is no dependency on it
510.84 -> From A I went backtracked again
512.86 -> And came to B
513.88 -> When I came to B
514.9 -> Is there any other route?
516.919 -> There was route of D
517.939 -> But D is already whistled
519.96 -> It is ticked
520.98 -> So there is no other path
523 -> So my B got made like this
526.02 -> So let's see if the graph would be this much
528.04 -> If it would be of this much vertex
529.56 -> Then you just pop the elements from the stack
531.58 -> And this becomes your route
533.1 -> This becomes your order
534.12 -> But now we have unwhistled more
537.022 -> So the loop of DFS
538.733 -> Will look for more
539.66 -> That are all whistled? No
541.18 -> Now I have G
542.699 -> So I will run DFS on G again
545.22 -> Separately
546.24 -> I ran DFS on G
547.76 -> Any other route from G?
549.78 -> I can go from G to F
551.8 -> So I went to F
553.819 -> I can go from F to E
555.34 -> But E is already whistled
556.86 -> So there is no other path
558.38 -> So I take out F from here
560.9 -> And here F went to where?
563.42 -> Because there is no other path from F
564.939 -> This is also whistled, this is also whistled
566.94 -> From F again, then I backtracked to G
569.96 -> So here my G is also finished
571.98 -> So here only one left, now H
574 -> Now again in the loop
576.02 -> When they check if there is any other unwhistled of DFS
579.54 -> So one more is left H
581.06 -> So H is whistled
582.58 -> And there was another path from H
584.1 -> There was F but F is already whistled
585.62 -> So finally your H is also deleted
588.14 -> And this went inside the stack
590.66 -> Now just take out the elements
592.68 -> When you take it out
593.7 -> Then what comes to you?
595.22 -> Last in first out
596.72 -> So here which was the last in? H
598.74 -> So H will come first
600.26 -> Then G came
601.28 -> Then F came
602.3 -> Then B came
602.82 -> Then A came
603.84 -> Then D came
604.56 -> Then E came
605.58 -> Then C came
606.1 -> So here is your valid sorting
609.12 -> Or valid topological ordering is made
611.34 -> But I am saying that this is non-unique
614.06 -> What does non-unique mean?
615.08 -> You went from B to A
617.1 -> I went from B to A from here
619.12 -> You could have gone from B to D too
620.64 -> Then another would have been made
622.16 -> Let's say we started from B
623.38 -> If you start from G
624.68 -> Then you can make more like this from G to D
627 -> If you start from H, someone else would have been made
629.02 -> But whatever will be made should be valid
631.04 -> So you check anyone in this
633.06 -> Let's say you check B, A
634.78 -> Okay?
635.3 -> Now see B is first, A is later
637.319 -> So here B is first, A is later
639.04 -> So you can check anyone
640.56 -> So a valid sequence is made like this
643.079 -> So here if we talk about time complexity
645.099 -> So we did that actually we covered all the vertex
650.62 -> In a way traversed it
652.12 -> And we will cover all the edges in the worst case
656.64 -> Nothing more than this
658.06 -> So order of V plus E
660.68 -> Total number of vertex plus total number of edges
663.4 -> This is the time complexity which is linear
665.62 -> Because whatever is more among both
667.44 -> And generally if the edges are more
668.96 -> Then you can say order of E too
670.98 -> Okay?
671.5 -> If we talk about space complexity
673.52 -> So this is given to me
675.04 -> I took this extra space stack
677.56 -> And the maximum size of this stack can be
680.56 -> The number of vertexes I have
682.079 -> So order of V is your extra space complexity
686.099 -> You can say that
687.119 -> So this is all about that topological sorting using DFS
691.144 -> Thank You.
Source: https://www.youtube.com/watch?v=3tkcfvCNtM8