CODEWITHSUNDEEP
c++algorithmtreedirected-acyclic-graphstarjans-algorithm
priyanka
priyanka

Reputation: 1

Difficulty in understanding lowtime in Tarjan algorithm

I'm trying to understand the low time used in tarjan algorithm using this example given on GFG - tarjan alogorithm example. 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.

Here is the link for tarjan algorithm on GFG - Tarjan Algorithm GFG

Upvotes: 0

Views: 243

Answers (1)

Damir Tenishev
Damir Tenishev

Reputation: 3402

As it is stated in the Tarjan Algorithm GFG(https://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/)

“Low” value of a node tells the topmost reachable ancestor (with minimum possible Disc value) via the subtree of that node.

In your examples you can't go through C, D, A because they are not in the subtree of E.

Upvotes: 0

Related Questions