The world needs more heroes like you who can spend less than 15 minutes explaining what takes certain professors at least two hours. This was really intuitive for both newcomers and detailed enough to actually wrote code with it. Thank you!
These tutorials are excellent. I wish I could thumbs up 10 times. I'm studying for coding interviews and this is the best tool I have come across for understanding graph theory problems.
An application of DAGs is representing circuits as a collection of gates, where subsequent gates require the inputs of previous gates, which is a perfect problem to use topological sorting on as it allows for iterative solutions to circuit propagation!
Another great mind at explaining things the way I like to understand them. First video I've seen on your channel. Instant subscribe and set notification on 'All'!
Your videos are very well produced, thank you very much for the efforts you put into them! Like some other folks have said, I wish Kahn's algorithm was also covered, it is pretty intuitive too and allows for cycle detection.
Thanks for the suggestion Louis, Kahns truly is a really great algorithm. It's especially good for beginners because it's soo simple and intuitive. I'll put together a video if I find the time
The tree example is unconnected with your algorithm for TopSort; If the TopSort algorithm is using indegree then the tree example will be really good as an introduction as they are using similar idea. It'd be great if you could always explain the runtime complexity. For this one, why it is O(V+E)?
Hi, First of all thank you for your explanation. I find your videos very helpful. But I have a question about the example code of your git repository about topological sort. graph.get(0).add(new Edge(0, 1, 3)); graph.get(0).add(new Edge(0, 2, 2)); graph.get(0).add(new Edge(0, 5, 3)); graph.get(1).add(new Edge(1, 3, 1)); graph.get(1).add(new Edge(1, 2, 6)); graph.get(2).add(new Edge(2, 3, 1)); graph.get(2).add(new Edge(2, 4, 10)); graph.get(3).add(new Edge(3, 4, 5)); graph.get(5).add(new Edge(5, 4, 7)); int[] ordering = topologicalSort(graph, N); // // Prints: [6, 0, 5, 1, 2, 3, 4] System.out.println(java.util.Arrays.toString(ordering)); So my question: if node 6 doesn't have relation with any node in any role, why the program return array : [6, 0, 5, 1, 2, 3, 4]?
any reason why you use a list and have to worry about/handle an index, when you could just use a stack? and pop from stack to get the ordering? it seems much easier to do without having to code up extra stuff to handle the index.
Thank you for this video! What happens in a case that we have a cycle. I'm pretty sure that the algorithm that you provided does not cover this end-case.
Why is it important that we only append the value when we're finishing the recursive call, and then reverse it, rather than appending when we mark a node as visited and not needing to reverse the output?
canonical (adj) MATHEMATICS relating to a general rule or standard formula. Basically, it just means this is a very common example throughout computer science, often used when teaching or describing the topic (toposort that is).
This is not handling possible cycles in the data. Also, is a recursive approach a good practical choice, considering the possibility of stack overflows?
How will you do this on an unconnected graph? for example if you had 3 more nodes that were graph that stand next to your graph. I think, in this case you will have to have a graph class and run the DFS on each node until you finish the list of nodes.
Hi, it doesn't matter where the DFS(s) starts. Remember that we're adding nodes in reverse order to our top sort ordering on the recursive callbacks so that the final result is in the correct ordering.
This implementation doesn't take care of the cycles. Here's a link to a good explanation for topsort with cycle handling leetcode.com/articles/course-schedule-ii/?page=2
The world needs more heroes like you who can spend less than 15 minutes explaining what takes certain professors at least two hours. This was really intuitive for both newcomers and detailed enough to actually wrote code with it. Thank you!
Clear, concise, great animation! Thank you so much buddy.
I read comments before watching a tutorial, thanks for the comment.
I searched for a video on this topic and this is the only one I found that explained it so well. Great job, I will share it with my classmates.
These tutorials are excellent. I wish I could thumbs up 10 times. I'm studying for coding interviews and this is the best tool I have come across for understanding graph theory problems.
This is the best explanation video for a graph algorithm. Can't get any better
The number of times I have watched this video and number of times I have forgotten this concept is really funny!
I understood enough to complete my quiz at 1:06, great video!
The fact you can clearly explain the concept and Algo under 15mins, proves you have mastered this topic and gain deep understanding, kudos.
Omg!You are just the perfect one demonstrating these concepts so clearly.It's really friendly for beginners to learn.Thank you very much!
I understand that I’m a bit late to the party but this is genuinely a brilliant explanation of Top Sort! Thank you so much!❤️❤️
Thanks William. Watched the whole MIT DFS class for Topological sort, finally understood it here.
The way you explain stuff visually helps me understand the algorithms well. Thanks a ton!
The best explanation I could find online!
It was not clear to me why the sorting process could starts from any node of the graph. I finally found the answear in your animiation. Thanks a lot.
Thank you for this. I have a final in my Data Structures and Algorithms course today, and I didn't understand this subject. Now I do. Thank you.
This is a great tutorial! Really well explained; visually and in detail.
Finally a great video! Thanks William
The good things is you went from total basics and that's what matters for understanding
An application of DAGs is representing circuits as a collection of gates, where subsequent gates require the inputs of previous gates, which is a perfect problem to use topological sorting on as it allows for iterative solutions to circuit propagation!
Man you make difficult topic easy to understand, very nice video. It is very great , how you represent topics in abstract way:)
Thank you, very clear and precise explanation.
Wow this tutorial is amazing! Made perfect sense to me!
Another great mind at explaining things the way I like to understand them.
First video I've seen on your channel. Instant subscribe and set notification on 'All'!
Your videos are very well produced, thank you very much for the efforts you put into them! Like some other folks have said, I wish Kahn's algorithm was also covered, it is pretty intuitive too and allows for cycle detection.
Thanks for the suggestion Louis, Kahns truly is a really great algorithm. It's especially good for beginners because it's soo simple and intuitive. I'll put together a video if I find the time
Thanks a lot William ! This is really helpful.
Clean, precise, awesome!!
Thanks for this amazing video !
Great explanation! Thank you.
This video saved so much time. God bless you pal : ))
Thank you so much, so clear and concise.
Appreciate it.
Thank you for great explanation!
The tree example is unconnected with your algorithm for TopSort; If the TopSort algorithm is using indegree then the tree example will be really good as an introduction as they are using similar idea. It'd be great if you could always explain the runtime complexity. For this one, why it is O(V+E)?
Loved this !!!! Thaaaaanks a bunch ! Well explained !!
GREAT, love the animation.
nice explanation.!
Amazing viz, thank you!
kudos! thanks a lot for posting
THANK YOU SO MUCH
thank you william
Thanks man, you're the best!
Lots of hard work sir
Thank you.
Wow Thanks so much. Animation helped a lot
GREAT explanation , Thank's
Simply beautiful
Great content man.
Thanks a lot.
Hi, First of all thank you for your explanation. I find your videos very helpful. But I have a question about the example code of your git repository about topological sort.
graph.get(0).add(new Edge(0, 1, 3));
graph.get(0).add(new Edge(0, 2, 2));
graph.get(0).add(new Edge(0, 5, 3));
graph.get(1).add(new Edge(1, 3, 1));
graph.get(1).add(new Edge(1, 2, 6));
graph.get(2).add(new Edge(2, 3, 1));
graph.get(2).add(new Edge(2, 4, 10));
graph.get(3).add(new Edge(3, 4, 5));
graph.get(5).add(new Edge(5, 4, 7));
int[] ordering = topologicalSort(graph, N);
// // Prints: [6, 0, 5, 1, 2, 3, 4]
System.out.println(java.util.Arrays.toString(ordering));
So my question: if node 6 doesn't have relation with any node in any role, why the program return array : [6, 0, 5, 1, 2, 3, 4]?
Node 6 doesn't have any dependencies, and no other node depends on it, therefore it can be placed anywhere in the topological ordering
Thanks!
any reason why you use a list and have to worry about/handle an index, when you could just use a stack? and pop from stack to get the ordering? it seems much easier to do without having to code up extra stuff to handle the index.
can you explain it in fortnite terms?
Will this algorithm work if the graph has cycle? Or being a DAG is a prerequisite for using this algorithm?
Awesome work man.
great video
This is sooo good!
BEAUTIFUL
Lovely!
Might be good to explain how to use the topo sort result to then actually solve the course scheduling problem (for example).
Thank you for this video!
What happens in a case that we have a cycle. I'm pretty sure that the algorithm that you provided does not cover this end-case.
You can't topologically sort a graph that has a cycle. 3:45
@@deepakr.sastry756 that’s correct.
You still need to check end cases. A user can input a graph that is not a DAG.
@@enoshcohen 4:39 check using Tarjan's
THANKS
Why is it important that we only append the value when we're finishing the recursive call, and then reverse it, rather than appending when we mark a node as visited and not needing to reverse the output?
10:59 We already has an array V to record the visited node. Why do you define another array visitedNodes?
if i have to reach D, the array says , i have to visit K ???
In case of a rooted tree, is it sufficient to do the level order traversal to get the topological ordering?
Exellent work
Can you also do a video based on Kahn's Algorithm for topological sort, based on inDegrees rather than outDegrees?
SSSP finding using topological sort approach, when would I not use this? Seems fastest for the usecase.
topological orderings are not necessarily unique, but they can be unique.
very useful
the short form that I've heard is "toposort" rather than "topsort"
Thanks mom
nice! and neat!
You are 3blue1brown for computer science.
9:17 from the given solution , K is given before I but K does not have a path to I. Is it supposed to happen,can you please tell me?
Great
You rock!
great video if you play it in 1.5x speed
I don't understand why we need to make a visitedNodes array when we already have V...
python implementation:
```graph = [[1, 2, 3], [5], [], [], [2, 3], [2]]
visited = [False] * len(graph)
ordering = list()
def dfs(node):
visited[node] = True
for neig in graph[node]:
if not visited[neig]:
dfs(neig)
ordering.insert(0, node)
for i in range(len(graph)):
if not visited[i]:
dfs(i)
print(ordering)```
seems like they should just call it a DAG sort instead of topological sort.
......WOW
thanks so much, may I ask, what do you mean by "canonical" example? (1:59)
canonical (adj)
MATHEMATICS
relating to a general rule or standard formula.
Basically, it just means this is a very common example throughout computer science, often used when teaching or describing the topic (toposort that is).
suscribed
I would prefer if you have your voice a little louder
Could be more concise, but good video.
Could this animation BE ANY better!?
This is not handling possible cycles in the data. Also, is a recursive approach a good practical choice, considering the possibility of stack overflows?
why do not start for in-degree is 0??????
How will you do this on an unconnected graph? for example if you had 3 more nodes that were graph that stand next to your graph. I think, in this case you will have to have a graph class and run the DFS on each node until you finish the list of nodes.
the algorithm shown in the video will also cover the secnario metioned in this comment.
Mark Zuckerberg is an awesome teacher.
Bro really said it's not that hard n precedes to say dig until bedrock😂
bro sounds like he divorced the day before
oh boi
get a pop filter bro
you can't start with H, it depends on D... start with C
Hi, it doesn't matter where the DFS(s) starts. Remember that we're adding nodes in reverse order to our top sort ordering on the recursive callbacks so that the final result is in the correct ordering.
Watch it in 2x.
This implementation doesn't take care of the cycles. Here's a link to a good explanation for topsort with cycle handling leetcode.com/articles/course-schedule-ii/?page=2
GOOD, BUT YOU SPEAK WAY TO SLOW.
its the best video ever uploaded to you tube.
EVER,
LIKE FOR EVER.
(DABs like a boss)
God Damm it feels good to be me.
This guy knows how to live life
Thanks a lot for this video, the algoritham is easy to understand because of the animation!