algorithm - Tarjan 的 SCC 算法中的 lowlink 是什么意思？

Question

我正在阅读以下链接中的代码 http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt我一直碰到“低链接”这个词，我不知道它是什么意思。我知道这是一个相当笨拙的问题，但有人可以向我解释一下吗？谢谢。

Answer 1

如链接文章中所述:

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.

换句话说，低链路值最初等于节点在初始DFS期间具有的数量。如果是访问的第一个节点，则值为0。如果是第二个节点，则值为1。第三个节点的值为2，第四个为3，以此类推。

从那里，低链路值被更新，以便它跟踪给定节点恰好在哪个 SCC 中。这个想法是，最初我们认为每个节点都在它自己的 SCC 中，但是如果我们发现两个不同的节点在同一个 SCC 中，我们更新所有这些节点的低链路值，使它们都相同。

希望这对您有所帮助!