So let me begin by telling you what a topological ordering of a directed
graph is. Essentially, it's an ordering of the vertices of the graph so that all of
the arcs, the directed edges of the graph, only go forward in the ordering. So, let
me encode an ordering by a labeling of the vertices with the numbers one through N.
This is just to encode the position of each vertex in this ordering. So formally
there's gonna be a function which takes vertices of G and maps things to integers
between one and N. Each of the numbers one through N should be taken on by exactly
one vertex. Here N is the number of vertices of G. So that's just the way to
encode an ordering and then here's really the important property that every directed
edge of G goes forward in the ordering. That is, if UV is a directed edge of the
directed graph G, then it should be that. The F value of the tail is less than the F
value of the head. That is, this directed edge has a higher F value as you, as you
traverse it in the correct direction. Let me give you an example just to make this
more clear. So suppose we have this very simple directed graph with four vertices.
Let me show you two different, totally legitimate topological
orderings of this graph. So the first thing you could do is you could label S1,
V2, W3 and T4. Another option would
be to label them the same way except you can swap the labels of, V and W. So if you
want you can label V three and W two. So again what these labeling meant to encode
is an ordering of the vertices. So the blue labeling you can think of as encoding
the ordering in which we put S first, then V, then W and then T. Whereas the green
labeling can be thought of as the same ordering of the nodes, except with W
coming before V. What's important is that the pattern of the edge is exactly the
same in both cases, and in particular, all of the edges go forward in this ordering.
So, in either case, we have S with edges from S to V and S to W. So that looks the
same way pictorially. Whichever order V and W are in. And then symmetrically,
there are edges from V and W to T. So you'll notice that no matter which order
we put V and W in, all four of these edges go forward in each of these orderings.
Now, if you're trying to put. V before S, it wouldn't work because the edge from S
to V would be going backward, if V preceded S. Similarly, if you put T
anywhere other than the final position, you would not have a topological ordering.
So in fact, these are the only two topological orderings of this directed
graph. I encourage you to convince yourself of that. Now who cares about
topological orderings? Well this is actually a, a very useful subroutine this
has been, come up in all kinds of applications. Really whenever you want a
sequence, a bunch of tasks, when there's precedents constraints amongst them. By
precedents constraints I mean one task has to finished before another. You can think,
for example, about the courses in some kind of undergraduate major, like
computer science major. Here the vertices are going to correspond to all of the
courses and there's a directed edge from course A to course B, if course A's a
prerequisite for course B, if you have to take it first. So then, of course, you'd
like to know a sequence in which you can take these courses so that you always take
a course after you've taken its prerequisites. And that's exactly what a
topological ordering will accomplish. So, it's reasonable to ask the question, when
does the directed graph have a topological ordering and when a graph does have such
an ordering, how do we get our grubby little hands on it? Well there's a very
clear, necessary condition for a graph to have a topological ordering, which is, it
had better be acyclic. Put differently, if a directed graph has a directed cycle
then there's certainly no way there's going to be a topological ordering. So, I
hope the reason for this is fairly clear. Consider any directed graph which does
have a directed cycle and consider any purported way of ordering the vertices.
Well now just traverse the edges of the cycle one by one. So you start somewhere
on the cycle. And if the first edge goes backwards, well you're already screwed.
You already know that this ordering is not topological; no way it just can go
backwards. So evidently the first edge of this cycle has to go forward, but now you
have to traverse the rest of the edges on this cycle, and eventually you come back
to where you started. So if you started out by going forward, at some point you
have to go backward. So that edge goes backward in the ordering, violating the
property of the topological ordering. That's true for every ordering, so
directed cycles exclude the possibility of topological orderings. Now the question
is, well what if you don't have a cycle? Is that a strong enough condition that
you're guaranteed to have a topological ordering. Is the only obstruction to
sequencing jobs without conflicts, the obvious one of having circular precedence
constraints? So it turns out that only is the answer yes as long as you don't have any
directed cycles, you're guaranteed a topological ordering, but we can even compute
one in linear time no less, via depth-first search. So before I show you this super
slick and super efficient reduction of computing topological orderings to depth
first search, let me first go over a pretty good but slightly less slick and slightly
less efficient solution to help build up your intuition about directed acyclic
graphs and their topological orderings. So for the straightforward solution we're
going to begin with a simple observation. Every directed acyclic graph has what I'm
gonna call a sink vertex. That is a vertex without any outgoing arcs. So in the four
node, directed acyclic graph we were exploring on the last slide, there is
exactly one source vertex and that's, excuse me, sink vertex, that's this right
most vertex here. Right? That has no outgoing arcs; the other three vertices
all have at least one outgoing arc. Now, why is it the case that a directed acyclic
graph has to have a sink vertex? Well suppose it didn't. Suppose it had no sink
vertex. That would mean every single vertex has at least one outgoing arc. So
what can we do if every vertex has one outgoing arc? Well we can start in an
arbitrary node. We know it's not a sink vertex cause we're assuming there aren't
any. So there's an outgoing arc so let's follow it. We get to some other node, by
assumption there's no sink vertex so this isn't a sink vertex. So there's an
outgoing arc. So let's follow it, we get to some other node. That also has an
outgoing arc, let's follow that, and so on. So we just keep following outgoing
arcs. And we do this as long as we want, because every vertex has at least one
outgoing arc. Well, there's a finite number of vertices. Right? This graph has,
say, N vertices. So, if we follow N arcs, we're gonna see N plus one vertices. So,
by the pigeon hold principle, we're gonna have to see a repeat. Right? So, if N plus
one vertices has only N distinct vertices, we're gonna see some vertex twice. So, for
example, maybe after I take the outgoing arc from this vertex. I get back to this
one that I saw previously. Well, what have we done? What happens when we get a
repeated vertex? By tracing these out going arcs and repeating a vertex we have
exhibited a directed cycle. And that's exactly what we're assuming doesn't exist.
We're talking about directed acyclic graphs. So, put differently, we just proved that a
vertex with no sink vertex has to have a directed cycle. So a directed acyclic
graph therefore has to have at least one sink vertex. So, here's how we use this
very simple observation now to compute a topological order of a directed acyclic graph.
Well let's do a little thought experiment. Suppose in fact this graph did have a
topological ordering. Let's think about the vertex that goes last in this topological
ordering. Remember, any arc which goes backward in the ordering is a violation.
So we have to avoid that. We have to make sure that every arc goes forward in the
ordering. Now, any vertex which has an outgoing arc, we better put somewhere
other than in the final position, all right? So the node that we put in the
final position, all of its arcs are gonna wind up to all of its outgoing arcs are
gonna wind up going backward in the topological ordering. There's nowhere else
they can go. This vertex is last. So in other words, if we're plan this to
successfully compute topological ordering, the only candidate vertices for that final
position in the ordering are the sink vertices, that's all that's gonna work. If
we put another non-sink vertex there we're toast, that's not gonna happen.
Fortunately, if it's directed acyclic we know there is a sink vertex, so at V, be a
sink vertex of G, if there's many sink vertices we pick one arbitrarily, we set
V's label to be the maximum possible. So there's N vertices, we're gonna put that
in the Nth position. And now we just recurse on the rest of the graph, which has
only N minus one vertices. So how would this work in the example on the right?
Well in the first iteration, or the first outermost recursive call, the only key, the only sink
vertex is this right's most circled in green. So there's four vertices, we're gonna
give that the label four. So then having labeled that four, we delete that vertex
and all the edges incident to it, and we recurse on what's left of the graph. So
that will be the left most three vertices plus the left most two edges. Now, this
graph has two sink vertices after we've deleted four and everything from it. So
both this top vertex and this bottom vertex are sinks in the residual graph. So
now in the next recursive call, we can choose either of those as our sink vertex.
Because we have two choices, that generates two topological orderings. Those
are exactly the ones we saw in the example. But if, for example, we choose
this one to be our sink vertex, then that gets the label three. Then we recurse
just on the northwestern most two edges. This vertex is the unique sink in that
graph. That gets the label two. And then we recurse on the one node graph and that
gets the, the label one. So why does this algorithm work? Well
there's, there's two quick observations we need. So first of all, we need to argue
that it makes sense, that in every iteration or in every recursive call, we
can indeed find a sink vertex that we can assign in the final position that's
still unfilled. And the reason for that, is just, if you take a directed acyclic
graph, and you delete one or more vertices from it, you're still gonna have a
directed acyclic graph. Alright, you can't create cycles by just getting rid of
stuff. You can only destroy cycles. And we started with no cycles. So through all the
intermediate recursive calls, we have no cycles. By our first observation, there's
always a sink. So the second thing we have to argue is that we really do produce a
topological ordering. So remember what that means. That means that for every edge
of the graph, it goes forward in the ordering. That is, the head of the arc is
given a position later than the tail of the arc. And this simply follows because
we always use sink vertices. So consider the vertex V, which is assigned
to the position I, this means then when we're down to a graph that has only I
vertices remaining, V is a sink vertex. So if I is, if V is a sink vertex for, when
only the first I vertices remain, what property does it have in the original
graph? Well it means all of the outgoing arcs that it has; have to go to vertices
that were already deleted and assigned higher positions. So for every vertex, by
the time it actually gets assigned a position, it's a sink. And it only has
incoming arcs from the as yet unassigned vertices. Its outgoing arcs all go
forward to vertices that were already assigned higher positions, and got deleted
previously from the graph. So now we have under our belt a pretty reasonable
solution for computing a topological ordering of a directed acyclic graph. In particular,
remember we observed that if a graph does have a directed cycle, then of course
there is no way there's a topological ordering. However you order the vertices, some edge of
the cycle is going to have to go backward. And the solution on the previous slide
shows that as long as you don't have a cycle, it guarantees a topological
ordering does indeed exist and in fact it's a constructive proof, a constructive
argument that gives an algorithm. What you do is you just keep plucking off sinks,
sink vertices one at a time and populating the ordering from right to left as you
keep peeling off these sinks. So that's a pretty good algorithm, it's not too slow.
And actually, if you implement it just so, you can even get it to run in linear time.
But I wanna conclude this video with an application of depth first search, which
is a very slick, very efficient computation of a topological ordering of a
directed acyclic graph. So we're just going to make two really quite minor
modifications to our previous depth first search subroutine. The first thing is we
have to embed it in a for loop just like we did with breadth first search when we
were computing the connected components of an undirected graph. That's because in
computing a topological ordering, we'd better give every single vertex a label,
we better look at every vertex at least once. So to do that, we'll just make sure
there's an outer for loop and then if we have multiple components, we'll just make
sure to invoke DFS as often as we need to. The second thing we'll do is we'll add a
little bit of bookkeeping and this will make sure that every node gets a label. And in
fact, these labels will define the topological order. So let's not forget the
code for depth first search. This is where you're given a graph G; in this case we're assuming
a directed acyclic graph and you're given a start vertex S. And what you do is you, as soon as
you get to S, you very aggressively start trying to explore its neighbors. Of
course, you don't visit any vertex you've already been to; you keep track of who
you've visited. And if you find any vertex that you haven't seen before, you
immediately start recursing on that node. So I said the first modification we need
is to embed this into an outer for loop to ensure that every single node gets labeled
so I'm gonna call that subroutine DFS-loop. It does not take a start vertex.
Initialization all nodes start out unexplored of course. And we're also going
to keep track of a global variable which I'll call current label. This is going to
be initialized to N and we're gonna count down each time we finish exploring a
new node. And these will be precisely the F values. These will be exactly the
positions of the vertices in the topological ordering that we output. In
the main, in the main loop we're gonna iterate over all of the nodes of the
graph. So, for example, we just do a scan through the node array. As usual, we don't
wanna do any work twice, so for a, if a vertex has already been explored in some
previous indication of DFS, we don't, we don't search from it. This should all be
familiar from our embedding a breadth-first search in a for loop when we
computed the connected components of an undirected graph, and if we get to a
vertex V of the graph that we haven't explored yet, then we just invoke DFS
in the graph with that vertex as the starting point. So, the final thing I need
to add is I need to tell you what the F values are with the actually assignments
of vertices to positions are. And as I foreshadowed we're going to use this global
current label variable and that will have us assign vertices to positions from
right to the left. Very much mimicking what was going on our recursive solution
where we plucked off sink vertices one at a time. So when's the right time to assign a
vertex its position? Well, it turns out the right time is when we've completely
finished with that vertex. So we're about to pop the recursive call from the stack
corresponding to that vertex. So after we've gone through the for loop of all
the edges outgoing from a given vertex, we set F of S equal to whatever the
current label is and then we decrement the current label. And that's it. That is the
entire algorithm. So, the claim is going to be that the F values produced, which
you'll notice, are going to be the integers between N through one, because
DFS will be called eventually once on every vertex and it will get some integer
assignment at the end. And everybody's gonna get a distinct value and the largest
one is N and the smallest one is one. The claim is that is a topological ordering.
Clearly this algorithm is just as blazingly fast as DFS itself, with just a
trivial amount of extra bookkeeping. Let's see how it works on our running example.
So let's just say we have this four node directed graph, which we're getting quite
used to. So this has four vertices. So we initialize the current label variable to be equal to four.
So let's say that, in the outer DFS loop, let's stay we start somewhere like the vertex V. So
notice, in this outer for loop, we wind up considering the vertices in a
totally arbitrary order. So let's say we first call DFS from this vertex V. So
what happens? Well, the only place you can go from V is to T and then at T there's
nowhere to go. So we recursively call DFS of T. There's no edges to go through.
We finish the for loop and so T is going to be assigned an F value equal to
the current label, which is N and here N is the number of vertices which is four.
So F of T is going to get. Sorry T is going to get the assignment the label
four. So then now we're done with T we back track back to V. We decrement the
current label as we finish up with T. We get to V, and now there's no more outgoing
arcs to explore, so its for loop is finished. So we're done with it, with
depth-first search. So it gets what's the new current label, which is now three. And
again having finished with V we decrement the current label which is now down to
two. So now we go back to the outer for loop. Maybe the next vertex we
consider is the vertex T. But we've already been there so don't bother to DFS
on T. Then maybe after that we tried it on S. So, maybe S is the third vertex that
the for loop considers. We haven't seen S yet so invoked DSF starting from vertex S.
From S there's two arcs to explore the one with V. V we've already seen nothing is
gonna happen with arc SV. But on the other hand the arc SW will cause us to recursively
call DFS on W. From W we try to look at the arc from W to T, but we've already
been to T so we don't do anything, that finishes up with W so depth-first search then
finishes up at the vertex W, W gets the assignment of the current label, so F of
W equals two. We decrement current label, now its value is one, now we
backtrack to S, we've already considered all of S's outgoing arcs so we're done
with S, it gets the current label which is one. And this is indeed one of the two
topological orderings of this graph that we exhibited, a couple slides ago. So
that's the full description of the algorithm and how it works on a concrete
example. Let's just discuss what are its key properties, its running time and its
correctness. So as far as the running time of this algorithm, the running time
is linear; it's exactly what you'd want it to be. And the reason the running time is
linear is for the usual reasons that these graph search algorithms have run a linear
time, you're explicitly keeping track of which nodes you've been to so that you
don't visit them twice. So you only do a constant amount of work for each of
the N nodes and each edge in a directed graph, you actually only look at each edge
once when you visit the tail of that edge. So you only do a constant amount of work
per edge as well. Of course the other key property is correctness. That is we need
to show that you all are guaranteed to get a topological ordering. So what does that
mean? That means every edge. Every arc travels forward in the ordering. So if UV
is in edge, then F of U, the label assigned to U, in this algorithm is
less than the label assigned to V. The proof of correctness splits into two cases
depending on which of the vertices U or V is visited first by depth-first search.
Because of our for loop, which iterates over all of the vertices of the graph
G, depth-first search is going to be invoked exactly once from each of the
vertices. Either U or V could be first, both are possible. So, first, let's assume
that U is visited by DFS before V. So then what happens? Well, remember what
depth-first search does when you invoke it from a node, it's going to find everything
findable from that node. So, if U is visited before V, that means V doesn't get
explored so it's a candidate for being discovered. Moreover, there's an arc
straight from U to V. So, certainly, DFS invoked at U is going to discover V.
Furthermore, the recursive call corresponding to the node V, is going to
finish, is going to get popped off the program stack before that of U. The
easiest way to see this is just to think about the recursive structure of
depth-first search. So when you call depth-first search from U, that recursive
call, that's gonna make further recursive calls to all of the relevant neighbors
including V and U's call is not gonna get popped off the stack until V's does
beforehand, that's because of the last in first out nature of a stack or of a recursive algorithm.
So, because V's recursive call finishes before that of U, that means it will be
assigned a larger label than U. Remember, the labels keep decreasing as
more and more recursive calls get popped off the stack. So that's exactly what we
wanted. Now, what's up in the second case, case two? So this is where V is visited
before U. And here's where we use the fact that the graph has no cycles. So
there's a direct arc from U to V. That means there cannot be any directed path
from V all the way back to U. That would create a directed cycle. Therefore, DFS,
invoked from V, is not going to discover U. There's no directed path from V to U,
again, if there was, there would be a directed cycle, so it doesn't find U at
all. So the recursive call of V, again, is going to get popped before U's is even
pushed onto the stack. So we're totally done with V before we even start to
consider U. So therefore for the same reasons, since V's recursive call finishes
first, its label is going to be larger, which is exactly what we wanted to prove.
So that concludes the first quite interesting application of depth-first
search. In the next video we'll look at an even more interesting one, which computes
the strongly connected components of a directed graph. This time we can't do it
in one depth for search, we'll need two.