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

Question

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

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

有没有人看到上述算法存在缺陷？我不是图论方面的专家，但我认为我对递归和迭代有很好的把握，我相信这也是一样的。我想让它在功能上与递归算法等价。它应该维护第一个算法的所有属性，即使不需要这些属性。

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

Answer 1

两种算法都很好。第二种是从递归到基于堆栈的直接转换。所有的突变状态都存储在堆栈中。g在算法执行期间从不更改。

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

子节点将具有对其父节点的引用（如果它是根节点，则为null)，并且它的范围(child.d.child.f)包含在其父节点的范围内。

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

child.π = parent

这里是对原来第一个算法的重写：

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