If you have a cycle,
there's no way that you're going to be able to solve the problem.
In fact a simpler graph processing
problem is just to find out if a graph has a cycle.
We'll talk about that in a second but let's do topological sort first, so
we know that the graph has no cycles.
It's a directed acyclic graph, and what we want to do is,
find a way to redraw the DAG so that all the edges point upwards and
give a bottom to top order too, so that all the edges are pointing upwards.
That's called a topological order of the graph.
And that'll give in this case an order in which maybe you could take the courses or
perform the manufacturing process or whatever else.
So that's the problem.
So how are we going to solve it, well we're going to use DFS.
In fact one of the lessons for particularly for
digraph processing is DFS is going to provide a way to solve it,
and might be hard to find a different way.
So, let's look at a demo of topological sort, and
all it is is just run DFS, but there's a particular
point at which we want to take the vertices out, or
to get the order, and that's called reverse DFS postorder.
So let's look at how that works.