使用堆栈进行深度优先搜索（特别是具有父级和时间戳属性的 CLRS）

Question

Cormen、Leiserson、Rivest 和 Stein (CLRS) 给出了（第 22.3 节）基于递归的 DFS 实现，它不仅将父数据

u.\pi

沿途添加到每个节点

u

，而且还添加时间戳字段

u.d

和

u.f

应该分别表示

u

的时间是第一次访问的时间，以及我们完全完成处理的时间

u

包括其所有邻居、它们的邻居等。该算法的运行时间为 O(|V| + |E|)。

DFS(G)
    for each vertex u in G.V
        u.color = WHITE
        u.parent = NIL
    time = 0
    for each vertext u in G.V
        if u.color == WHITE
            DFS-VISIT(G, u)

DFS-VISIT(G, u)
    time = time + 1
    u.d = time
    ui.color = GRAY
    for each v in G.Adj[u]
        if v.color == WHITE
            v.parent = u
            DFS-VISIT(G, v)
    u.color = BLACK
    time = time + 1
    u.f = time

练习 22.3-7 要求使用非递归算法来计算使用堆栈的 DFS。

我最初的反应是做类似this的事情，但是正如这个issue提到的，关于保持这个O(|V| + |E|)

的能力存在一些问题。

其他方法 here 和 here 显然是 O(|V| + |E|)，但不要以导致深度优先树的方式设置父属性（请参阅此 issue）。 （此外，第一个设置

v.f

的速度太快，即在

v

的邻居被探索之前。）

对 CLRS 可能有什么想法有什么猜测吗？

编辑：好的，我想我明白了如何通过使用堆栈字典以有效的方式跟踪下一个白色邻居，使第一种方法在 O(|V|+|E|) 中工作（参见评论这里）。 我想我仍然很好奇人们是否能想到更简单的解决方案。

Answer 1

用 Python 完成，以便我可以测试。

DFS

和

DFS_VISIT

只是原始版本的 Python 版本。

我的

DFS_VISIT_2

是后者的非递归替代品。我用生成器迭代器表示每次访问。它们不是递归调用，而是将要访问的节点返回到主循环，主循环为其创建访问并将其放入堆栈中。

其余代码是测试，生成相同的随机图两次，使用两种实现运行 DFS，并比较结果，即写入的所有节点属性。他们是平等的。

WHITE, GRAY, BLACK = 1, 2, 3
NIL = None

def DFS(G):
    for u in G.V:
        u.color = WHITE
        u.parent = NIL
    global time
    time = 0
    for u in G.V:
        if u.color == WHITE:
            DFS_VISIT(G, u)

def DFS_VISIT(G, u):
    global time
    time = time + 1
    u.d = time
    u.color = GRAY
    for v in G.Adj[u]:
        if v.color == WHITE:
            v.parent = u
            DFS_VISIT(G, v)
    u.color = BLACK
    time = time + 1
    u.f = time

def DFS_VISIT_2(G, u):
    def visit(u):
        global time
        time = time + 1
        u.d = time
        u.color = GRAY
        for v in G.Adj[u]:
            if v.color == WHITE:
                v.parent = u
                yield v
        u.color = BLACK
        time = time + 1
        u.f = time
    visits = [visit(u)]
    while visits:
        for child in visits[-1]:
            visits.append(visit(child))
            break
        else:
            visits.pop()

import random
class Graph:
    pass
class Node(int):
    pass
expect = None
for DFS_VISIT in DFS_VISIT, DFS_VISIT_2:
    random.seed(0)
    G = Graph()
    G.V = [Node(_) for _ in range(100)]
    G.Adj = {u: random.sample(G.V, 10) for u in G.V}
    DFS(G)
    result = [(u, u.color, u.parent, u.d, u.f) for u in G.V]
    if expect is None:
        expect = result
    else:
        print(result == expect)
        for node in result:
            print(node)

在线尝试！