Tarjan的强连通分量算法中，lowlink是什么意思？

Question

9

我在阅读以下链接中的代码http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt时，不断遇到单词“low-link”，但我不知道它的含义。我知道这可能是一个初学者的问题，但请问有人能解释一下吗？谢谢。

- turtlesoup

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

正如链接文章中提到的那样：

该算法还维护了一个较低的链接数，当第一次访问顶点时，初始值与访问编号相同。

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

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

希望这可以帮助你！