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

好吧，这是我在 Stack Overflow 上的第一篇文章，我已经阅读了一段时间并且非常欣赏这个网站。我希望这是可以接受的问题。所以我一直在阅读《算法简介》（Cormen. MIT Press），并且我已经了解了图形算法。我一直在非常详细地研究为广度和深度优先搜索而设计的正式算法。

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

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

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

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

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

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

该算法将根据算法访问每个节点的顺序为每个断开连接的区域生成一棵生成树。树将通过对父节点的引用来表示（u.π），以及线段树（u.d and u.f).

子节点将拥有对其父节点的引用（或NULL如果它是根），以及它的范围（child.d .. child.f) 包含在其父级范围内。

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

child.π = parent

Edit:我发现翻译中有一个错误。您实际上并不是将当前状态推入堆栈，而是将未来的方法参数推入堆栈。此外，您没有为弹出的节点着色GRAY并设置f field.

这是最初的第一个算法的重写：

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)

可能有一些地方可以优化，但至少现在应该可以工作。

Result:

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