Kahn’s Algorithm 与 DFS：如何找出有向图中参与环的节点？

2026-11-04数据小许

结论

要准确找出有向图中所有参与环的节点，可以使用强连通分量（SCC）算法，例如 Tarjan 或 Kosaraju。两者的时间复杂度都是 O(V + E)，其中 V 是节点数，E 是边数。

题目中的两种做法都要注意正确性：

Kahn’s Algorithm 结束后，剩余节点可能包含环下游的节点，不能将它们全部标记为参与环。
DFS 发现指向当前搜索路径的边时，可以确认存在环，但只标记这条边指向的节点，会漏掉环中的其他节点。

如果只需要判断是否存在环，Kahn’s Algorithm 和正确实现的 DFS 都可以在线性时间内完成。

为什么 Kahn’s Algorithm 的剩余节点不一定在环中？

考虑下面的有向图：

A → B
B → A
B → C

A 和 B 构成环。C 没有出边，因此不可能参与环。

三个节点的初始入度都大于 0，Kahn’s Algorithm 找不到入度为 0 的节点，最终会把 A、B、C 全部留下。

剩余入度大于 0，只说明节点还有来自剩余图的入边，不能证明它能沿有向路径回到自身。

完整执行 Kahn’s Algorithm 后，剩余节点包括环上的节点，以及从环出发能够到达的节点。因此，这种方法可以判断图中是否存在环，也可用于拓扑排序，但不能直接给出精确的环节点集合。

DFS 跟踪当前路径能解决什么？

有向图的 DFS 通常需要区分三种状态：尚未访问、位于当前递归路径中、已经搜索完成。

如果搜索到一条边 u → v，且 v 位于当前递归路径中，那么这条边与路径上从 v 到 u 的部分构成一个环。

例如：

A → B → C → A

发现 C → A 时，只标记 A 会漏掉 B 和 C。这个环涉及当前路径中从 A 到 C 的所有节点。

不过，仅标记每条这类回边对应的路径片段，仍不能保证找全所有环节点。某个节点还可能通过指向已搜索完成节点的边参与另一个环。要完整处理这些关系，需要额外维护信息；强连通分量算法就是解决这一问题的标准方法。

判断环时，必须检查目标节点是否仍在当前路径中。仅仅发现目标节点已经访问过，并不代表存在环。

用强连通分量准确识别环节点

强连通分量中的任意两个节点都可以相互到达。按照通常把自环也视为环的定义，可以使用以下规则：

分量包含至少两个节点：分量内所有节点都参与某个环。
分量只有一个节点：仅当该节点存在指向自身的边时，它才参与环。

第二条不能省略，因为不带自环的孤立节点也构成一个强连通分量。

Tarjan 算法可以在一次 DFS 中找出所有强连通分量。下面的伪代码展示了完整的判断流程，adj[u] 表示节点 u 的出边目标列表：

next_index = 0
stack = empty stack

for each vertex u:
    index[u] = UNVISITED
    on_stack[u] = false
    in_cycle[u] = false

function strongconnect(u):
    index[u] = next_index
    low[u] = next_index
    next_index = next_index + 1

    stack.push(u)
    on_stack[u] = true

    for each v in adj[u]:
        if index[v] == UNVISITED:
            strongconnect(v)
            low[u] = min(low[u], low[v])
        else if on_stack[v]:
            low[u] = min(low[u], index[v])

    if low[u] == index[u]:
        component = empty list
        repeat:
            v = stack.pop()
            on_stack[v] = false
            component.append(v)
        until v == u

        if size(component) > 1:
            for each v in component:
                in_cycle[v] = true
        else:
            in_cycle[u] = (u appears in adj[u])

for each vertex u:
    if index[u] == UNVISITED:
        strongconnect(u)

return in_cycle

实现时，Tarjan 的 on_stack 表示节点仍在等待归属强连通分量的栈中，不能直接用“当前递归路径中的节点集合”替换。节点的递归调用结束后，仍有可能留在这个栈中。

效率与实现注意事项

在邻接表表示下，Kahn’s Algorithm、用于判断有向环的 DFS，以及 Tarjan、Kosaraju 的时间复杂度都是 O(V + E)。选择方法时，首先要确认它能否返回所需结果；仅比较遍历次数，无法判断哪一种适合这个问题。

Tarjan 的辅助空间为 O(V)，不包含图本身。上面的单节点自环检查即使扫描该节点的邻接表，总时间复杂度仍为 O(V + E)。

实际实现时还需要注意：

从每个尚未访问的节点开始搜索，覆盖整个图。
对长链或很深的图，递归实现可能耗尽调用栈；可根据运行环境选择显式栈实现。
不要在每次 DFS 递归时复制整个路径集合，否则会增加时间和空间开销。
哪种方法更不容易出错取决于具体实现，不能仅凭算法名称下结论。对于这项需求，使用成熟的 SCC 实现通常更容易检查正确性。