Kosaraju's Algorithm vs Tarjan's Algorithm

Правка en2, от 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)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский 175iq 2019-03-19 00:51:36 57 Tiny change: 'e order ? ' -> 'e order ? (Basically reversal of graph without use of extra memory)'
en1 Английский 175iq 2019-03-19 00:50:13 454 Initial revision (published)