深度优先搜索

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); // 对每个未访问的节点调用 DFS count++; // 连通分量数量加 1 } } return count; }

---

7. DFS 的变种

回溯算法：DFS 常用于解决组合优化问题，如八皇后问题、数独等。

记忆化搜索：在递归过程中记录中间结果，避免重复计算。

迭代加深搜索（IDS）：结合 DFS 和 BFS 的优点，逐步增加搜索深度。

---

8. DFS 与 BFS 的比较 特性DFSBFS数据结构栈（递归或显式栈）队列空间复杂度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; }