Welcome back. Today's topic is topological sort, also called top sort for short. We're going to discuss what is top sort, where it's used and how to find a topological ordering with some animation. The motivation for top sort is that many real world situations can be modeled as a graph of nodes, and directed edges where some events have to occur before others. Some simple examples include school class prerequisites, program dependencies, event scheduling, assembly, instruction ordering, and much much more. Let's begin with an example.

Suppose you're a university student, and you really want take class H. Well, before you can enroll in class age, you must first take classes the an E but before taking classes D, you must also take classes A and B, which have no prerequisites. So in some sense, there appears to be an ordering on the nodes of the graph. If we needed to take all the classes, the top sort algorithm would be capable of telling us the order in which we should enroll in classes, such that we never enroll in a course, which we do not have prerequisites for. Another canonical example of an application of top sort is for program build dependencies. A program cannot be built unless all its dependencies are first built. For example, consider this graph where each node represents a program and the edges represent that one program depends on another to run.

Well if we're trying to build program j On the right hand side, then we must first build program H and G. But to build those, we also need n f. But to build those we also need and so on. The idea is to first build the programs without dependencies and then move on. From there. How do we find a valid ordering in which to build all the programs? Well, this is where tops are comes into play. One possible ordering might be to start by building a, then building C, B, D, F, E, G, H, and then J.

Notice that there are unused dependencies in this case, and that will happen from time to time which is fine. So in conclusion, top sort is an algorithm which will give us a topological ordering on a directed graph, a topological order Ordering is an ordering of nodes for which each edge from node A to node B. node A appears before node B in the ordering. If it helps, this is just a fancy way of saying that, we can align all the nodes in a line and have all the edges pointing to the right. And important note to make that topological orderings are not unique. As you can imagine, there are multiple valid ways to enroll in courses, such that you can still graduate or to compile a program and its dependencies in a different order than you previously did. Sadly, not every type of graph has a topological ordering.

For example, any graph with a directed cycle cannot have a valid ordering. Well think of why this might be true. There cannot be an order if there is a second dependency. Since there is nowhere to start, every node in a cycle depends on another. So any graph with a directed cycle is therefore forbidden. The only graphs that have valid topological orderings are called directed acyclic graphs, that is grasses directed edges and no cycles.

So a natural question to ask is How do I verify that my graph does not contain a directed cycle? One method is to use Tarzan's strongly connected component algorithm which can detect these cycles. Another neat thing definitely worth mentioning is that every tree has a topological ordering. Since by definition trees do not have any cycles and easy way to find a topological ordering With trees as to iteratively, pick off the leaf nodes. It is like you're cherry picking from the bottom, it doesn't matter the order you do it. Once the root of a subtree has all grayed out children, then it becomes available.

This procedure continues until there are no more nodes left. So we know how it works with trees, but how about general directed a cyclic graphs? Well, the algorithm is also simple, just repeat the following steps. First finding unvisited node doesn't matter which from this node, do a depth first search exploring only reachable unvisited nodes on the recursive call back, add the current node to the top logical ordering in the reverse order. And that's it. Let's do An example and things will become much clearer.

Here's a directed acyclic graph. And then we want to find one of many topological orderings. For as the algorithm executes, I'll be keeping track of the call stack on the left hand side. And in case you're curious, I will also be posting the current topological ordering at the bottom of the screen. The first step is going to be to picking unvisited node, I'm going to pick node h arbitrarily. Now we do a depth first search outwards from HTML possible directions exploring where we can.

Let's go to node j. Now that I might know j, I'm going to keep exploring. And so let's go to m. Now that we're at m, there's nowhere left to go so we backtrack and add as well. last element to the top logical ordering still at j and we still need to explore L. Now we're at L. Now backtrack because there's nowhere left to go. Also backtrack, J and add it to the ordering. Notice that the stack frames getting popped off the call stack as I recurse.

Now we're at h, and we still need to visit node i. So now we're at node i and from node II, we try and visit node L. But then we figure out that note ELLs already visited so we don't go there, backtrack, backtrack, again, add AI to the ordering, and mark it as explored. And finally, we're back at each. As you saw, selecting a random unvisited node made us visit a subsection of the graph. We continue this process Until all nodes are visited. The next node I'm going to randomly pick is going to be node E. In the interest of time and simplicity, I will let the animation run and you can follow along.

Note that if you try and predict the next few values and topological ordering, he may not get the same values as me, because topological orderings are not unique. However, this does not mean you are incorrect. All right, I will let the animation play and try and follow along. So, that's it for That subsection of the graph. The next node I'm going to pick is going to be node C to visit. So we start node C and explore this subsection of the graph.

Now that all nodes are visited, we have a valid topological ordering at the bottom of the screen. So now that we understand how the algorithm works, what does the code actually look like? Here's some pseudocode. For top sort. Let's walk through it real quick. The first thing I do is I get the number of nodes from the graph, which I assume is passed in as an adjacency list from the function.

Then I declare an array called v short for visited, which tracks whether a note has been visited or not. The next array called orderings is the result that we'll be returning from this function. This is equivalent to the ordering of the bond. screen in the last slides associated with the orderings array is the index i, which tracks the insertion position of the next element in the topological ordering. As you have been seeing in the slides, we insert elements and backwards, which is why is starts at n minus one. Next, we're ready to enter a for loop to iterate over all the nodes in our graph.

The loop variable called at tracks the ID of the node we're currently processing. I then check if we're on the visited node, because those are the only ones we care about. Then I started that first search. Notice that before I do, I initialize an array called visited nodes, which I pass into the depth first search method to add nodes as we find them. Then after that's done after the depth search is finished, I look at the notes we found in our visited nodes array and then add them to the ordering. Now the last bit we need to look at is the depth first search method itself.

The first search method is very simple. All I do is I mark the node we're currently at to be visited. Then for each edge going outwards from the node we're at, I make sure the destination node is visited, then call the method again, but this time on the destination node. On the callback when the method returns, this is when we're stuck and need to backtrack. So this is where I add the current node to the visited nodes array, which is essentially the output for this method. Back to the top sorting method, now that we understand how to tops are algorithm works, there's a neat optimization we can do to prove the performance in terms of both time and space.

Notice that every time we enter the inner if statement block, we need to allocate memory for an array, that array gets filled with node IDs and then we iterate over them to place them inside the orderings array. But how about we just directly in search found node inside the ordering survey, instead of allocating memory and doing this additional work? Well, that's exactly what we're going to do. Here I got rid of the unnecessary array and modify the depth first search method to return the next valid insertion position in the orderings array. Now, we need to pass in the index i and the orderings array, so that it can be filled directly and find the depth first search method inside the new depth per search method. One thing that Change as I now we have a return value.

And we're passing in some additional variables. Notice that instead of adding the current node to the visit notes array, as we were doing before, that, we simply insert that note directly inside the orderings array. The last thing to do is to return i minus one, because the index of the current insertion position is no longer index i index i minus one. So that's it for the topological sort. As always, there's some source code for the topological sort algorithm, which can be found at my GitHub account github.com slash William fuzzers slash algorithms. Thank you very much for watching.

If you have any questions, just leave a comment. Please like this video and subscribe to my channel for more Computer Science and Mathematics videos. Guys, thank you very much and see you next time.