- Okay, now we're gonna do topological sorting.
This is our first graph algorithm proper.
Yeah, I know we've looked at a lot of tree algorithms,
but this is one that operates
on the more general class of graphs.
Although there are some restrictions.
So I'm gonna start with a hypothetical, Egbert and Edwina,
my dear friends, are going to take a vacation,
and there are some things that they need to do.
So trying to get organized, they jot down a list
of all the stuff that they think they need to do.
And they see it's a very daunting list.
So they've been taking a class on algorithms,
and they think they're very clever.
So they're going to build a graph of dependencies.
So what is that?
Well, let's take all these tasks that they need to perform,
and we'll assign a node to each task
and then Egbert and Edwina are going to draw an arrow
from each node to another node
when they think one node should precede another
in their list of things to do.
So they do all that, and you see there's purchase tickets
leads to get seat assignments.
And get seat assignments precedes check-in,
and pack bags precedes feed the fish
but this is kind of a rat's nest.
It's a mess.
And they're not quite sure how to use this information
in order to make a list of the things that they need to do
in the order that they need to do them.
So the first thing they decide to do
is get these words out of the way.
They realize that they have a labeled graph,
and so they can use those labels.
So they get them out of the way
so that they can get a clear picture of the graph.
And now we see node A is associated
with get seat assignments.
Node B is associated with make sure the oven is off
and things like that.
And then they puzzle over what to do.
What now? Okay.
Well, Edwina has the brilliant observation
that Node G here
has no arrows pointing into it.
It only has arrows going out of it.
And when they take a look at the graph,
when they take a look at it more carefully,
they realize that this is the only node in this graph
that has out arrows, but no in arrows.
So they realize that this means
that nothing precedes this particular step,
which is purchasing tickets.
So they
take G out of the graph and set it aside
and remove all the edges that were associated with it.
And then they take a look and say, well, gee, what's next?
And they see now there are two nodes
that have no edges going into them.
And so they decide they're gonna do the same thing.
They're gonna take one node out of the graph.
And so they pick one node, they pick D,
and they take that out of the graph and set it next to G,
and they delete all the edges.
So what's next?
Well, now there are four nodes that have no in edges.
They're A, B, K, and E all have edges going out of them,
but no edges going in.
So again, they realize that these are things
that anything that's preceded them is already removed
from the graph so they can pick any one of these.
So they pick A, and they remove that from the graph,
and they repeat this process.
So at the next step, E, B, and K have no in edges.
And so they pick one, K, and they remove it from the graph.
Then again, now they look, they see E and B
are the only two nodes with no in edges.
And so they pick one B, and they remove it from the graph.
Again, they remove E from the graph.
And now there's only one.
So that's easy.
They take I from the graph.
Again, there's only one, F.
Everything else has an in edge.
Now, J is the only one.
Now C is the only one with no in edges.
And we get down to the last two,
and you see how that's gonna work out.
So what they've produced,
they use this ordering here that we have at the bottom,
the order that they removed these nodes from the graph,
and they use that to reorder their list.
And now they have a list that tells them
what order they should perform all of these steps,
purchase tickets, pack bags, get the seat assignments,
feed the fish, make sure the oven is off, water the plants.
Now you can lock the front door.
Now that you've locked the front door,
you can leave the key with the neighbor.
Only then can you drive to the airport, park the car,
check in, and board the plane.
So this is what's called a topological sort.
And to be more formal about it,
topological sorting is we're given some graph G,
you produce a linear ordering of its nodes
such that every directed edge, AB,
from node A to node B, for each one of those edges,
A comes before B in the ordering.
Now it should probably come as no surprise
that you can do this with directed, acyclic graphs only,
the graph has to be directed because they're directed edges.
And you can't have a cycle because then there's this loop,
and there's no end to it.
And so there's no preceding a relationship.
Cycles break that kind of a relationship.
It's also important to note
that some directed acyclic graphs
have more than one topological sort.
So to go back to the example here earlier,
every time we had a choice of nodes
to remove from the graph,
that's a branch in the possibilities
of the topological sorts
that we could have produced for that graph.
So some directed acyclic graphs
will have one topological sort.
Some may have more than one topological sort,
but every directed acyclic graph
has at least one topological sort.
And there's a directed, acyclic graph.
We know it is even without examining it any further
because we've just performed a sort on it,
and it's worked okay.
Here's some simpler examples.
On the left, we have directed, acyclic graph,
and on the right, we have a graph that's directed,
but not acyclic.
We see it contains this cycle highlighted in yellow.
Now here's some pseudocode
for implementing topological sort.
And as you might expect, it's pretty simple.
We start with an empty list
to hold the topologically sorted nodes.
And we start with a list of all the nodes
with no incoming edges, all right?
In the first example, there was only one such node, G,
but there may be more than one.
And as long as that set is not empty,
we remove a node from that set.
If there's more than one, we can pick any one.
It doesn't matter.
We append that node to the list t
that holds the topologically sorted nodes.
And then for each node with an edge e from n to m,
we remove the edge from the graph
just as we saw in the previous example.
And if m has no incoming edges,
then we insert that into, oh, that's a mistake.
Let me fix that right now, into s.
If m has no incoming edges, then we insert m into that set
of all nodes with no incoming edges.
And this while loop will execute
until there's nothing left in s,
and if we get to this point and the graph still has edges,
then we know we've encountered a cycle,
and so we return an error.
Otherwise, we return t, this empty list,
to hold the topologically sorted nodes.
So with this smaller example, we start off,
and A is the only node that has no incoming edges,
so that's in set s.
Set t is empty.
I shouldn't call them sets. Those are vectors.
Bad instructor.
Okay, and then we remove A,
and we find that F now has no incoming edges.
And so we add F to s.
And then we take F, and we put it in t,
and we find that G has no incoming edges,
just like we did before.
And we've produced a topological sort.
Now, one thing that I think is really cool
about a topological sort is when you're done
if you were to redraw all of those edges back in it,
you remember, we, when we took the nodes out of the graph,
we didn't include the edges.
But if you draw the edges back in,
now all the edges, you'll notice,
are moving in the same direction.
We've produced a linear order,
and nothing is going backwards.
Everything is going forwards.
And so that's a neat property that we introduce
in the particular drawing of the graph
when we perform a topological sort.
And by the same token, this is the graph of Edwina
and, what was his name?
Egbert's vacation.
And this is the representation of it
given a topological sort.
And again, you'll see that all of the arrows
are moving in the forward direction.
So I think that's kind of cool.
And that's really all there is to topological sort.
What's the complexity?
Well, to process the entire graph,
we have to go through all the vertices and all the edges.
We have to remove the vertices one at a time.
And we have to remove all the edges
that are incident to the vertices that we remove,
or nodes that we remove.
And so the complexity in the worst case,
generally in fact, is big O of the cardinality of V
plus the cardinality of E.
And now you know how to do topological sorts. Super cool.
All right, that's it for now.