非递归深度优先搜索（DFS）使用堆栈 [英] Non-recursive Depth-First Search (DFS) Using a Stack

问题描述

好的，这是我在Stack Overflow上的第一篇文章，我一直在阅读一段时间，真的很欣赏这个网站。我希望这是可以接受的要求。所以我一直在阅读算法入门（Cormen。MIT Press），我一直都在使用图算法。我一直在研究正式的算法，为广度和深度首先搜索细节非常详细。

Ok this is my first post on Stack Overflow I have been reading for a little while and really admire the site. I am hoping this is something that will be acceptable to ask. So I have been reading through Intro to Algorithms (Cormen. MIT Press) all the way through and I am up to the graph algorithms. I have been studying the formal algorithms laid out for breadth and depth first search in very fine detail.

以下是深度优先搜索的伪代码： p>

Here is the psuedo-code given for depth-first search:

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算法在当前顶点的邻接列表上递归地调用自身，并且只在顶点没有更多边缘时才绘制黑色。

This algorithm is recursive and it proceeds from multiple sources (will discovered every vertex in unconnected graph). It has several properties that most language specific implementations might leave out. It distinguishes between 3 different 'colors' of vertices. It initially paints all of them white, then when they are 'discovered' (visited in DFS-VISIT) they are then painted gray. The DFS-VISIT algorithm runs a loop recursively calling itself on the adjacency list of the current vertex and only paints a vertex black when it has no more edges to any white node.

每个顶点的其他两个属性都保持不变，uf是顶点被发现（绘成灰色）或顶点完成（绘成黑色）时的时间戳。第一次绘制一个节点时，它的时间标记为1，并且每当另一个绘制时（无论是灰色还是黑色），它都会增加到下一个整数值。 u.π也被维护，它只是一个指向发现你的节点的指针。

Also two other attributes of each vertex are maintained u.d and u.f are the time stamps to when the vertex was discovered (painted gray) or when a vertex is finished (painted black). The first time a node is painted it has a time stamp of one and it is incremented to the next integer value for each time another is painted (whether it be grey or black). u.π is also maintained which is just a pointer to the node from which u was discovered.

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

*编辑10/31/12 * 这让我很尴尬，因为我的算法长期以来一直不正确，它在大多数情况下都能正常工作，但不是全部。我刚刚得到了一个问题的流行问题徽章，我看到Irfy在他的回答中发现了问题，所以这就是信用所在。我只是在这里为任何需要这个的人修复它。

* EDIT 10/31/12 * This is embarrassing that my algorithm has been incorrect for so long, it would work in most cases, but not all. I just got a popular question badge for the question and I saw where Irfy had spotted the problem in his answer below, so that is where the credit goes. I am just fixing it here for anyone that needs this in the future.

有没有人看到上述算法存在缺陷？我目前还没有图论的专家，但我认为我对递归和迭代有很好的把握，我相信这应该是一样的。我正在寻找使其功能等价于递归算法。它应该保留第一个算法的所有属性，即使它们不是必需的。

Does anyone see a flaw with the above algorithm? I am by far no expert on graph theory, but I think I have a pretty good grasp on recursion and iteration and I believe this should work the same. I am looking to make it functionally equivalent to the recursive algorithm. It should maintain all the attributes of the first algorithm even if they are not needed.

当我开始写它时，我不认为我会有一个三重循环，但那是事实证明。我看过其他迭代算法，当我环顾Google，只有一个双重嵌套的循环，但是，他们似乎并没有从多个来源进行。 （即它们不会发现每个不连接的图的顶点）

When I began writing it I did not think I would have a triply loops but that's the way it turned out. I have seen other iterative algorithms when I looked around Google that only have a doubly nested loop, however, they do not appear to proceed from multiple sources. (i.e. they will not discover every vertex of unconnected graph)

推荐答案

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

Both algorithms are fine. The second one is a direct translation from recursive to stack-based. All mutating state are stored in the stack. G never changes during the execution of the algorithm.

算法会为每个断开的区域生成一棵生成树，基于算法访问每个节点的顺序。这些树将用参考父节点（u.π）和段树（ ud >和 uf ）。

The algorithms will produce a spanning tree for each disconnected region, based on the order the algorithm visited each node. The trees will be represented both with references to the parent-nodes (u.π), and as segment trees (u.d and u.f).

子对象的父节点（或 NULL ，如果它是一个根），以及包含在其父范围内的范围（ child.d .. child.f ） 。

A child will have a reference to its parent node (or NULL if it is a root), as well as having it's range (child.d .. child.f) contained within it's parent's range.

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

child.π = parent

---

编辑：我在翻译中发现错误。你实际上并没有将当前状态推入堆栈，而是未来的方法论证。另外，你没有着色弹出的节点 GRAY 并设置 f 字段。

---

I found a mistake in the translation. You are not actually pushing the current state into the stack, but a future method argument. In addition, you are not coloring the popped nodes GRAY and setting the f field.

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

Here is a rewrite of the original first algorithm:

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)

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

There is probably a few places that could be optimized, but should at least work now.

结果：

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

这篇关于非递归深度优先搜索（DFS）使用堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！