sinha's blog

By sinha, history, 7 months 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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sinha (previous revision, new revision, compare).

»
7 months 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.