I was reading the code in the following link http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt I kept bumping into the word "low-link", and I have no idea what it means. I know this is a rather nooby question, but can someone explain it to me? Thanks.
What does lowlink mean in Tarjan's SCC algorithm?
Asked Answered
As mentioned in the linked article:
The algorithm also maintains a low-link number, which is initially assigned the same value as the visit number when a vertex is visited for the first time.
In other words, the low-link value is initially equal to which number the node has during the initial DFS. If it's the first node visited, the value will be 0. If it's the second node, it will be 1. The third node has value 2, the fourth value 3, etc.
From there, the low-link value is updated so that it tracks which SCC the given node happens to be in. The idea is that initially we consider each node to be in its own SCC, but then if we find that two different nodes are in the same SCC, we update the low-link values of all of these nodes so that they're all the same.
Hope this helps!
© 2022 - 2024 — McMap. All rights reserved.