深度优先搜索

1. 算法思想

DFS 通过递归或栈来实现，其过程如下：

从起始节点开始，访问该节点并标记为已访问。
选择一个未访问的邻接节点，继续深入探索。
如果当前节点没有未访问的邻接节点，则回溯到上一个节点。
重复上述过程，直到所有节点都被访问。

2. 算法实现

DFS 可以通过递归或栈来实现。

递归实现

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {// 标记当前节点为已访问visited[node] = true;cout << node << " "; // 输出访问的节点// 遍历所有邻接节点for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfs(neighbor, graph, visited); // 递归访问}}
}

栈实现

void dfs(int start, vector<vector<int>>& graph) {vector<bool> visited(graph.size(), false);stack<int> stk;// 将起始节点入栈stk.push(start);visited[start] = true;while (!stk.empty()) {int node = stk.top();stk.pop();cout << node << " "; // 输出访问的节点// 遍历所有邻接节点for (int neighbor : graph[node]) {if (!visited[neighbor]) {visited[neighbor] = true;stk.push(neighbor); // 将未访问的邻接节点入栈}}}
}

3. 算法步骤

初始化：
- 创建一个标记数组 visited，用于记录节点是否被访问过。
- 选择起始节点。
访问节点：
- 访问当前节点，并标记为已访问。
递归/栈扩展：
- 遍历当前节点的所有邻接节点，对未访问的节点递归调用 DFS 或将其入栈。
回溯：
- 当无法继续深入时，回溯到上一个节点。

4. 时间复杂度

邻接表表示：O(V+E)，其中 V 是顶点数，E 是边数。
邻接矩阵表示：O(V2)，因为需要遍历整个矩阵。

5. 应用场景

图的连通性：判断图中两个节点是否连通。
拓扑排序：用于有向无环图（DAG）的拓扑排序。
路径搜索：寻找图中从起点到终点的路径。
环检测：检测图中是否存在环。
生成迷宫：通过 DFS 生成随机迷宫。

6. 代码示例：图的连通分量

以下代码使用 DFS 计算无向图的连通分量数量：

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {visited[node] = true;for (int neighbor : graph[node]) {if (!visited[neighbor]) {dfs(neighbor, graph, visited);}}
}int countConnectedComponents(vector<vector<int>>& graph) {int n = graph.size();vector<bool> visited(n, false);int count = 0;for (int i = 0; i < n; ++i) {if (!visited[i]) {dfs(i, graph, visited); // 对每个未访问的节点调用 DFScount++; // 连通分量数量加 1}}return count;
}

7. DFS 的变种

回溯算法：DFS 常用于解决组合优化问题，如八皇后问题、数独等。
记忆化搜索：在递归过程中记录中间结果，避免重复计算。
迭代加深搜索（IDS）：结合 DFS 和 BFS 的优点，逐步增加搜索深度。

8. DFS 与 BFS 的比较

特性	DFS	BFS
数据结构	栈（递归或显式栈）	队列
空间复杂度	O(V)O(V)（递归深度）	O(V)O(V)（队列大小）
适用场景	路径搜索、拓扑排序	最短路径、连通分量
是否找到最短路径	否	是

9.例题

P1036 [NOIP 2002 普及组] 选数 - 洛谷

#include <iostream>
#include <cstdio>
using namespace std;
bool isprime(int a){for(int i = 2; i * i <= a; i++)if(a % i == 0)return false;return true;
}int n,k;
int a[25];
long long ans;void dfs(int m, int sum, int startx){if(m == k){if(isprime(sum))ans++;return ;}for(int i = startx; i < n; i++)dfs(m + 1, sum + a[i], i + 1);return ;
}int main(){scanf("%d%d",&n,&k);for(int i = 0; i < n; i++)scanf("%d",&a[i]);dfs(0, 0, 0);printf("%d\n",ans);return 0;
}