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.


Mark this section as read?

Information

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

Sign in