Topological Sort Algorithm | Graph Theory 

Clear, concise, great animation! Thank you so much buddy.

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!

Omg!You are just the perfect one demonstrating these concepts so clearly.It's really friendly for beginners to learn.Thank you very much!

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.

The way you explain stuff visually helps me understand the algorithms well. Thanks a ton!

This is a great tutorial! Really well explained; visually and in detail.

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.

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.

This is the best explanation video for a graph algorithm. Can't get any better

I understood enough to complete my quiz at 1:06, great video!

Thanks William. Watched the whole MIT DFS class for Topological sort, finally understood it here.

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!❤️❤️

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.

The best explanation I could find online!

The number of times I have watched this video and number of times I have forgotten this concept is really funny!

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'!

Hello everyone, I released another video on how to find the topological sort of a graph using Khan's algorithm (which is arguably easier to understand than the DFS solution IMO): ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-cIBFEhD77b4.html

Man you make difficult topic easy to understand, very nice video. It is very great , how you represent topics in abstract way:)

Well structured and well explained tutorials. Thank you.

Thanks a lot for this video, the algoritham is easy to understand because of the animation!

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.

This is a really good tutorial! Thank you for your work!

Finally a great video! Thanks William

Thank you so much, so clear and concise. Appreciate it.

This video saved so much time. God bless you pal : ))

The fact you can clearly explain the concept and Algo under 15mins, proves you have mastered this topic and gain deep understanding, kudos.

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.

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.

Thanks a lot William ! This is really helpful.

Clean, precise, awesome!!

Great explanation! Thank you.

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.

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?

Again, Such a great video!

Thanks for this amazing video !

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!

Thank you so much. A clear explanation!!

Clear explanation and nice code!

Nicely done, thanks!

The good things is you went from total basics and that's what matters for understanding

Kudos for explaining the topological sort in simplest way possible 🙂

Loved this !!!! Thaaaaanks a bunch ! Well explained !!

In case of a rooted tree, is it sufficient to do the level order traversal to get the topological ordering?

Awesome work man.

Wow Thanks so much. Animation helped a lot

GREAT, love the animation.

Thanks man, you're the best!

Thank you for great explanation!

Awesome video. Thanks!

such a great animation, thanks!

This is sooo good!

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.

thank you. extremely helpful. :D

GREAT explanation , Thank's

Amazing viz, thank you!

kudos! thanks a lot for posting

10:59 We already has an array V to record the visited node. Why do you define another array visitedNodes?

THANK YOU SO MUCH

thank you william

Exellent work

Hi! visitedNodes plays a role of a stack, why you iterate it from the first element but not pop last to get order[i]?

Can you also do a video based on Kahn's Algorithm for topological sort, based on inDegrees rather than outDegrees?

Thanks!

Great content man.

Thanks a lot.

Concise++!

Thank you.

what is equivalent of V[edge.to] in python ?

Might be good to explain how to use the topo sort result to then actually solve the course scheduling problem (for example).

Lots of hard work sir

So good!

if i have to reach D, the array says , i have to visit K ???

top top explanation

very useful

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.

Lovely!

great video

thanks so much, may I ask, what do you mean by "canonical" example? (1:59)

THANKS

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)?

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?

BEAUTIFUL

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?

SSSP finding using topological sort approach, when would I not use this? Seems fastest for the usecase.

nice! and neat!

Simply beautiful

How should i know which node is the starting or randomly choose?

you are genius

good video!

You rock!

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?

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!

Great

yeah but how do you detect cycles with this method?

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"); } }

can you explain it in fortnite terms?

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]?

suscribed