使用堆栈的非递归深度优先搜索 (DFS) [英] Non-recursive Depth-First Search (DFS) Using a Stack
问题描述
好的，这是我在 Stack Overflow 上的第一篇文章，我已经阅读了一段时间并且非常欣赏这个网站.我希望这是可以接受的问题.所以我一直在通读 Intro to Algorithms (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.
这是深度优先搜索的伪代码:
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.
还有每个顶点的另外两个属性 u.d 和 u.f 是顶点被发现(涂成灰色)或顶点完成(涂成黑色)的时间戳.第一次绘制节点时，它的时间戳为 1，并且每次绘制另一个节点时都会递增到下一个整数值(无论是灰色还是黑色).u.π 也被维护，它只是一个指向发现 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
* EDIT 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.
结果:
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屋！
