be careful that the graph you use for this has no cycles, if it does the algorithm will give you an incorrect ordering (impossible to do topological sort with cycles in the graph)
According to geeksforgeeks "The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges)". Why you here chose 'A' as starting vertex?
The first vertex in a topologically sorted array of vertices has an in-degree of 0. We haven't yet built a topologically sorted array at the time of picking 'A'. We pick 'A' in order to begin building that array.
To clarify what he said, when you START topological sorting, you can choose any vertex. However, the output after top sorting is a vertex with an in-degree of 0.
The video is understood easily. It would be better understood if u can take an array of elements and construct the graph and then do the topological sort.
Ok I have a question here! I understood the tutorial but how the for loop is running from "0 to V" . I mean the code is written for A->B... vertices and the vertices in the code snippet (in function topologicalSort) is shown for vertices 0->1... ; I know the question sounds stupid but what if the vertices were assigned numbers starting from 99? I think m missing something.. thanks?
you didn't discuss the condition for starting node i.e. can we start DFS which has an incoming edge e.g. swap the id's of A and B, then start DFS with A?
@@it41tanmayaron26 Since we only have one way directed edges and there is no cycle we have to provide the condition for starting nodes. I used a naive approach to avoid starting with such nodes which have an incoming edge. We add an extra cost of O(|V|) for finding the root nodes by traversing the whole DAG, say ROOTS. Then we perform Topological sort starting from each root node i in ROOTS. The extra cost can be neglected w.r.t to the total runtime of Topological sort.
I think then you can resort to take a edge list implementation, where the list is a min heap or max heap based on requirement. So that it doesn't only picks based on unvisited but also considers weight. I think something like this is used in task schedulers like spark driver or yarn 😅 not sure
Do they force Indians to make tutorial videos as an assignment? They just seem to be the only ones with tutorials on RUclips even though they aren't the only ones that know this. Good job people
In the explanation, I did not understand how G is never inserted to stack till very end. since all it's neighbours are visted and SortUtil end statement is reachable for G node ryt. So G should be much deeper in stack. How did it jumped to D. Am I getting something wrong. Great explanation though.
At the end he says the time complexity is O(V + E). This is just his way of explicitly naming what the factors are. V + E is linear meaning that, the time complexity is O(N). He did not answer about the space complexity, but I think it would also be constant. Each node can hold the data about whether it was visited and which neighbors it has. There should be no reason to have to exponentially save more data when the list of nodes increases. It would be linear.
If using an adjency matrix to represent the graph, then for a given edge adjMatrix[i][j] check adjMatrix[j][i] to see if there's a corresponding edge. If so, then the graph is cyclical.
@@darkstarggez2103 Graph can have many topological sort based on starting node I suppose. But for starting node of G, G should be deep inside the stack ryt after C is put inside. ..... for this one. According to the C++ code the recursion os sortutil would end with insertion of G to stack
Hi Manasratan, Topological Sorting takes the DFS approach to print the nodes. And, it's time complexity is same as that of a DFS: O(V+E). The only difference here is that we maintain an extra stack where we temporarily store nodes. So, the space complexity becomes O(V). Hope it helps.
No. In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices. So Topological sorting is different from DFS. For example, a DFS of the shown graph is “5 2 3 1 0 4”, but it is not a topological sorting. This better explained with the help of a diagram over here: www.geeksforgeeks.org/topological-sorting/
from programming point, traversal method is same, while DFS uses queue to print its values, Topological sort uses stack. Bottom line: reversing the DFS values gives you topological sort
I just want to express my appreciations to my Indian colleagues for producing so many high quality CS related content!
CS as in Counter-Strike? C Sharp? Computer Science?
@Taslim Arif I think he meant India produces good content for other two areas as well
Fax
@@Ajay-qv6fk XD
Watch at 1.5 X speed
watch at 2X.
@@timetraveler6780 watch at 3 * 10^8 m/sec
@@aadishjain6838 😂😂😂
@@aadishjain6838 Nailed it...Brooooooooooooo🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣
Try to listen at 0.5x, it's much more funnier🤣🤣🤣🤣🤣
Thank you Illuminati for contributing this video, the explanation is clear and easy to understand.
why are you calling him illumnati
@@noumanmustafa7435 Look at the description ! XD
really time saving and appropriate explanation ! we need these types of explanations in viva's
be careful that the graph you use for this has no cycles, if it does the algorithm will give you an incorrect ordering (impossible to do topological sort with cycles in the graph)
It can also be applied when we want to assign level of each vertex
Best Ever Explanation.Please upload more video on Graphs as we have limited videos on Graph topics.Thanks
According to geeksforgeeks "The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges)". Why you here chose 'A' as starting vertex?
The first vertex in a topologically sorted array of vertices has an in-degree of 0. We haven't yet built a topologically sorted array at the time of picking 'A'. We pick 'A' in order to begin building that array.
Fine
To clarify what he said, when you START topological sorting, you can choose any vertex. However, the output after top sorting is a vertex with an in-degree of 0.
Настали времена когда индусы объясняют лучше чем лекторы с вмк
GeeksforGeeks is illuminati, CONFIRMED!
**plays X-files theme**
The video is understood easily. It would be better understood if u can take an array of elements and construct the graph and then do the topological sort.
What's the point of array then?
can we use BFS for Topological sort?
if not then why can't?
DFS vs Topology? would they give same/different results?
what is illuminati??
question for anyone who can answer: How do we know we start from a source vertex? thanks
just start at the beginning of your bool visited array and skip items if they get turned to true along the way
Ok I have a question here! I understood the tutorial but how the for loop is running from "0 to V" . I mean the code is written for A->B... vertices and the vertices in the code snippet (in function topologicalSort) is shown for vertices 0->1... ; I know the question sounds stupid but what if the vertices were assigned numbers starting from 99? I think m missing something.. thanks?
indexing always start with 0 that A, B, C.. are just representation similarly you can't start a vertex from 99..
you didn't discuss the condition for starting node i.e. can we start DFS which has an incoming edge e.g. swap the id's of A and B, then start DFS with A?
You got the answer???
@@it41tanmayaron26 Since we only have one way directed edges and there is no cycle we have to provide the condition for starting nodes. I used a naive approach to avoid starting with such nodes which have an incoming edge. We add an extra cost of O(|V|) for finding the root nodes by traversing the whole DAG, say ROOTS. Then we perform Topological sort starting from each root node i in ROOTS. The extra cost can be neglected w.r.t to the total runtime of Topological sort.
Thanks a lot Illuminati!
Despite the heavy accent, the material is really clearly instructed. Gj
Splendid explanation! Btw, as a non-native speaker i'm incredibly thankful for your accent:D
Thanks Trinitas!
Now implement that script but with weighted edges.
I think then you can resort to take a edge list implementation, where the list is a min heap or max heap based on requirement. So that it doesn't only picks based on unvisited but also considers weight. I think something like this is used in task schedulers like spark driver or yarn 😅 not sure
Thanks for sharing your knowledge mate! Very well explained
the example has cycles in it, right? but topological sort is for acyclic graphs? right?
Very clear and easy to follow, thanks!
I got stuck at geeksforgeeks code, after seeing this video it completely cleared
So... did you get placed?
Respect! GFG is lifeline fro indian CSE students
Do they force Indians to make tutorial videos as an assignment? They just seem to be the only ones with tutorials on RUclips even though they aren't the only ones that know this. Good job people
no XD
DAMMIT!!! SUCH A GOOD EXPLANATION! :D
Very well explained, thanks!
Nice Video, I like explanation and sweet voice :)
how do you implement this code for a graph of letters. I'm getting an error "Segmentation Fault: 11"
Use unordered_map if you are using c++, if you use java then use hashmap.
I think that i also done this same question my B.F.S also kis kisko lagta hai ki BFS se bhi ho sakta hai 🙄
yes using kahn's algo
In the explanation, I did not understand how G is never inserted to stack till very end. since all it's neighbours are visted and SortUtil end statement is reachable for G node ryt. So G should be much deeper in stack. How did it jumped to D. Am I getting something wrong. Great explanation though.
there can be more than one topological ordering for any DAG, so u can construct another topological ordering with G much deeper in the stack too
Would the time and space complexity of this algorithm both be O(N)?
What is N here?
At the end he says the time complexity is O(V + E). This is just his way of explicitly naming what the factors are. V + E is linear meaning that, the time complexity is O(N).
He did not answer about the space complexity, but I think it would also be constant. Each node can hold the data about whether it was visited and which neighbors it has. There should be no reason to have to exponentially save more data when the list of nodes increases. It would be linear.
@@anthonyruffino2212 space complexity is O(V) due to stack
how do you know which node to start with
thank you so much💕. You saved me! I have a final exam today.
Me too
Is it Depth first traversal is De same to Topoligal sort? Like why is has Different name but same algo?
Shauk bdi cheez h
@@it41tanmayaron26 ??
Quick and clear, thank you so much!!!!
Can we apply this for weighted graph?
DFS and Topological are the same?
After pushing A to the stack, how did he visit C?
Marcos C. Santos he is moving alphabetically and so after pushing A he moved to B but as B is already visited, he then moved to C.😊✌
Real Bonanza thank you. :D
@@travelspurs but u can visit any unvisited node like G ,D and then procede because u can see topological sort is not unique
@@travelspurs am i right?
@Taslim Arif Thanks
Really well explained. Thanks a lot!
You're welcome, Yogesh! :)
so how do you check if there is a cycle?
If using an adjency matrix to represent the graph, then for a given edge adjMatrix[i][j] check adjMatrix[j][i] to see if there's a corresponding edge. If so, then the graph is cyclical.
Try DFS. If program doesn't stop compiling, then you are stuck in a cycle
GreeksforGeeks Need no introduction 👌
simple short and useful
How come after we push D into the stack we go to G and not J? Would we get the same result if we visited J then G?
like he said at the start of the video a graph can have many topological sorts the one represented above is just one of many others
@@darkstarggez2103 Graph can have many topological sort based on starting node I suppose. But for starting node of G, G should be deep inside the stack ryt after C is put inside. ..... for this one. According to the C++ code the recursion os sortutil would end with insertion of G to stack
Author Illuminati! 😂 xD
*wait...*
*plays X-files theme*
Read description lol
you did not explain time complexity........
Hi Manasratan,
Topological Sorting takes the DFS approach to print the nodes. And, it's time complexity is same as that of a DFS: O(V+E). The only difference here is that we maintain an extra stack where we temporarily store nodes. So, the space complexity becomes O(V). Hope it helps.
Can i get a C code for this question?
Yes. And what for main course?
Clean explanation. Thanks.
Afyer sorting A, why u directly move to D, why not G???
You can move to any unvisited node, but the person explaining is visiting nodes in alphabetical order
Real Great! Thank you
Best explanation!
Mann...wait...
Contributed by Illuminati.????
Username!!! Of writer
here also we use only stack but why
You can use an array. When you're done, the nodes in the array are in reverse order.
Thoda jaldi bola karo yaar kuuch logon ko subah panvel nikalna hai
this topological sort doesnt make sense
so is topological sorting same as DFS ??
No.
In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices. So Topological sorting is different from DFS. For example, a DFS of the shown graph is “5 2 3 1 0 4”, but it is not a topological sorting.
This better explained with the help of a diagram over here: www.geeksforgeeks.org/topological-sorting/
Ok understood it better
Thank you
noooooooooo, in no way, its sorting technique whereas dfs is traversal
simply put: topological ordering uses DFS to scan/traverse the graph in every round.
from programming point, traversal method is same, while DFS uses queue to print its values, Topological sort uses stack.
Bottom line: reversing the DFS values gives you topological sort
Does it work if graph have cycles
Very helpful! Thank you :)
beautiful 2see old school c++ code
xD
Very helpful!
Your subtitles comes over the video content
Very clearly explained
using this technique my answer is little Deferent,
So???? Nice??
very nice explanation
Thanks Aazim.
great explanation!
Thanks Harsha!
Thank for making good content video
Question is, did he read?
Nice explanation. Thanks a lot :-)
So.. you got placed?
great vid
really clear explanation!!
Thanks FENG YU SUNG :)
bearable only at speed of 2
Thank you sir
thank you
illuminated explanation
funny accent
Good tutorial
1.75X speed
Amazing
illuminati members hit like
3:10
Ratta marke bola sub kuch😂😂😂😂😂😂😂😂😂😂😂😂😂
thank you!:D
Improve voice plz
Jesus bless you.Thank you
*Ram
Thank you
You're welcome mostafa :)
great going
Thanks Vineet!
great explanation
True!!
Thank 🙏💕u so much sir
He didn't even read it
that funny fake voice tone!
Hey Illuminati.🤣🤣
1.25x
thanks man!
Very poor explanantion