Click here to Skip to main content
15,881,803 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I'm trying to understand the low time used in tarjan algorithm using the second example given on GFG Tarjan's Algorithm to find Strongly Connected Components - GeeksforGeeks[^]

What I have tried:

According to GFG the definition of lowtime is that the lowtime is the time which indicates for each node what is the topmost ancestor which can be reached directly from that node OR the topmost reachable ancestor (with minimum possible Discovery time value) via the subtree of that node. Now in the given example, low values of B, C, and D are 1 and of E, F, G are 3 and of H, I, J are 6.

But my doubt is why the low values of E,F,G is not 1, I mean we can reach from E to A through the path - E->F->G->C->A OR E->F->G->C->D->A, so the topmost ancestor of E should be A and not C and similarly for F and G, the low value of them should also be 1.

I know I'm wrong somewhere in understanding this algorithm, but I have watched many videos on youtube and have gone through many sites but still I'm unable to understand this. If someone has useful links for tarjan algorithm then please share here and also clarify about this example that how the lowtime of E is not 1.
Posted

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900