wallcrawler's blog

DOUBT In Kosaraju's and Sharir's algorithm For Finding STRONGLY CONNECTED COMPONENT!! HELP NEEDED!!
By wallcrawler, history, 6 years ago, In English

As given in cp-algorithms.com for SCC, that we need to reverse the graph after sorting the vertices in decreasing order of exit time for finding strongly connected component so that we do not jump out into another SCC.

But instead of reversing the graph and traversing it can't we just traverse the original graph with increasing order of exit time ??

Please Help!! Thanks in advanced :)

  • Vote: I like it
  • -3
  • Vote: I do not like it

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

No. Consider this case.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much, I was struggling for a while now, my thing reports just 1 !! :)

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Same question has been answered here https://cs.stackexchange.com/questions/19652/kosaraju-s-algorithm-why-transpose/22408#22408

→ Reply