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. GR
- 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 GR, whereas my textbook suggests that I begin by transposing G, do the first DFS on GR 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.