OK, so now that we have looked at depth first search, we are going to talk about a cool application
of depth, first search, and this isn't like a practical application that I'm talking about for a specific
problem that you would solve or some type of project you would build.
This is a cool algorithm that uses depth first search that can be then in turn used for all kinds of
applications, and that is called topological sort.
So let's get right into it.
I have a graph right here.
And as you can see, there's a few things that you might recognize.
We have directed edges here.
And if you look more closely at the graph, you will notice that not only does it have directed edges,
but it does not have any cycles.
So you can't go something like this, you know, from this edge to here from this vertex two, this
vertex to this vertex back or anything that there's no loops here that you can see.
So this is what we refer to as a DAG for short, but that is directed a cyclic graph.
And it's actually required that we have a directed acyclic graph to perform topological sort.
So what is topological sort?
So it gives you a non unique and I'm stressing that because you will see that the ordering in which
I go through this and create the type of logical wording of the graph, a type of logical ordering.
I'm saying a liquid topological ordering because there can be multiple ordering.
It may not be the same as what you might get if you do this problem and start somewhere else, or it
just comes out different.
The point of it is that you're going to visit the nodes in depth, first search fashion and the final
ordering that you will have that you with a store in a container.
As you will see, I'll put a container down here for the walk through that I'm going to do.
It will not have any conflicts in that ordering.
If you start from left and go to the right of all the labeled vertices, which I will label in a moment,
you all of the vertices on the left, anything to the right means that that vertex to the left of it
basically has a directional edge going out to that direction.
So you could not.
You can go from left to right, but you couldn't traverse from right to left on those.
So it's basically the idea that you have to come from somewhere to get to a specific node and topological
sort ensures that it produces an ordering where you couldn't have something like, you know, you start
with this node and then afterwards, you know you, you visit this node, you can't visit this node
right here and tell this nodes are already visited because you notice that it basically you have to
come from this node to get to here.
You have to go from this node to this node to this node.
You can't let go here.
And visit this first without this already being visited.
And that's what topological sort will ensure that we have an ordering that respects rules like that.
So let's go ahead and walk through an example this time, I'm not going to have a stack over here,
but I'm going to have a little marker, a little smiley face that represents our stack and then we will
mark our visited nodes.
And down here on the bottom, I will build a topological ordering so you can think of it as like a container
that we're adding our topological ordering to.
And an important point is that I will be adding these vertices in reverse order and I will be adding
the vertices in the recursive process of the depth first search.
So it is a very simple algorithm now that you understand depth, first search.
So all we're really doing is we are performing depth first search multiple times, if necessary, on
the graph until we visited all the nodes.
And we are when we're doing the recursive process, when we're popping things off the stack, we will
be adding them from right to left in reverse order into a container, and that's all we're really doing.
So let's go ahead and get into it.
I'm going to start here at Vertex A, so I have this little smiley face.
That means we're going to add Vertex eight to the stack.
So it's on the stack right now.
Then I head over to see I add Vertex C to the stack.
But you notice there is nowhere I can go from C.
There's an incoming edge, but it doesn't go out.
There's no other outcome in edge.
There is no out coming edge from C.
So because of that, we are going to pop C off the stack.
I take the smiley face away.
It's no longer on the stack.
The last thing on the stack is a.
And I'm going to add it here on the right side to my topological ordering.
So then I can go to B from A we come back to air and we still have somewhere to go.
I'm going to push B to the stack.
From B. I'm going to head over to E!
I'm going to push E to the stack from E!
I'm going to head to G, I'm going to post G to the stack.
So we're just doing the same depth for a search here, you know, going deep.
I go to H.
I push h to the stack.
There's no outgoing edges from H.
I cannot get to anything, so I pop it off the stack.
Since I'm popping out of the stack, we're in our recursive process.
I'm going to add that popped up h to my container and we're going in reverse order.
Remember from right to left here.
So I'm pushing it to the front, not pushing it to the back of this container from G.
We can still go to F.
So let's go to F.
Let's add that to the stack from F we can go to.
So let's add it to the stack.
No outgoing edges from I as pop that off the stack.
Now we're back at F well, actually first, we want to add I to our container here since we purchased
off the stack.
Now that we're back at F, we noticed that F has outgoing edges, but we've visited all of these vertices,
so therefore we're going to pop f off the stack.
So the recursive version of this, you can think of us as going back to the previous stack frame now,
and we're going to put that in our container as well since we pop it.
Same thing with G already visited F and H, so we're going to pop that off and put it to our container.
Same thing with E!
The only outgoing edge was here to G and it's been visited, so pop it off added to the container.
Come back to be, you know, B has an outgoing edge to DX.
So let's go explore d add to the stack.
Can't go anywhere from DB besides this place that we've already visited here at E!
So pop it off the stack, add it to our container.
Come back to B.
B, we've already visited these two outgoing adjust to these practices.
So let's take that off the stack.
Put it in our container.
Go back to a and this is normally where we'd be wrapping up our depth first search.
But for this, this is where the end of this depth, first search process would would.
Stop.
So we've gone all the way through and came all the way back to where we started.
But we're actually still going to have to visit this, okay, because, you know, it's kind of like
a initial starting node and we start here a and had no way to get to K, so we'll do the same thing.
Pop this off the stack at it.
And now we're going to start at K.
So we start at K and we start the whole depth versus project process again.
Add K to the stack, but you notice that we've already visited B and E, which are these two outgoing
edges to these vertices from K?
Because of that, we're actually going to immediately then pop K off the stack.
And since we did it pop off the stack, we're going to add it to our container and now we are done and
we have our topological ordering down here.
And so I don't have these drawn is nodes, which if you check online, a lot of people will put, you
know, these topological ordering as nodes and with arrows, but you can imagine it here.
If I had circles around these, you could draw arrows kind of like this.
As all the edges that go out to their respective nodes, like goes to be in, I could go from K to be
like an arrow here and then K to E.
And if I keep doing that, if I go to a and then I like draw something to see and draw something to
be.
And then for B, I go to D and E and so on and so forth.
You will notice that all of the edges start from the left and go to the right.
There are no arrows for edges that will go to the left start.
You know, you're going to start, for example, here on H.
And go back this direction.
So all of the arrows, the outgoing edges will be going in the right direction, and that is actually
a way to really show that this isn't top of logically sorted order.
So that's a good thing to practice if you're doing some graphs on paper to better understand this.
The main thing that we're doing with this is I am going to have a project description for you where
you are going to take in some input and it's going to be in the form of a JSON file.
So JavaScript object notation and I will be describing what to do for the project.
But the goal is to use topological sort and since, you know, depth first search.
And this is a tiny little addition on to the depth of research that you've already seen the implementation
for, it should be pretty easy for you to modify it and create this topological sort.
As we said, we're just performing death for search, you know, multiple times if necessary and in
the recursive phase when we're popping off.
From the stack, we are adding in reverse order to a container, so that's the only difference.
I believe it is easily achievable for you.
So we are going over this concept for you to implement it in a project.
So what is this useful for?
Well, one of the biggest things is build dependencies for code, because we just talked about the fact
that the topological ordering is from the, you know, coming from Vertex that were dependencies for
the vertex that you're at.
So if you have some specific vertex, you must have had to come from certain ones unless it's an originating
vertex.
That way, the ordering basically is going to be based on those dependencies, those outgoing directed
edges.
So you can do the same thing for build dependencies for a code like if you need to build the code,
compile the code, but it needs it's dependent on certain libraries and things like that.
You know, that's a situation where topological sort could come in handy.
Also, scheduling jobs, you know, just scheduling tasks and things like that.
And even shortest path finding which you modify this topological saw algorithm a little bit.
Add some extra stuff and you can find the shortest path through one of these directed acyclic graphs
where you might have like weights on the graph, like numbers associated with it based on distances
and things like that.
So we won't be covering that, but definitely useful to look it up.
Once you've done this, I believe it would be an easy addition for you to do a shortest path finding
thing with your code.
And of course, there is even more stuff that you can use it for just because of the useful nature.
The time complexity is big, though, of the number of vertices plus the number of edges.
This is because the graph edges are directed and you're only going to end up looking at each edge in
each vertex once, even though once you implement the code, you might be like, Hey, it kind of looks
like I have a loop and then I have like another loop inside of it, kind of, you know?
So you might be thinking, Oh, this is going to be, you know, something squared or you're going to
multiply vertices times, edges or something like that.
But in fact, the time complexity should be vertices plus edges if it's implemented in a good way.
So with that, I will leave you to the project, I will be putting in a description and I will be going
over an implementation of the project the way that I implemented it.
So it's kind of a walk through in case you struggled with it.
I go through and explain everything, but before you look at that, definitely attempt the project on
your own.
That is the goal for you to figure stuff out and become a better programmer and understand how to put
these algorithms to use.
So with that, I will see you in the next lecture.