How to Write Iterative Tarjan SCC Algorithm, Part II

In previous part, we talked about iterative DFS, where we use a stack named frontier to keep the visiting order. This time, we are going to look at the iterative topological sort and Karasoju SCC algorithm.

The key idea of my iterative topological sort is use another stack named head to track when we finish visiting all descendant vertex of the head vertex.

上一次，我们提到了迭代深度优先查找（DFS）——用一个叫frontier的栈来保持访问顺序。今天，我们将看到迭代拓扑排序以及Karasoju强连通算法。

今天的重点在于，我们会增加一个栈，名为head。当父节点的所有后代都访问过之后，应该满足head.peek() === frontier.peek()。

Recursive Topological Sort

In the beginning, we introduce the code of recursive topological sort:

    function topologicalSortRec(graph) {
      var n = graph.numberOfVertex,
      order = [],

      DFS= function(g, i) {
        // recursive search graph g,
        // from the initial node i
        (for x in g.getAdjacentVertex(i)) {
          if (not g.isVisited(x)) {
            DFS(g, x);
          }
        };

        order[i] = n--;
        graph.markVisited(i);
      };

      (for 1 <= i <= n) {
        if (not graph.isVisited(i)) {
          DFS(graph, i);
        }
      }

      return order;
    }

As we notice, we get the topological order from recursive DFS. The proof of correctness will be found at Wikipedia or online course Algorithms: Design and Analysis, Part 1

Call Stack

Take a directed graph represented by adjacency list below for instance.

1: [2, 4] 2: 3 3: [5] 4: [3, 5]

(Please draw this simple graph on the paper to help understand. 1: [2, 4] means there are only two edges from vertex 1, that are 1 → 2 and 1 → 4.)

Here is the call stack of recursive topological sort. In each loop at current v, we list its parent vertex in column titled P. If all of descendant vertex of v which we list in column titled v.c() have been visited, we set the order(v).

Inspiration

According to Part Zero, we add frontier to call stack table as below.

If we look into the frontier and the time when descendant vertex array is empty, we may notice the top of frontier is the vertex we visit currently.

Stack Head

So we introduce a stack named head to track the time when we finish visiting all descendant vertex of the head vertex (current v).

    function iterTopologicalSort(graph) {
      var frontier = new Stack(),
          head = new Stack(),
          n = graph.numberOfVertex,
          order = [];

      frontier.push(1);
        while (not frontier.isEmpty()) {
          current = frontier.peek();
          if (current === head.peek() /*head may be empty here*/) {
              // we hit the time to set order
              frontier.pop();
              head.pop();
              order[current] = n--;
              graph.markVisited(current);
          } else {
              // current is just a child of some v
              head.push(current);
              (for x in graph.getAdjacentVertex(current)) {
                if (not graph.isVisited(x)) {
                  frontier.push(x);
                }
              };  // end for
          } // end else
        } // end while
    }

Running the iterative code, we update the stack table:

As we see, The time of finishing visit all descendant of current v, and to set order(current) is when peek() eqauls, i.e. head.peek() == frontier.peek().

Attention

• Empty Head. At line 10, head.peek() may throw an exception if head.isEmpty(). We can check it before each peek(), or we can push -1 (whatever bottom item) to make sure head is always contains item(s) before frontier.isEmpty().
• Vertex Status. Same issue may be occurred similarly as in iterative DFS we mentioned in last part. (see issue #20)

Kosaraju SCC

Kosaraju SCC algorithm, which runs DFS twice, finds some kind of visiting order in the first DFS. So we can find topological sort order as in the first DFS, then use the order for the second DFS.

Running Time

Roughly speaking, the running time of iterarive topological sort is same as time of DFS. The time of Kosaraju SCC which runs DFS twice, is still $O(m+n)$.

Next

See code on details in graph.search.js of Algo.js. And next post, I am going to explain iterative Tarjan SCC algorithm, which cost me a few time.