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!
Mentioning not only DAG but Tree gives me a lot of intuitions... That's why I watch this channel even after I graduated and got a job. Studying never ends definetly. Thank you William.
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.
Finally understood it, much clearer than the exposition in my class. I now understand even why it works to give a topological ordering based on how you pop the call stack.
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
Very well explained! Thank you! At this point of my online uni, i'm just skim through the lecture recording and just search up related topic videos on youtube to learn. Why can't the uni just gave us a list of youtube videos to learn.
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!
Nice and easy explanation. Love it! I've got one little question, though. Let's take this tree you presents at 4:46 and let's pretend that these nodes are some functions in a program. When A got execute, B, C and D don't depend anymore on anything and could potentially run on separate threads. Let's also say that I know how threads and synchronization primitives work. How to split/detect what nodes can run concurrently? Is there any algorithm for it?
When you’re getting in a game you gotta first gather up all the OG’s (good players) first and then get the newbies (bad players) if you don’t have any more OG’s left. You need someone (Topological sort) to tell you which players are better than others in order to do this.
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]?
Sorry if this is a dumb question... From the animation you said that you could do topological sorting by choosing nodes at random and dfs down their children. But in the code, if I'm reading it correctly, you're just going in the order of the adjacency list. Are there any trade-offs here? Thanks, and great video for a tough topic!
You don't usually know how your DAG is structured/labelled exactly, so beginning at node 0 -> node n-1 is effectively random. You could traverse all the nodes in any permutation and you'll still get a topological sort. To answer your question, I'm not aware of any performance benefits of trying one particular permutation over another.
Thanks for this awesome video, I have a question. What if when only C and B vertices are remaining and we choose B vertex randomly, will that be correct too? Because choosing B will result in B being added to list and then again selecting C randomly(the only vertex remaining and that will be added at last) Will that be correct?
the result is still CB..., i think the key of post order is, let's say we have A and B, if A can lead to B then B would be after A(A...B), but if A can't lead to B, then we have 2 possible results: 1. B lead to A(B...A) 2. B and A don't have anything to do with each other, the relative position of them doesn't matter anymore(that also means A...B, or B...A are both accepted). That's why we can have multiple results.
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).
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?
i have a question. it might be dumb but anyway, when discussing topological sorting, shouldn't we start from a source node, i.e., a node that doesn't depend on any other nodes? In your example, you started from node H; is that correct?
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.
The numerical node values and counters were giving me a hard time understanding the code. So I wrote the same code for a different type of graph data. You don't need to maintain index for ordering array as the graph node data is of string type and we can easily concat them. Here's the code. package com.graph; import com.google.common.collect.Lists; import java.util.*; public class TSortPractice { static class EdgeV2 { String to; String from; public EdgeV2(String from, String to) { this.to = to; this.from = from; } } static int n = 5; static Map graph; static String ordering = " "; static Set visitRegister; public static void main(String[] args) { graph = new HashMap(n); visitRegister = new HashSet(n); graph.put("a", Lists.newArrayList(new EdgeV2("a", "b"), new EdgeV2("a", "c"))); graph.put("b", Lists.newArrayList(new EdgeV2("b", "d"))); graph.put("c", Lists.newArrayList(new EdgeV2("c", "d"))); graph.put("d", Lists.newArrayList(new EdgeV2("d", "e"))); topSort(); System.out.println(ordering); } static boolean notVisited(String node){ return !visitRegister.contains(node); } static void doVisit(String node) { visitRegister.add(node); } static void dfs(String currentNode) { doVisit(currentNode); if(graph.containsKey(currentNode)) { for(EdgeV2 edgeV2: graph.get(currentNode)) { String nextNode = edgeV2.to; if(notVisited(nextNode)) dfs(nextNode); } } ordering = currentNode+" "+ordering; } static void topSort() { Set nodes = graph.keySet(); for(String node: nodes) { if(notVisited(node)) dfs(node); } System.out.println("top sort done"); } }
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.
Mentioning not only DAG but Tree gives me a lot of intuitions... That's why I watch this channel even after I graduated and got a job. Studying never ends definetly. Thank you William.
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.
Omg!You are just the perfect one demonstrating these concepts so clearly.It's really friendly for beginners to learn.Thank you very much!
The way you explain stuff visually helps me understand the algorithms well. Thanks a ton!
Finally understood it, much clearer than the exposition in my class. I now understand even why it works to give a topological ordering based on how you pop the call stack.
I understood enough to complete my quiz at 1:06, great video!
This is the best explanation video for a graph algorithm. Can't get any better
The fact you can clearly explain the concept and Algo under 15mins, proves you have mastered this topic and gain deep understanding, kudos.
Thanks!
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.
Thanks William. Watched the whole MIT DFS class for Topological sort, finally understood it here.
This is a great tutorial! Really well explained; visually and in detail.
The number of times I have watched this video and number of times I have forgotten this concept is really funny!
yes :)
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.
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 a lot for this video, the algoritham is easy to understand because of the animation!
Finally a great video! Thanks William
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'!
Man you make difficult topic easy to understand, very nice video. It is very great , how you represent topics in abstract way:)
Your explanation is clear and examples are interesting.
Wow this tutorial is amazing! Made perfect sense to me!
Thank you, very clear and precise explanation.
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
Well structured and well explained tutorials. Thank you.
Clear explanation and nice code!
Very well explained! Thank you! At this point of my online uni, i'm just skim through the lecture recording and just search up related topic videos on youtube to learn. Why can't the uni just gave us a list of youtube videos to learn.
Thanks a lot William ! This is really helpful.
This is a really good tutorial! Thank you for your work!
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!
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
This video saved so much time. God bless you pal : ))
The good things is you went from total basics and that's what matters for understanding
Thank you so much, so clear and concise.
Appreciate it.
Clean, precise, awesome!!
Loved this !!!! Thaaaaanks a bunch ! Well explained !!
Thanks for this amazing video !
Kudos for explaining the topological sort in simplest way possible 🙂
Great explanation! Thank you.
Nice and easy explanation. Love it! I've got one little question, though. Let's take this tree you presents at 4:46 and let's pretend that these nodes are some functions in a program. When A got execute, B, C and D don't depend anymore on anything and could potentially run on separate threads. Let's also say that I know how threads and synchronization primitives work. How to split/detect what nodes can run concurrently? Is there any algorithm for it?
Thank you for great explanation!
Thank you so much.
A clear explanation!!
you are genius
Awesome video. Thanks!
can you explain it in fortnite terms?
When you’re getting in a game you gotta first gather up all the OG’s (good players) first and then get the newbies (bad players) if you don’t have any more OG’s left. You need someone (Topological sort) to tell you which players are better than others in order to do this.
data structures final on monday 😿💔saved me a ton of stress, thank you! 💗
GREAT, love the animation.
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)?
Might be good to explain how to use the topo sort result to then actually solve the course scheduling problem (for example).
kudos! thanks a lot for posting
Thank you very much!!
such a great animation, thanks!
Lots of hard work sir
Amazing viz, thank you!
thank you william
Again, Such a great video!
nice explanation.!
Nicely done, thanks!
10:59 We already has an array V to record the visited node. Why do you define another array visitedNodes?
Thanks man, you're the best!
Wow Thanks so much. Animation helped a lot
THANK YOU SO MUCH
GREAT explanation , Thank's
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
Thank you.
Great content man.
Awesome work man.
Sorry if this is a dumb question...
From the animation you said that you could do topological sorting by choosing nodes at random and dfs down their children.
But in the code, if I'm reading it correctly, you're just going in the order of the adjacency list.
Are there any trade-offs here?
Thanks, and great video for a tough topic!
You don't usually know how your DAG is structured/labelled exactly, so beginning at node 0 -> node n-1 is effectively random. You could traverse all the nodes in any permutation and you'll still get a topological sort. To answer your question, I'm not aware of any performance benefits of trying one particular permutation over another.
@@WilliamFiset-videos I see, that makes sense, thank you so much!
Thanks a lot.
Can you also do a video based on Kahn's Algorithm for topological sort, based on inDegrees rather than outDegrees?
Hi! visitedNodes plays a role of a stack, why you iterate it from the first element but not pop last to get order[i]?
top top explanation
thank you. extremely helpful. :D
In case of a rooted tree, is it sufficient to do the level order traversal to get the topological ordering?
Thanks for this awesome video, I have a question.
What if when only C and B vertices are remaining and we choose B vertex randomly, will that be correct too? Because choosing B will result in B being added to list and then again selecting C randomly(the only vertex remaining and that will be added at last)
Will that be correct?
the result is still CB..., i think the key of post order is, let's say we have A and B, if A can lead to B then B would be after A(A...B), but if A can't lead to B, then we have 2 possible results: 1. B lead to A(B...A) 2. B and A don't have anything to do with each other, the relative position of them doesn't matter anymore(that also means A...B, or B...A are both accepted). That's why we can have multiple results.
Simply beautiful
So good!
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).
This is sooo good!
Concise++!
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?
very useful
i have a question. it might be dumb but anyway, when discussing topological sorting, shouldn't we start from a source node, i.e., a node that doesn't depend on any other nodes? In your example, you started from node H; is that correct?
SSSP finding using topological sort approach, when would I not use this? Seems fastest for the usecase.
great video
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.
THANKS
Exellent work
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
if i have to reach D, the array says , i have to visit K ???
the short form that I've heard is "toposort" rather than "topsort"
BEAUTIFUL
Will this algorithm work if the graph has cycle? Or being a DAG is a prerequisite for using this algorithm?
late reply but yes it is a prerequisite
Lovely!
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?
How should i know which node is the starting or randomly choose?
Edward Huahui random
The numerical node values and counters were giving me a hard time understanding the code. So I wrote the same code for a different type of graph data. You don't need to maintain index for ordering array as the graph node data is of string type and we can easily concat them. Here's the code.
package com.graph;
import com.google.common.collect.Lists;
import java.util.*;
public class TSortPractice {
static class EdgeV2 {
String to;
String from;
public EdgeV2(String from, String to) {
this.to = to;
this.from = from;
}
}
static int n = 5;
static Map graph;
static String ordering = " ";
static Set visitRegister;
public static void main(String[] args) {
graph = new HashMap(n);
visitRegister = new HashSet(n);
graph.put("a", Lists.newArrayList(new EdgeV2("a", "b"), new EdgeV2("a", "c")));
graph.put("b", Lists.newArrayList(new EdgeV2("b", "d")));
graph.put("c", Lists.newArrayList(new EdgeV2("c", "d")));
graph.put("d", Lists.newArrayList(new EdgeV2("d", "e")));
topSort();
System.out.println(ordering);
}
static boolean notVisited(String node){
return !visitRegister.contains(node);
}
static void doVisit(String node) {
visitRegister.add(node);
}
static void dfs(String currentNode) {
doVisit(currentNode);
if(graph.containsKey(currentNode)) {
for(EdgeV2 edgeV2: graph.get(currentNode)) {
String nextNode = edgeV2.to;
if(notVisited(nextNode))
dfs(nextNode);
}
}
ordering = currentNode+" "+ordering;
}
static void topSort() {
Set nodes = graph.keySet();
for(String node: nodes) {
if(notVisited(node))
dfs(node);
}
System.out.println("top sort done");
}
}