visited 数组

一句话理解

visited 标记这个状态做过没有。

为什么要学

避免死循环和重复搜索。

讲解

图遍历 vis[u]。网格 vis[x][y]。状压 vis[s][u]。

要不要回溯，取决于状态是否允许再次出现在另一条路径。

例子

BFS 最短路 vis 永不撤销。回溯找方案常常撤销。

常见错误

• 该 vis 不 vis。
• BFS 里晚 vis 导致队列爆炸。