175iq's blog

By 175iq, history, 6 years ago, In English

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)

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If in original graph you have edges as sorted adjacency list, to find the transpose edges you just go int next from (|V|-1 to 0], and have a pointer to last edge in adjacency list. If it's same as pointer, you decrease the pointer, if not, you know it's a transpose edge.