Order of steps in Kosaraju-Sharir

Question

The Wikipedia summary of the Kosaraju-Sharir algorithm is as follows:

Let G be a directed graph and S be an empty stack.

• While S does not contain all vertices.
  • Choose an arbitrary vertex v not in S.
  • Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
• Reverse the directions of all arcs to obtain the transpose graph.
• While S is nonempty:
  • Pop the top vertex v from S.
  • Perform a depth-first search starting at v in the transpose graph.
  • The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

But in my textbook - Sedgewick's Algorithms (fourth edition) - it describes the steps of the algorithm as follows:

• Given a digraph G, compute the reverse post-order of its reverse digraph. G^R
• Run a standard DFS on G, but consider the unmarked vertices in the order just computed instead of the standard numerial order
• The set of all vertices...

The conclusion drawn in the third step is identical, as are the operations performed in the first two steps, but it seems that those two steps are given in opposite orders: Wikipedia tells me to start by doing a DFS on G and then transposing it, doing the second DFS on G^R, whereas my textbook suggests that I begin by transposing G, do the first DFS on G^R and the second on G.

My primary question is: Am I understanding this correctly, or am I misinterpreting what one or the other is saying?

Secondly: Intuitively, it seems as though these operations are transitive and therefore that these two "different methods" are in fact equivalent, and will always yield the same final result. I've tested this intuition on a couple of digraphs and it seems to hold true - but is it?

Thirdly: Assuming it is, is there any objective reason to prefer one over the other, or is it simply a matter of preference?

NOTE: As of now, this question is cross-posted on StackOverflow. I'm an established user there, so I know that cross-posting is generally frowned upon, but I've just joined this SE and am curious to gauge the response I get here relative to what I get there. I will delete one or the other after doing so. If you'd like me to do so immediately, please comment.

Answer 1

1. Yes, you are understanding this correctly.

2. The set of SCCs of a graph is uniquely determined. So if the algorithms were returning different sets, this would imply that one of them is incorrect. For the Wikipedia version a correctness proof is linked at the bottom of the article. If Sedgewick also gives a correctness proof of his algorithm, these two proofs together imply the property.

3. Reversing a graph twice will give you the original graph. Thus, if one algorithm performs especially well/bad on a certain graph, the other one will show that performance on the reversal of the graph in question. So neither algorithm will perform better in the general case.

The comment on SO that the WP version does use $O(n)$ extra space for the stack is not entirely correct: Sedgewick also has to store the order of traversal in some way, which wll also take $O(n)$ space (though possibly with a smaller hidden constant). Additionally, you can replace the stack with a different way of storing the order in the WP algorithm as well.