### Information

 Author(s) François Aubry Deadline No deadline Submission limit No limitation

## Graphs - DFS: topological order

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.