如何使用迭代版本的 DFS 检测有向图中的循环？

Question

在递归DFS，我们可以通过着色节点的检测周期WHITE，GRAY并BLACK为解释在这里。

如果GRAY在 DFS 搜索期间遇到节点，则存在循环。

我的问题是：当我标记节点作为GRAY和BLACK在DFS的这个版本的迭代？（来自维基百科）

    1  procedure DFS-iterative(G,v):
    2      let S be a stack
    3      S.push(v)
    4      while S is not empty
    5          v = S.pop()
    6          if v is not labeled as discovered:
    7              label v as discovered
    8              for all edges from v to w in G.adjacentEdges(v) do 
    9                  S.push(w)

Answer 1

一种选择是，如果您正在进入或退出信息，则将每个节点两次推送到堆栈中。当您从堆栈中弹出一个节点时，您会检查您是进入还是退出。如果输入颜色为灰色，则再次将其推入堆叠并前进到邻居。如果退出，只需将其着色为黑色。

这是一个简短的 Python 演示，它在一个简单的图形中检测循环：

from collections import defaultdict

WHITE = 0
GRAY = 1
BLACK = 2

EDGES = [(0, 1), (1, 2), (0, 2), (2, 3), (3, 0)]

ENTER = 0
EXIT = 1

def create_graph(edges):
    graph = defaultdict(list)
    for x, y in edges:
        graph[x].append(y)

    return graph

def dfs_iter(graph, start):
    state = {v: WHITE for v in graph}
    stack = [(ENTER, start)]

    while stack:
        act, v = stack.pop()

        if act == EXIT:
            print('Exit', v)
            state[v] = BLACK
        else:
            print('Enter', v)
            state[v] = GRAY
            stack.append((EXIT, v))
            for n in graph[v]:
                if state[n] == GRAY:
                    print('Found cycle at', n)
                elif state[n] == WHITE:
                    stack.append((ENTER, n))

graph = create_graph(EDGES)
dfs_iter(graph, 0)

输出：

Enter 0
Enter 2
Enter 3
Found cycle at 0
Exit 3
Exit 2
Enter 1
Exit 1
Exit 0

Answer 2

您可以通过不立即弹出堆栈元素来简单地做到这一点。对于每次迭代， dov = stack.peek()和 if vis White，将其标记为Grey并继续探索其邻居。

但是，如果v是灰色，则表示您v在堆栈中第二次遇到并完成了探索。标记它Black并继续循环。

修改后的代码如下所示：

procedure DFS-iterative(G,v):
    let S be a stack
    S.push(v)
    while S is not empty
        v = S.peek()
        if v is not labeled as Grey:
            label v as Grey
            for all edges from v to w in G.adjacentEdges(v) do
                if w is labeled White do
                    S.push(w)
                elif w is labeled Grey do
                    return False    # Cycle detected
                                    # if w is black, it's already explored so ignore
        elif v is labeled as Grey:
            S.pop()                 # Remove the stack element as it has been explored
            label v as Black

如果您使用一个visited列表来标记所有访问过的节点和另一个，recStack即跟踪当前正在探索的节点的列表，那么您可以做的是，而不是从堆栈中弹出元素，只需执行stack.peek(). 如果没有访问元素（这意味着你遇到该元素在堆栈中的第一次），就标志着它True在visited和recStack探索它的孩子。

但是，如果该peek()值已被访问，则意味着您正在结束对该节点的探索，因此只需将其弹出并recStack再次使其为 False。