data structures - Order of steps in Kosaraju's algorithm -

the wikipedia summary of kosaraju-sharir algorithm follows:

let g directed graph , s empty stack.

• while s not contain vertices.
  • choose arbitrary vertex v not in s.
  • perform depth-first search starting @ v. each time depth-first search finishes expanding vertex u, push u onto s.
• reverse directions of arcs obtain transpose graph.
• while s nonempty:
  • pop top vertex v s.
  • perform depth-first search starting @ v in transpose graph.
  • the set of visited vertices give connected component containing v; record , remove these vertices graph g , stack s. equivalently, breadth-first search (bfs) can used instead of depth-first search.

but in textbook - sedgewick's algorithms (fourth edition) - describes steps of algorithm follows:

• given digraph g, compute reverse post-order of reverse digraph. g^r
• run standard dfs on g, consider unmarked vertices in order computed instead of standard numerial order
• the set of vertices...

the conclusion drawn in final step identical, operations performed in preceding - seems operations given in different orders: wikipedia tells me start doing dfs on g , then transposing it, doing second dfs on g^r, whereas textbook suggests begin transpose, first dfs on g^r , second on g.

my primary question is: understanding correctly, or misinterpreting 1 or other saying?

secondly: intuitively, seems though these operations transitive , therefore these 2 "different methods" in fact equivalent, , yield same final result. i've tested intuition on couple of digraphs , seems hold true - it?

thirdly: assuming is, there objective reason prefer 1 on other, or matter of preference?

imo 2 algorithms equivalent there slight difference. difference in order of sccs (strongly connected components) output them.

say have acyclic di-graph having sccs s1, s2, s3, s4 in order.

s1 -> s2 -> s3 -> s4 

algorithm 1 (wikipedia).

when build stack s, vertex v, vertices coming after v shall enter stack s before v, because carrying out dfs on forward graph.

now reverse graph:

r_s1 <- r_s2 <- r_s3 <- r_s4 

the first vertex popped stack s shall in r_s1. hence when perform dfs, first scc output shall r_s1.

algorithm 2 (book).

here first reverse graph:

r_s1 <- r_s2 <- r_s3 <- r_s4 

now when conduct dfs on vertex v, vertices coming before v (in original graph) shall ordered before v. also, since start order_index n , decrement order_index, vertices coming after v shall have lower topological ordering v.

original graph:

s1 -> s2 -> s3 -> s4 

the lowest ordered vertex shall in s4. hence first scc output graph shall s4 opposed r_s1 in first case.