是否有 "official" 或任何正确的 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 将再次被压入堆栈。但这没关系：在接下来的pass中基本会被忽略，因为它已经被标记为"visited":

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)

您不太可能在实际实施中添加此检查。但是代码是伪代码，并且通常以非常通用的形式编写，为了简洁和通用，只要算法正确，就会省略这种 "optimization" 或 "improvement" 。在这里，差异不会影响正确性：在这两种情况下，那部分说

// do something with current

每个节点只会执行一次。