低鏈接在Tarjan的SCC算法中意味着什麼？

Question

我正在閱讀以下鏈接中的代碼http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt 我一直在碰到「低鏈接」這個詞，我不知道它的含義。 我知道這是一個相當白癡的問題，但有人可以向我解釋嗎？ 謝謝。

Answer 1

作爲鏈接的文章中提到：

該算法還保持了低鏈接數，當一個頂點參觀了 第一次是最初分配相同的值作爲訪問數 。

換句話說，低鏈接值最初等於節點在初始DFS期間的數目。如果它是訪問的第一個節點，則值爲0.如果它是第二個節點，則它將爲1.第三個節點的值爲2，第四個值爲3，等等。

從那裏，低鏈接值被更新以便跟蹤給定節點碰巧在哪個SCC中。這個想法是，最初我們認爲每個節點都在它自己的SCC中，但是如果我們發現兩個不同的節點在同一個SCC中，我們更新所有這些節點的低鏈接值，以便它們都是相同的。

希望這會有所幫助！