是否存在DFS的“官方”，甚至是任何正确的实施？

Question

在这个question DFS的伪代码提供：

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

但是，它有一个非常明显的细节 - 相同的节点可以 - 并且经常会 - 被推到堆栈两次!!!!!!

               1
               | \
               |  2
               | /
               3

按1

流行1

添加1到访问

按2,3

流行2

添加2到访问

推1再堆叠

...

...

当然，这不可能是正确的？

Answer 1

你说的是节点1将再次被推入堆栈。但这没关系：它在下一次传递中基本上会被忽略，因为它已被标记为“已访问”：

if (current is in visited):
    continue

或者，如果尚未访问该节点，则只能将该节点添加到堆栈中：

for each node v such that (current,v) is an edge:
    if (v is NOT in visited) s.push(v)

在实际实现中添加此检查并不是不太可能。但是代码是伪代码，并且这通常以非常通用的形式编写，其中为了紧凑性和通用性而省略这种“优化”或“改进”，只要该算法是正确的。在这里，差异并不影响正确性：在这两种情况下，那部分说

// do something with current

只会为每个节点执行一次。