Kosaraju's Algorithm vs Tarjan's Algorithm

Revision en2, by 175iq, 2019-03-19 00:51:36

By what factor is Kosaraju's algorithm for finding strongly connected component slower as compared to Tarjan's algorithm. It appears to me that the factor should be 3 as there are 2 dfs passes in Kosaraju's algorithm and we also have to transpose the graph once. Am I missing something ?

Also is there any way to find the tranpose graph without declaring a new graph and storing the edges in reverse order ? (Basically reversal of graph without use of extra memory)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English 175iq 2019-03-19 00:51:36 57 Tiny change: 'e order ? ' -> 'e order ? (Basically reversal of graph without use of extra memory)'
en1 English 175iq 2019-03-19 00:50:13 454 Initial revision (published)