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 1,

because DFS will be called eventually once on every vertex, and

it will get some integer assignment at the end.

And everybody is going to get a distinct value, and the largest one is n and

the smallest one is 1.

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.

Lets see how it works on our running example.

So lets just say we have this four node directed graph that we're getting

quite used to.

So this has four vertices, so

we initialize the current label variable to be equal to 4.

So let's say that in the outer DFS loop,

let's say 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 at 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 4.

So f(t) is going to get, so our t is going to get the assignment, the label 4.

So then now we're done with t, we backtrack 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 for loops finish.

So we're done with it in depth-first search.

So it gets what's the new current label, which is now 3, and again,

having finished with v, we decrement the current label, which is now down to 2.

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 we don't bother to DFS on t.

And then maybe after that, we try it on s.

So maybe s is the third vertex that the for loop considers.

We haven't seen s yet, so we invoke DFS, starting from the vertex s.

From s, there's two arcs to explore, the one with v, v we've already seen, so

nothing's going to happen with the 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(w) = 2.

We decrement current label, now its value is 1.

Now we backtrack to s, so we've already considered all of s's outgoing arcs, so

we're done with s.

It gets the current label, which is 1.

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 in 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 search algorithms run in 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 are guaranteed to get a topological ordering.

So what does that mean?

That means every arc travels forward in the ordering.

So if (u,v) is an edge, then f(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 was 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 isn't getting explored, so

it's a candidate for being discovered.

Moreover, there's a 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, it's 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 going to

make further recursive calls to all of the relevant neighbors including v, and

u's call is not going to 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.