Topological Sorting

A topological ordering of a directed graph G is a labeling of G's nodes such that:
(1) the f(v)'s are the set {1, 2, ... , n}
(2) if (u, v) in G, then f(u) < f(v)

Every directed acyclic graph has a sink vertex - a vertex that has no outgoing edges.

Here is a slick way to do a topological sorting with DFS:

DFS-loop(graph G)
    mark all nodes unexplored
    current_label = n (number of nodes, to keep track of ordering)
    for each v in G
        if v not yet explored
            DFS(G, v)

DFS(graph G, vertex start)
    mark start explored
    for every edge(start, v)
        if v not yet explored
            DFS(G, v)
    set f(start) = current_label
    current_label--

This will run in linear time because you do a constant amount of time at each node and traverse each edge only once since we keep track of which has or has not been explored.

To prove correctness, we need to show that if (u,v) is an edge, then f(u)<f(v).
Case 1: If u is visited by DFS before v, the recursive call corresponding to v will finish before that of u, so f(v)>f(u).
Case 2: If v is visited before u, there is no path (v, u) because otherwise it would be a directed cycle. Then, the recursive call of v gets popped before u even gets put on the stack. Thus f(u)<f(v).