深度优先搜索中 visited 标记时机探索

30 6 月, 2024 752点热度 0人点赞 0条评论

0 前言

如果你经常涉及到搜索算法，那么一般对 visited 有一定了解。如果你知道 visited 的作用，却不知道什么时候是正确的进行 visited 标记的时机，这篇文章会给你帮助。

1 visited 概念

在涉及到图或者其他一些结构的搜索时，常常会涉及到节点的重复访问问题，而这个时候，我们常常都会使用 visited 概念来对已经访问过的节点进行标记，从而避免在搜索过程中重复访问同一个节点，避免无限循环或效率降低。

接下来我将从递归和迭代两个场景展示深度优先搜索标记时机的不同（这里以图为例）。

2 递归场景下的 visited 标记时机

DFS(v)
  在 v 上打 visited 标记
  for u in v 的相邻节点
    if u 没有打过 visited 标记 then
      DFS(u)
    end
  end
end

以上是递归方式的深度优先搜索的标准实现方式，可以看到，在递归函数开始时，即在进入一个新节点前，立即将该节点标记为已访问，后续便不会再对标记过的节点进行递归调用。

3 迭代场景下的 visited

DFS(v)
  在 v 上打 visited 标记
  v 入栈
  while 栈不为空
    u 出栈
    for w in u 的相邻节点
      if w 没有打过 visited 标记 then
        在 w 上打 visited 标记
        w 入栈
      end
    end
  end
end

以上是迭代方式的深度优先搜索的标准实现方式，值得注意的点是，节点不是在出栈的时候打上 visited 标记，而是在入栈的时候打上 visited 标记，这是初学者很容易混淆的点。

作为对比我们可以看看，如果是在出栈的时候进行 visited 标记，伪代码如下：

DFS(v)
  v 入栈
  while 栈不为空
    u 出栈
    在 u 上打 visited 标记
    for w in u 的相邻节点
      if w 没有打过 visited 标记 then
        w 入栈
      end
    end
  end
end

上述两种方法都能够正确地完成深度优先搜索。

第一种方法，因为先标记再入栈，确保了不会有一个节点被多次压入栈中，从而避免了重复访问同一节点。

第二种方法，如果图中存在环，则有可能会有多次将同一个节点压入栈中的情况，但由于每次出栈时都会检查节点是否已被访问，因此虽然可能有多次入栈操作，但不会导致重复处理（即不会再次访问已经标记为 visited 的节点）。

所以，第二种方式相比第一种方式，会存在重复的入栈操作的额外开销。