用于有向图上循环检测的迭代深度优先搜索

Question

我发现这个伪代码 维基百科, ，看起来非常优雅和直观：

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

我正在尝试使用 3 个标记（未访问、已访问、已处理）为此编写一个迭代版本，但是缺少尾递归确实让我很困扰。

我应该如何处理这个问题？

Answer 1

使用与递归算法的相同逻辑，我在堆栈上添加了一个生成的逻辑值，它跟踪最后后代目前处理的位置。

这是算法的“回溯”步骤所必需的。

from typing import List

UNDISCOVERED = -1
DISCOVERED = 0
PROCESSED = 1


def is_acyclic(graph: List[list], vertex_count: int) -> bool:
    state = [UNDISCOVERED] * vertex_count
    for vertex in range(vertex_count):
        if not dfs(graph, vertex, state):
            return False

    return True


def dfs(graph: List[list], v: int, state: list) -> bool:
    stack = [(v, 0)]
    while stack:
        curr, pos = stack[-1]
        if state[curr] == PROCESSED:
            stack.pop()
            continue
        if state[curr] == DISCOVERED and pos == 0:
            return False
        if pos == 0:
            state[curr] = DISCOVERED

        for i in range(pos, len(graph[curr])):
            stack[-1] = curr, pos + 1
            descendant = graph[curr][i]
            stack.append((descendant, 0))
            break
        else:
            state[curr] = PROCESSED

    return True

.

Answer 2

例如，您可以向节点添加“颜色”，类似于 CLRS 中递归 DFS 的方法。当您实例化每个节点（假设它们是对象）时，放置一个 颜色 场使得每个节点最初都有 node.color $\x左箭头{}$ 白色的.

以下是你的伪代码 修改的 我相信会有所帮助：

    L ← Empty list of all nodes, where node.color ← black (once placed here)
    while exists nodes such that node.color is white do
    select a node n such that n.color is white
    visit(n)

function visit(node n)
    if n.color is black then:
        return
    if n.color is gray then:
        stop   (back edge is found indicates cycle exists)

    mark n.color as gray

    for each node m with an edge from n to m do
        visit(m)

    mark n.color as black
    add n to head of L

这个想法是所有“未访问”的节点开始颜色为“白色”。然后，当我们遇到一个节点时，我们会访问它并在探索它时将其着色为“灰色”。当我们完成对这个节点的探索后，我们将其着色为“黑色”。我们只在“白色”颜色的节点上调用 DFS。

另外关于实现，除了堆栈之外，您还可以使 L 一个集合，只需检查大小（因为您知道只有不同的节点会添加到该集合中），一旦大小等于节点数，您就知道您已经访问了图形的所有节点，但作为如果你最终使用着色，就会出现没有节点的情况， n 这样 n.color == white.