Tarjan的SCC算法中的lowlink是什么意思?



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

如链接文章中所述:

该算法还维护一个低链接数,该号码最初是 为 第一次。

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

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

希望这有帮助!

最新更新