tur*_*oup 8 algorithm terminology tarjans-algorithm
我正在阅读以下链接中的代码http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt 我一直碰到“低链接”这个词，我没有知道这意味着什么。我知道这是一个相当菜鸟的问题，但有人可以向我解释一下吗？谢谢。
如链接文章中所述：
该算法还维护一个低链接编号，当第一次访问顶点时，该编号最初被分配与访问编号相同的值。
换句话说，低链路值最初等于节点在初始 DFS 期间的编号。如果是第一个访问的节点，则值为 0。如果是第二个节点，则为 1。第三个节点的值为 2，第四个值为 3，以此类推。
从那里，低链接值被更新，以便它跟踪给定节点碰巧在哪个 SCC。这个想法是，最初我们认为每个节点都在它自己的 SCC 中，但是如果我们发现两个不同的节点是在同一个 SCC 中，我们更新所有这些节点的低链接值，使它们都相同。
希望这可以帮助！
| 归档时间： |
|
| 查看次数： |
2437 次 |
| 最近记录： |