<p>使用<em>递归</em>dfs,很容易看到给定顶点何时“完成”(即,当我们访问了dfs树中的所有子节点时)。完成时间可以在递归调用返回后立即计算。<br/>
然而,对于迭代的dfs,这并不容易。现在,我们使用while循环迭代处理队列,我们丢失了一些与函数调用相关的嵌套结构。或者更准确地说,我们不知道回溯何时发生。</em>不幸的是,如果不向顶点堆栈添加一些额外的信息,就无法知道回溯何时发生。在</p>
<p>将完成时间添加到dfs实施中的最快方法如下:</p>
<pre><code>##### iterative dfs (with finish times) ####
path = []
time = 0
finish_time_dic = {}
for i in range(max(max(ori_data)),0,-1):
start = i
q = [start]
while q:
v = q.pop(0)
if v not in path:
path.append(v)
q = [v] + q
for w in revscc_dic[v]:
if w not in path: q = [w] + q
else:
if v not in finish_time_dic:
finish_time_dic[v] = time
time += 1
print path
print finish_time_dic
</code></pre>
<p>这里使用的技巧是,当我们从堆栈中弹出<code>v</code>时,如果这是我们第一次看到它,那么我们将它再次添加回堆栈</em>。这是通过使用:<code>q = [v] + q</code>完成的。我们必须在</em>之前将<code>v</code>推送到堆栈的<em>上(我们在</em>之前编写代码,将<code>v</code><em>推送到</em>的for循环之前推送{<cd1>}的邻居),否则这个技巧就行不通了。最终,我们将再次从堆栈中弹出<code>v</code>,再次<em>。此时,<em>v已完成</em>!我们之前已经看过<code>v</code>,因此,我们进入else情况并计算一个新的完成时间。在</p>
<p>对于提供的图形,<code>finish_time_dic</code>给出了正确的完成时间:</p>
^{pr2}$
<p>注意,这个dfs算法(经过finishing times修改)<em>仍然具有</em>O(V+E)<em>的复杂度</em>,尽管我们将图的每个节点压入堆栈<em>两次</em>。然而,还有更优雅的解决方案。
我建议阅读Magnus Lie Hetland的《Python算法:掌握Python语言的基本算法》(ISBN:14302323749781430232377)的第5章。问题5-6和5-7(第122页)准确地描述了你的问题。作者回答了这些问题,并给出了另一种解决办法。在</p>
<p>问题:</p>
<blockquote>
<p>5-6 In recursive DFS, backtracking occurs when you return from one of the recursive calls. But where has the backtracking gone in the iterative version?</p>
<p>5-7. Write a nonrecursive version of DFS that can deal determine finish-times. </p>
</blockquote>
<p>答案:</p>
<blockquote>
<p>5-6 It’s not really represented at all in the iterative version. It just implicitly occurs once you’ve popped off all your “traversal descendants” from the stack. </p>
<p>5-7 As explained in Exercise 5-6, there is no point in the code where backtracking occurs in the iterative DFS, so we can’t just set the finish time at some specific place (like in the recursive one). Instead, we’d need to add a marker to the stack. For example, instead of adding the neighbors of u to the stack, we could add edges of the form <code>(u, v)</code>, and before all of them, we’d push <code>(u, None)</code>, indicating the backtracking point for <code>u</code>. </p>
</blockquote>