Low-link

定义 Definition

Low-link（也常写作 lowlink）在图论与算法中通常指“低链接值/回溯值”：在深度优先搜索（DFS）中，一个节点能够通过若干条树边与至多一条回边到达的、最小的发现时间（或最小的 DFS 序号）。它常用于求强连通分量（SCC）等算法（如 Tarjan 算法）。在其他语境里它也可能被当作字面组合（“低的链接/低连接度”），但最常见的专业含义如上。

发音 Pronunciation

/ˈloʊ.lɪŋk/

例句 Examples

If a node’s low-link equals its index, it may be the root of an SCC.
如果一个节点的 low-link 等于它的索引值，它可能就是某个强连通分量的根节点。

During DFS, we update the low-link value when we find a back edge to an earlier node on the stack.
在 DFS 过程中，当我们发现一条指向栈中更早节点的回边时，就会更新 low-link 值。

词源 Etymology

由 low（低的、最小的）+ link（连接、关联）组合而成，用来表达“能通过连接关系回溯到的最小位置/编号”。该术语在图算法语境中被固定下来，尤其与 Tarjan 的相关工作紧密关联。

相关词 Related Words

• Algorithm
• Back-edge
• Depth-first
• Edge
• Graph
• Index
• Node
• SCC
• Stack
• Tarjan

作品示例 Notable Works

• Robert Tarjan, Depth-First Search and Linear Graph Algorithms（1972）：提出并系统化了 DFS 相关的图算法思想，low-link（或 lowlink）概念常与其 SCC 方法一起出现。
• Thomas H. Cormen et al., Introduction to Algorithms（《算法导论》）：在强连通分量等章节讲解 Tarjan 类方法时，会讨论与 low-link/lowlink 等价的“可回溯到的最小编号/时间”概念。
• Robert Sedgewick & Kevin Wayne, Algorithms：在图算法与 DFS 的实现讲解中，常使用 lowlink/low-link 作为实现变量名或概念说明。