We are going to see that we can very easily compute a topological order of a graph using DFS.

As with most DFS derived algorithms, all we need to do is to reason about the DFS tree. For clarity we will add the relevant code again:

static void dfsVisit(int u) {
    state[u] = OPEN;
    for(int v : g[u]) {
        if(state[v] == UNV) {
            dfsVisit(v);
        } else if(state[v] == OPEN) {
            // (u, v) is a cycle edge
        }
    }
    state[u] = CLOSED;
}

We are going to argue that:

Theorem:

In an acyclic graph, when a node becomes \(CLOSED\) then all of its out-neighbours are already closed.

Proof:

Suppose that we are executing dfsVisit(u). Let's consider any out-neighbour \(v\) of \(u\) and see why at the end of the for loop, \(v\) must be \(CLOSED\). We consider 3 cases depending on the state of \(v\) when it was inspected in the loop:

1. \(v\) was \(CLOSED\): then it will also be closed at the end of the loop, there is nothing to prove;

2. \(v\) was \(UNV\): then we called dfsVisit(v) and at the end of that call, \(v\) became \(CLOSED\). Hence it will also be closed at the end of dfsVisit(u);

3. \(v\) was \(OPEN\): this means that \((u, v)\) is a cycle edge which is impossible since we assumed that the input graph was acyclic.

In short: in an acyclic graph a node always becomes \(CLOSED\) after all of its out-neighbours.

Recall that in a topological order, we want a node to be placed anywhere before all of its out-neighborus. This means that, the order in which the nodes are closed must be, if one exists, the reverse order of a topological order.

Therefore, we can compute a topological order of a graph by putting the nodes in a list when we close them. By what we've seen above we will get a topological order by reversing that list.

In our implementation we will use an array instead of a list and put the elements from the end to the start of the array so that we don't need to reverse it in the end. An alternative is to use a stack but we did not opt for this solution because in most applications we need those nodes in an array afterwards anyway so that we can access the i-th element of the order in constant time.

static final int UNV = 0, OPEN = 1, CLOSED = 2;
static LinkedList<Integer>[] g;
static int[] state;
static boolean foundCycle;

static int[] toposort; // toposort will have the node indexes in topological order
static int toposortIndex; // to keep track where to put the next node

static void toposort() {
    foundCycle = false;
    state = new int[g.length];
    toposort = new int[g.length];
    toposortIndex = g.length - 1;
    for(int u = 0; u < g.length; u++) {
        if(state[u] == UNV) {
            dfsVisit(u);
        }
    }
}

static void dfsVisit(int u) {
    state[u] = OPEN;
    for(int v : g[u]) {
        if(state[v] == UNV) {
            dfsVisit(v);
        } else if(state[v] == OPEN) {
            // (u, v) is a cycle edge, the graph contains a cycle
            foundCycle = true;
        }
    }
    // add u to the topological order
    // note that we start from the end since we want to reverse the closing order
    toposort[toposortIndex--] = u;
    state[u] = CLOSED;
}

At the end of the execution of toposort(), if \(foundCycle\) is \(false\) then \(toposort\) will contain the nodes of the graph in topological order.