algorithm - 使用堆栈的非递归深度优先搜索 (DFS)

Question

好的，这是我在 Stack Overflow 上发表的第一篇文章，我已经阅读了一段时间并且真的很欣赏这个网站。我希望这是可以接受的问题。因此，我一直在通读算法简介(Cormen。麻省理工学院出版社)，我一直在学习图形算法。我一直在非常详细地研究为广度和深度优先搜索制定的正式算法。

这是深度优先搜索的伪代码:

DFS(G)
-----------------------------------------------------------------------------------
1  for each vertex u ∈ G.V
2      u.color ← WHITE       // paint all vertices white; undiscovered
3      u.π ← NIL
4      time ← 0              // global variable, timestamps
5  for each vertex u ∈ G.V
6      if u.color = WHITE
7          DFS-VISIT(G,u)

DFS-VISIT(G, u)
-----------------------------------------------------------------------------------
1  u.color ← GRAY          // grey u; it is discovered
2  time ← time + 1 
3  u.d ← time
4  for each v ∈ G.Adj[u]   // explore edge (u,v)
5      if v.color == WHITE
6          v.π ← u
7          DFS-VISIT(G,v) 
8  u.color ← BLACK         // blacken u; it is finished
9  time ← time + 1
10 u.f ← time

该算法是递归的，它从多个源进行(将发现未连接图中的每个顶点)。它有几个属性，大多数语言特定的实现可能会遗漏。它区分顶点的 3 种不同“颜色”。它最初将它们全部涂成白色，然后当它们被“发现”(在 DFS-VISIT 中访问)时，它们被涂成灰色。 DFS-VISIT 算法运行一个循环，在当前顶点的邻接列表上递归地调用自身，并且仅当顶点没有更多边到任何白色节点时才将顶点涂成黑色。

还保留了每个顶点的另外两个属性 u.d 和 u.f 是顶点被发现时(涂成灰色)或顶点完成时(涂成黑色)的时间戳。第一次绘制节点时，它的时间戳为 1，每次绘制另一个节点(无论是灰色还是黑色)时，它都会递增到下一个整数值。 u.π 也被维护，它只是指向发现 u 的节点的指针。

Algorithm Non-Recursive-DFS(G)
-----------------------------------------------------------------------------------
1   for each vertex u ∈ G.V
2       u.color ← WHITE
3       u.π ← NIL
4   time = 0
5   for each vertex u ∈ G.V
6       if u.color = WHITE
7           u.color ← GRAY
8           time ← time + 1
9           u.d ← time
7           push(u, S)
8           while stack S not empty
9               u ← pop(S)
10              for each vertex v ∈ G.Adj[u]
11                  if v.color = WHITE
12                      v.color = GRAY
13                      time ← time + 1
14                      v.d ← time
15                      v.π ← u
16                      push(v, S)
17              u.color ← BLACK 
18              time ← time + 1
19              u.f ← time

* EDIT 10/31/12 * 令人尴尬的是，我的算法长期以来一直不正确，它在大多数情况下都有效，但不是全部。我刚刚得到了这个问题的热门问题徽章，我看到 Irfy 在他下面的回答中发现了问题，所以这就是功劳所在。我只是在这里为将来需要它的任何人修复它。

有没有人发现上述算法的缺陷？到目前为止，我不是图论方面的专家，但我认为我对递归和迭代有很好的掌握，我相信这应该是一样的。我希望使其在功能上等同于递归算法。它应该保留第一个算法的所有属性，即使不需要它们也是如此。

当我开始写它时，我认为我不会有一个三重循环，但结果就是这样。当我环顾谷歌时，我看到了其他迭代算法，它们只有一个双重嵌套循环，但是，它们似乎并没有从多个来源进行。 (即他们不会发现不连通图的每个顶点)

Answer 1

两种算法都很好。第二个是从递归到基于堆栈的直接转换。所有变异状态都存储在堆栈中。 G 在算法执行过程中永远不会改变。

算法将根据算法访问每个节点的顺序为每个断开连接的区域生成一个生成树。这些树将通过对父节点的引用 (u.π) 和线段树(u.d 和 u.f)来表示。

一个子节点将有一个对其父节点的引用(如果它是根节点则为 NULL)，以及它的范围(child.d .. child.f) 包含在它的父级范围内。

parent.d < child.d < child.f < parent.f

child.π = parent

---

编辑:我在翻译中发现了一个错误。您实际上并不是将当前状态插入堆栈，而是将 future 的方法参数插入堆栈。此外，您没有为弹出的节点着色 GRAY 并设置 f 字段。

这里是对原始第一个算法的重写:

algorithm Stack-DFS(G)
    for each vertex u ∈ G.V
        u.color ← WHITE
        u.π ← NIL
    time ← 0
    S ← empty stack
    for each vertex u ∈ G.V
        if u.color = WHITE
            # Start of DFS-VISIT
            step ← 1
            index ← 0
            loop unconditionally
                if step = 1
                    # Before the loop
                    u.color ← GRAY
                    time ← time + 1
                    u.d ← time
                    step ← 2
                if step = 2
                    # Start/continue looping
                    for each vertex v ∈ G.Adj[u]
                        i ← index of v
                        if i ≥ index and v.color = WHITE
                            v.π ← u
                            # Push current state
                            push((u, 2, i + 1), S)
                            # Update variables for new call
                            u = v
                            step ← 1
                            index ← 0
                            # Make the call
                            jump to start of unconditional loop
                    # No more adjacent white nodes
                    step ← 3
                if step = 3
                    # After the loop
                    u.color ← BLACK
                    time ← time + 1
                    u.right ← time
                    # Return
                    if S is empty
                        break unconditional loop
                    else
                        u, step, index ← pop(S)

可能有几个地方可以优化，但至少现在应该可以了。

结果:

Name   d    f   π
q      1   16   NULL
s      2    7   q
v      3    6   s
w      4    5   v
t      8   15   q
x      9   12   t
z     10   11   x
y     13   14   t
r     17   20   NULL
u     18   19   r