algorithm - 在广度优先搜索和深度优先搜索中为什么访问的数组是全局初始化的

Question

Visited 数组是指我们记录一个节点是否被访问的数组。

Answer 1

树的遍历很容易，前提是树的格式正确。您不必跟踪是否有可能在无限循环中重复某些工作，因为只有一条路径可以到达每个节点。

但是对于图可能包含循环的广义图遍历，许多琐碎的算法在遇到循环时最终会无限循环。为了保证此类算法确实终止，我们通常希望在整个遍历过程中跟踪我们访问过哪些节点，而不是重新探索我们已经访问过的节点。

这就是 visited 集合的目的(无论是数组、集合等都无关紧要)。备选方案可能是每个节点都有一个访问标志，该标志可以在遍历之前取消设置并在遍历期间设置。这避免了对全局集合的需要，但施加了自己的限制(一次只能进行一次遍历)。

visited 集合不需要是“全局”¹，但确实需要在每个遍历的所有部分共享的公共(public)范围内。

---

¹如果它是“全局的”，那么在任何有意义的范围内，同样一次只能进行一次遍历。