[Graph Algo Series 3] Digraph: Topological and Kosaraju’s Algo

Ensure that you are familiar with the concepts in the series 1 and series 2 before diving into this article.

Topological Sort (DAG)

Definition: Given a directed acyclic graph (DAG), put the vertices in order such that all its directed edges point from a vertex earlier in the order to a vertex later in the order. E.g. pre-requisite classes.

Note how we can get the preorder, postorder and reverse postorder of nodes.

preOrder = new Queue<Integer>();
postOrder = new Queue<Integer>();
reversePostOrder = new Stack<Integer>();

private void dfs(Digraph G, int v) {
  preOrder.enqueue(v)

  // do something
  dfs(G, nextV)

  postOrder.enqueue(v);
  reversePostOrder.push(v);
}

Topological sort is the reverse postorder in a DAG.

Strong Connectivity (Kosaraju’s Algo)

Definition: two vertices are mutually reachable is considered ‘strongly connected’. It has the attribute of reflexive, symmetric and transitive.

We can use Kosaraju’s Algo to count number of strongly connected components in a graph:

• Given a digraph G, use DFS to compute the reverse post order ;
• Run a DFS on G based on the reverse post order, and all vertices reached are in a strong component.

int count = 0; // number of strongly-connected components
boolean[] marked marked = new boolean[G.V()]; // marked[v] = has vertex v been visited?
int[] id = new int[G.V()]; // id[v] = id of strong component containing v

for (int v : reversePostOrder) {
    if (!marked[v]) {
        dfs(G, v);
        count++; // Count for strongly connected component.
    }
}

private void dfs(Digraph G, int v) {
    marked[v] = true;
    id[v] = count;
    for (int w : G.adjacent(v)) {
        if (!marked[w]) dfs(G, w);
    }
}

Time complexity: time and space O(V+E), strong connectivity query O(1).

Reference: The textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne