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 thefor
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 ofdfsVisit(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.