8

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

4

1 回答 1

7

如链接文章中所述：

该算法还维护了一个低链接数，当一个顶点第一次被访问时，它最初被分配与访问数相同的值。

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

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

希望这可以帮助！

于 2012-06-28T22:55:05.637 回答