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

acyclicgraph, 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 edgewhich 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.

### Information

Author(s) | FranÃ§ois Aubry |

Deadline | No deadline |

Submission limit | No limitation |