C++深搜时如何避免重复访问导致的死循环？

Question

在C++深度优先搜索（DFS）中，如何避免因重复访问节点而陷入死循环？这是实现DFS算法时常见的问题。解决方法通常是使用一个布尔类型的访问标记数组`visited[]`，其大小与节点数相同。在访问某个节点前，先检查该节点是否已被访问过。如果已访问，则跳过；否则，将其标记为已访问并继续搜索。例如，在图遍历中，初始化所有节点为未访问状态：`vector visited(n, false);`。当访问节点`i`时，执行`visited[i] = true;`。此外，递归调用时需确保正确传递访问标记，避免遗漏或错误重置。此方法可有效防止DFS陷入无限循环，同时保持算法的正确性和效率。注意，对于递归深度较大的情况，还需考虑栈溢出的风险并优化实现。

Answer 1

1. 初识DFS与重复访问问题

深度优先搜索（DFS）是一种常用的图遍历算法，广泛应用于路径查找、连通性检测等场景。然而，在实现DFS时，若不注意节点的访问状态管理，可能会导致算法陷入死循环。

例如，考虑一个无向图中存在环的情况。如果没有正确标记已访问节点，递归调用将不断返回到同一个节点，从而形成无限循环。

解决这一问题的核心思路是：在访问某个节点之前，先检查该节点是否已被访问过。

2. 使用布尔数组避免重复访问

为防止重复访问节点，通常会使用一个布尔类型的访问标记数组`visited[]`，其大小与节点数相同。以下是具体实现步骤：

1. 初始化所有节点为未访问状态：`vector visited(n, false);`
2. 在访问节点`i`时，执行`visited[i] = true;`
3. 在递归调用前，检查目标节点是否已被访问：如果`visited[target] == true`，则跳过；否则继续递归。

void dfs(int node, vector& visited, const vector>& adj) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adj);
        }
    }
}
    

3. 递归调用中的注意事项

在DFS的递归实现中，正确传递访问标记数组`visited[]`至关重要。以下是一些常见错误及解决方案：

• 错误重置访问标记：确保每次递归调用时，`visited[]`的状态不会被意外重置。
• 遗漏访问检查：在递归调用前必须检查目标节点的访问状态。

此外，递归深度较大的情况下，可能引发栈溢出问题。可以通过以下方法优化：

• 使用迭代代替递归。
• 调整编译器的栈大小限制。

4. 流程图示例

以下是DFS算法的流程图，展示了如何通过访问标记数组避免重复访问：

graph TD
            A[开始] --> B[选择起始节点]
            B --> C{节点已访问？}
            C --是--> D[跳过节点]
            C --否--> E[标记节点为已访问]
            E --> F[遍历相邻节点]
            F --> G{相邻节点已访问？}
            G --是--> H[跳过相邻节点]
            G --否--> I[递归调用DFS]
            I --> J[结束]

5. 实际应用案例

以一个简单的无向图为例，说明如何使用`visited[]`数组防止DFS陷入死循环：

节点编号	邻接节点
0	[1, 2]
1	[0, 3]
2	[0, 3]
3	[1, 2]

对于上述图结构，若不使用`visited[]`，DFS可能会在节点之间无限循环。引入访问标记后，可有效避免此类问题。