【C++ 算法】DFS & BFS 一篇速成学习
📃个人主页：island1314
⛺️ 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞
- 生活总是不会一帆风顺，前进的道路也不会永远一马平川，如何面对挫折影响人生走向 – 《人民日报》
🔥 目录
一、DFS
1. 基本思想
DFS（Depth-First Search）是一种通过递归或显式栈结构实现的搜索算法，其核心思想是 “一条路走到黑，不撞南墙不回头”。它会沿着某条分支尽可能深入，直到无法继续时回溯到上一个分叉点
2. 特点
- 数据结构：使用栈（递归调用栈或手动维护的栈）。
- 空间复杂度：取决于递归深度，最坏为 𝑂(𝐻)O(H)（𝐻H 为树的高度或图的深度）。
- 时间复杂度：𝑂(𝑉+𝐸)O(V+E)（遍历所有顶点和边）。
- 适用场景：
- 路径搜索（如迷宫问题）
- 连通性检测（如岛屿问题）
- 回溯问题（如排列组合、N皇后）
- 拓扑排序（后序遍历逆序）
3. C++实现
非递归实现（显式栈）
voiddfs_iterative(int start, vector<vector<int>>& graph){ stack<int> st; vector<bool>visited(graph.size(),false); st.push(start); visited[start]=true;while(!st.empty()){int u = st.top(); st.pop();for(int v : graph[u]){if(!visited[v]){ visited[v]=true; st.push(v);}}}}递归实现（以图的遍历为例）
voiddfs(int u, vector<bool>& visited, vector<vector<int>>& graph){ visited[u]=true;for(int v : graph[u]){if(!visited[v]){dfs(v, visited, graph);}}}4. 经典例题
例题1：八皇后（洛谷P1219）
题目链接：USACO1.5 八皇后 Checker Challenge - 洛谷
思路：二进制来表示
代码如下：
#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<unordered_map>usingnamespace std;int n;#defineMASK(n)((1<<(n+1))-2)//如 6 得到的是1000 0000 -> 111 1110,零位上的1不用 unordered_map<int,int> ind;int tot =3;int arr[20];voidout(){for(int i =1; i <= n; i++){if(i >1) cout <<" ";printf("%d", arr[i]);}printf("\n"); tot--;return;}intdfs(int i,int t1,int t2,int t3){if(i > n){if(tot)out();return1;}int ans =0;for(int t = t1; t; t -=(-t & t)){int j = ind[-t & t];if((t2 &(1<<(i + j -1)))&&(t3 &(1<<(i - j + n))))//正斜线和反斜线{ arr[i]= j; ans +=dfs(i +1, t1^(1<< j), t2^(1<<(i + j -1)), t3^(1<<(i - j + n)));//把t1中的j标记为0,然后向左移动一位}}return ans;}intmain(){scanf("%d",&n);for(int i =0; i <2* n; i++) ind[1<< i]= i;int ans =dfs(1,MASK(n),MASK(2* n -1),MASK(2* n -1));//列，正斜边，反斜边 cout << ans <<"\n";return0;}例题2：奇怪的电梯（洛谷P1135）
题目链接：P1135 奇怪的电梯 - 洛谷
思路：
- 先设立两个数组dis[]和to[]，分别**表示到某层的最少按钮数和按键，dfs(k , a)中k表示使用的按钮数目，a表示到某一层，**当dis[]记录到的到某层的最少按钮数小于等于k时，就可递归返回。
代码如下：
#include<iostream>usingnamespace std;constint N =205;int to[N], dis[N];//起点到每个点最短距离int n;voiddfs(int k,int a){if(dis[a]<= k)return; dis[a]= k;//刷新到a的最短距离if(a + to[a]<= n)dfs(k +1, a + to[a]);if(a - to[a]>=1)dfs(k +1, a - to[a]);}intmain(){int a, b; cin >> n >> a >> b;for(int i =1; i <= n; i++){ cin >> to[i];//输入每个按钮的值 dis[i]= n +1;}dfs(0, a);printf("%d\n", dis[b]== n +1?-1: dis[b]);return0;}例题3：选数（洛谷P1036）
题目链接：P1036 NOIP 2002 普及组选数 - 洛谷
思路：
- **dfs(u, ind, sum)**分别表示当前已经选择了几个数，当前这一层可以选择的最小数字，所选当前的和值，is_prime()函数则用来判断是否为质数。
- 这题与之前文章里的【题目/算法训练】全排列相关问题（不用next-permutation）中的组合型枚举很像，想了解的朋友们可以下
代码如下：
#include<iostream>#include<algorithm>#include<cstring>usingnamespace std;constint N =25;int a[N];int n, k;longlong ans =0;//计算素数的数量boolis_prime(int x){if(x <2)returnfalse;for(int i =2; i <= x / i; i++){if(x % i ==0)returnfalse;}returntrue;}voiddfs(int u,int ind,int sum){if(u == k){if(is_prime(sum)) ans++;return;}for(int i = ind; i <= n; i++){dfs(u +1, i +1,sum + a[i]);}}intmain(){ cin >> n >> k;for(int i =1; i <= n; i++) cin >> a[i];dfs(0,1,0);printf("%lld\n", ans);return0;}例题4：迷宫（洛谷P1605）
题目链接：P1605 迷宫 - 洛谷
思路：
- **技巧：**从（1，1）开始读入，给地图上可以行走的地方初始化为1，0表示不可以走的点，相当于给地图外面放上障碍，就不用向上面一样对(x，y)进行特殊判断（如判断是否为1该点相邻的点，是不是障碍，有没有访问过）
代码如下：
#include<iostream>usingnamespace std;constint N =7;int g[N][N];int n, m, t, sx, sy, ex, ey;int ans =0;//记录方法的数量int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};voiddfs(int x,int y){if(x == ex && y == ey){ ans++;return;} g[x][y]=0;//表示当前点遍历过for(int i =0; i <4; i++){int dx = x + dir[i][0], dy = y + dir[i][1];if(g[dx][dy]==0)continue;dfs(dx, dy);} g[x][y]=1;}intmain(){ cin >> n >> m >> t;for(int i =1; i <= n; i++){for(int j =1;j<=m;j++) g[i][j]=1;} cin >> sx >> sy >> ex >> ey;for(int i =0; i < t; i++){int x, y; cin >> x >> y; g[x][y]=0;}dfs(sx, sy); cout << ans <<"\n";return0;}例题5：吃奶酪（洛谷P1433）
题目链接：P1433 吃奶酪 - 洛谷
思路：
- **技巧：**从（1，1）开始读入，给地图上可以行走的地方初始化为1，0表示不可以走的点，相当于给地图外面放上障碍，就不用向上面一样对(x，y)进行特殊判断（如判断是否为1该点相邻的点，是不是障碍，有没有访问过）
代码如下：
#include<iostream>#include<cmath>usingnamespace std;constint N =17;double ans =1e9;int n;double x[N], y[N];double dis[N][N];//dis[i][j]表示从第i个奶酪到第j个奶酪的距离double dp[70000][20];//2^16,第一个位置表示状态编码,第二个位置表示达到当前状态，最后一个吃掉的奶酪编号int ind[70000];//权值映射doubled(int i,int j){returnsqrt((x[i]- x[j])*(x[i]- x[j])+(y[i]- y[j])*(y[i]- y[j]));}voiddfs(int t,int now,double s){if(t ==0){//吃掉了所有奶酪if(s < ans) ans = s;return;}for(int k = t; k; k -=(k &-k)){int to = ind[k &-k], next_t = t -(1<< to);double l = s + dis[now][to];if(dp[next_t][to]!=0&& dp[next_t][to]<= l)continue; dp[next_t][to]= l;if(ans <= l)continue;dfs(next_t, to, l);}}intmain(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; x[0]= y[0]=0;//小老鼠位置for(int i =1; i <= n; i++) cin >> x[i]>> y[i];for(int i =0; i <= n; i++){for(int j = i; j <= n; j++) dis[i][j]= dis[j][i]=d(i, j);}for(int k =1, i =0; i <= N; i++, k *=2)ind[k]= i;//权值到下标映射dfs((1<<(n +1))-2,0,0);//当前位置状态码，所在奶酪下标，到达状态所走总路程printf("%.2lf\n", ans);return0;}例题6：单词搜索（LeetCode 79）
题目链接：P1433 吃奶酪 - 洛谷
思路：
- 很常规的DFS搜索，当第一个字符发生匹配时，就开始往下搜索，不匹配就退回来，直到遍历完所有字符都没有匹配成功，才返回false.
- 因此需要注意的是：应该是写成
if (dfs(board, word, i, j, 0)) return true;，而不是return dfs(board, word, i, j, 0);
代码如下：
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};int n, m;bool st[505][505];booldfs(vector<vector<char>>& board, string word,int x,int y,int pos){if(pos == word.size())returntrue;// 向量的方式，定义上下左右四个位置for(int i =0; i <4; i++){int dx = x + dir[i][0], dy = y + dir[i][1];if(dx >=0&& dx < n && dy >=0&& dy < m && board[dx][dy]== word[pos]&&!st[dx][dy]){ st[dx][dy]=true;if(dfs(board, word, dx, dy, pos +1))returntrue; st[dx][dy]=false;}}returnfalse;}boolexist(vector<vector<char>>& board, string word){ n = board.size(), m = board[0].size();for(int i =0; i < n; i++){for(int j =0; j < m; j++){if(board[i][j]== word[0]){ st[i][j]=true;if(dfs(board, word, i, j,1))returntrue; st[i][j]=false;}}}returnfalse;}二、BFS
1. 基本思想
BFS（Breadth-First Search）通过队列逐层扩展搜索，保证先访问离起点最近的节点。其核心是“地毯式搜索，层层推进”。
2. 特点
- 数据结构：使用队列。
- 空间复杂度：𝑂(𝑉)O(V)（最坏情况存储所有顶点）。
- 时间复杂度：𝑂(𝑉+𝐸)O(V+E)。
- 适用场景：
- 无权图的最短路径（如迷宫最短步数）。
- 层级遍历（如二叉树的层次遍历）。
- 广播网络（如社交网络中的信息扩散）。
- 检测图的二分性（Bipartite）
3. C++实现
标准实现（以图的遍历为例）
voidbfs(int start, vector<vector<int>>& graph){ queue<int> q; vector<bool>visited(graph.size(),false); q.push(start); visited[start]=true;while(!q.empty()){int u = q.front(); q.pop();for(int v : graph[u]){if(!visited[v]){ visited[v]=true; q.push(v);}}}}4. 经典例题
例题1：马的遍历（洛谷P1443）
题目链接：P1443 马的遍历 - 洛谷
思路：
- 假设马在（x，y）这个点，则马可以移动的方向有8个，偏移量如下所示，注意马走日。
- 注：马一次跳跃到达的点(x1,y1)和马原坐标(x,y)的关系是 ∣x1−x∣+∣y1−y∣=3.
| （-1，-2） | （1，-2） | |||
|---|---|---|---|---|
| （-2，-1） | （2，-1） | |||
| （x，y） | ||||
| （-2，1） | （2，1） | |||
| （-1，2） | （1，2） |
这题如果用之前的dfs（step，x，y）来表示则会超时，因此我们应该使用BFS算法层序遍历，遍历每一层，如果遍历了某个节点时，那么后续遍历这个节点绝对比之前找的step要大，层序遍历更适合求最短步长
代码如下：
#include<iostream>#include<queue>usingnamespace std;constint N =405;int dir[8][2]={//偏移量{2,1},{-2,1},{2,-1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};int dis[N][N];int n, m;structNode{//广搜队列Node(int x,int y,int s):x(x),y(y),s(s){}int x, y, s;};voidbfs(int a,int b){ queue<Node> q; q.push(Node(a, b,0)); dis[a][b]=0;//从当前节点扩展到其他点while(!q.empty()){ Node now = q.front(); q.pop();for(int k =0; k <8; k++){int dx = now.x + dir[k][0], dy = now.y + dir[k][1];if(dx <1|| dx > n)continue;if(dy <1|| dy > m)continue;if(dis[dx][dy]!=-1)continue; q.push(Node(dx, dy, now.s +1)); dis[dx][dy]= now.s +1;}}}intmain(){int a, b; cin >> n >> m >> a >> b;for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){ dis[i][j]=-1;//赋初值}}bfs(a, b);//到达当前点所花步数，(a,b)表示当前所在位置for(int i =1; i <= n; i++){for(int j =1; j <= m; j++){ cout << dis[i][j]<<" ";} cout <<"\n";}return0;}5. BFS 解决最短路问题
例题1：迷宫离入口最近的出口（LeetCode 1296）
题目链接：1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）
思路：
- 类似于层序遍历的操作，从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候，得到起点到出口的最短距离。
代码如下
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};intnearestExit(vector<vector<char>>& maze, vector<int>& entrance){int n = maze.size(), m = maze[0].size(); queue<pair<int,int>> q; q.push({entrance[0], entrance[1]}); vector<vector<int>>vis(n, vector<int>(m)); vis[entrance[0]][entrance[1]]=true;int ans =0;while(!q.empty()){ ans++;int size = q.size();while(size--){auto[x, y]= q.front(); q.pop();for(int k =0; k <4; k++){int dx = x + dir[k][0], dy = y + dir[k][1];if(dx >=0&& dx < n && dy >=0&& dy < m &&!vis[dx][dy]&& maze[dx][dy]=='.'){if(dx ==0|| dx == n -1|| dy ==0|| dy == m -1)return ans; q.push({dx, dy}); vis[dx][dy]=true;}}}}return-1;}例题2：最小基因变化（LeetCode 433）
题目链接：433. 最小基因变化 - 力扣（LeetCode）
思路：
- 如果将「每次字符串的变换」抽象成图中的「两个顶点和一条边」的话，问题就变成了「边权为 1的最短路问题」
- 因此，从起始的字符串开始，来一次 bfs即可
代码如下
intminMutation(string startGene, string endGene, vector<string>& bank){ unordered_set<string> vis; unordered_set<string>hash(bank.begin(), bank.end());if(startGene == endGene)return0;if(!hash.count(endGene))return-1; string change ="ACGT"; queue<string> q; q.push(startGene); vis.insert(startGene);int ret =0;while(!q.empty()){ ret++;int size = q.size();while(size--){ string t = q.front(); q.pop();for(int i =0; i <8; i++){ string tmp = t;for(int j =0; j <change.size(); j++){ tmp[i]= change[j];if(hash.count(tmp)&&!vis.count(tmp)){if(tmp == endGene)return ret; q.push(tmp); vis.insert(tmp);}}}}}return-1;}例题3：单词接龙（LeetCode 127）
思路：
- 和上题类似
代码如下
intladderLength(string beginWord, string endWord, vector<string>& wordList){ unordered_set<string>hash(wordList.begin(), wordList.end()); unordered_set<string> vis;if(hash.count(endWord)==0)return0; queue<string> q; q.push(beginWord); vis.insert(beginWord);int ret =1;while(!q.empty()){ ret++;int size = q.size();while(size--){ string t = q.front(); q.pop();for(int i =0; i < t.size(); i++){ string tmp = t;for(char ch ='a'; ch <='z'; ch++){ tmp[i]= ch;if(hash.count(tmp)&&!vis.count(tmp)){if(tmp == endWord)return ret; q.push(tmp); vis.insert(tmp);}}}}}return0;}例题4：为高尔夫比赛砍树（LeetCode 675）
题目链接：675. 为高尔夫比赛砍树 - 力扣（LeetCode）
- 先找出砍树的顺序;
- 然后按照砍树的顺序，一个一个的用 bfs 求出最短路即可。
代码如下
int m, n;bool vis[55][55];int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};intbfs(vector<vector<int>>&forest,int bx,int by,int ex,int ey){if(bx == ex && by == ey)return0; queue<pair<int,int>> q;memset(vis,0,sizeof(vis)); q.push({bx, by}); vis[bx][by]=true;int step =0;while(!q.empty()){ step++;int size = q.size();while(size--){auto[a, b]= q.front(); q.pop();for(int i =0; i <4; i++){int x = a + dir[i][0], y = b + dir[i][1];if(x >=0&& x < n && y >=0&& y < m && forest[x][y]&&!vis[x][y]){if(x == ex && y == ey)return step; q.push({x, y}); vis[x][y]=true;}}}}return-1;}intcutOffTree(vector<vector<int>>& forest){// 1. 找出砍树顺序(从小到大) n = forest.size(), m = forest[0].size(); vector<pair<int,int>> trees;for(int i =0; i < n; i++){for(int j =0; j < m; j++){if(forest[i][j]>1){ trees.push_back({i, j});}}}sort(trees.begin(), trees.end(),[&](const pair<int,int> x,const pair<int,int> y){return forest[x.first][x.second]< forest[y.first][y.second];});// 2. 按照顺序砍树 -- 相邻树的最短距离int bx =0, by =0;int ret =0;for(auto&[a, b]: trees){int step =bfs(forest, bx, by, a, b);if(step ==-1)return-1; ret += step; bx = a, by = b;}return ret;}https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/6. 多源最短路 BFS
例题1：01 矩阵（LeetCode 542）
题目链接：542. 01 矩阵 - 力扣（LeetCode）
对于求的最终结果，我们有两种方式:
- 方法一：从每一个 1 开始，然后通过层序遍历找到离它最近的0。
- 这一种方式，我们会以所有的 1起点，来一次层序遍历，势必会遍历到很多重复的点。并且如果矩阵中只有一个 0的话，每一次层序遍历都要遍历很多层，时间复杂度较高。
- 方法二：从 0 开始层序遍历，并且记录遍历的层数。当第一次碰到 1 的时候，当前的层数就是这个 1离 0 的最短距离
- 这一种方式，我们在遍历的时候标记一下处理过的1，能够做到只用遍历整个矩阵一次，就能得到最终结果。
- 但是，这里有一个问题，0是有很多个的，我们怎么才能保证遇到的1距离这一个 0是最近的呢?
- 其实很简单，我们可以先把所有的 0 都放在队列中，把它们当成一个整体，每次把当前队列里面的所有元素向外扩展一次。
代码如下
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; vector<vector<int>>updateMatrix(vector<vector<int>>& mat){int n = mat.size(), m = mat[0].size();// dist[i][j] == -1 没有搜索过 vector<vector<int>>dist(n, vector<int>(m,-1)); queue<pair<int,int>> q;// 1. 把所有点放入队列for(int i =0; i < n; i++){for(int j =0; j < m; j++){if(mat[i][j]==0){ dist[i][j]=0; q.push({i, j});}}}// 2. 一层一层扩展while(!q.empty()){auto[a, b]= q.front(); q.pop();for(int k =0; k <4; k++){int x = a + dir[k][0], y = b + dir[k][1];if(x >=0&& x < n && y >=0&& y < m && dist[x][y]==-1){ dist[x][y]= dist[a][b]+1; q.push({x, y});}}}return dist;}例题2：飞地的数量（LeetCode 1020）
题目链接：1020. 飞地的数量 - 力扣（LeetCode）
思路（正难则反）
- 从边上的 1开始搜索，把与边上1相连的联通区域全部标记一下然后再遍历一遍矩阵，看看哪些位置的1没有被标记即可标记的时候，可以用「多源 bfs 」解决。
代码如下
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};intnumEnclaves(vector<vector<int>>& grid){int n = grid.size(), m = grid[0].size(); vector<vector<bool>>vis(n, vector<bool>(m)); queue<pair<int,int>> q;for(int i =0; i < n; i++){for(int j =0; j < m; j++){if((i ==0|| i == n -1|| j ==0|| j == m -1)&& grid[i][j]==1){ q.push({i, j}); vis[i][j]=true;}}}while(!q.empty()){auto[a, b]= q.front(); q.pop();for(int k =0; k <4; k++){int x = a + dir[k][0], y = b + dir[k][1];if(x >=0&& x < n && y >=0&& y < m &&!vis[x][y]&& grid[x][y]==1){ q.push({x, y}); vis[x][y]=true;}}}int ret =0;for(int i =0; i < n; i++){for(int j =0; j < m; j++){if(grid[i][j]==1&&!vis[i][j]) ret++;}}例题3：地图上的最高点（LeetCode 1765）
题目链接：1765. 地图中的最高点 - 力扣（LeetCode）
思路
- 01 矩阵的变型题，直接用多源 BFS 解决
代码如下
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; vector<vector<int>>highestPeak(vector<vector<int>>& isWater){int n = isWater.size(), m = isWater[0].size(); vector<vector<int>>dist(n, vector<int>(m,-1)); queue<pair<int,int>> q;for(int i =0; i < n; i++){for(int j =0; j < m; j++){if(isWater[i][j]){ dist[i][j]=0; q.push({i, j});}}}while(!q.empty()){auto[a, b]= q.front(); q.pop();for(int k =0; k <4; k++){int x = a + dir[k][0], y = b + dir[k][1];if(x >=0&& x < n && y >=0&& y < m && dist[x][y]==-1){ dist[x][y]= dist[a][b]+1; q.push({x, y});}}}return dist;}例题4：地图分析（LeetCode 1765）
题目链接：1162. 地图分析 - 力扣（LeetCode）
思路
- 01 矩阵的变体
代码如下
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};intmaxDistance(vector<vector<int>>& grid){int n = grid.size(), m = grid[0].size(); vector<vector<int>>dist(n, vector<int>(m,-1)); queue<pair<int,int>> q;for(int i =0; i < n; i++){for(int j =0; j < m; j++){if(grid[i][j]){// 所有陆地 dist[i][j]=0; q.push({i, j});}}}int ret =-1;while(!q.empty()){auto[a, b]= q.front(); q.pop();for(int k =0; k <4; k++){int x = a + dir[k][0], y = b + dir[k][1];if(x >=0&& x < n && y >=0&& y < m && dist[x][y]==-1){ dist[x][y]= dist[a][b]+1; q.push({x, y}); ret =max(ret, dist[x][y]);}}}return ret;}8. BFS 解决拓扑排序
例题1：课程表（LeetCode 207）
思路：BFS 解决拓扑排序即可
- 将所有入度为0的点加入到队列中;当队列不空的时候，一直循环:
- 取出队头元素;
- 将于队头元素相连的顶点的入度-1;
- 然后判断是否减成 0,。如果减成0，就加入到队列中。
代码如下
boolcanFinish(int numCourses, vector<vector<int>>& prerequisites){ vector<vector<int>>adj(numCourses); vector<int>d(numCourses,0); queue<int> q;for(auto e: prerequisites){int u = e[0], v = e[1]; adj[u].emplace_back(v); d[v]++;}for(int i =0; i < numCourses; i++){if(d[i]==0) q.push(i);}int cnt =0;while(!q.empty()){int u = q.front(); q.pop(); cnt++;for(auto v: adj[u]){if(--d[v]==0) q.push(v);}}return cnt == numCourses;}例题2：课程表II（LeetCode 210）
题目链接：210. 课程表 II - 力扣（LeetCode）
思路：和上面类似
代码如下
vector<int>findOrder(int numCourses, vector<vector<int>>& prerequisites){ vector<vector<int>>adj(numCourses); vector<int>d(numCourses,0);for(auto e: prerequisites){int v = e[0], u = e[1];// e[0] <- e[1] adj[u].push_back(v); d[v]++;} queue<int> q;for(int i =0; i < numCourses; i++){if(d[i]==0) q.push(i);} vector<int> ans;while(!q.empty()){int u = q.front(); q.pop(); ans.push_back(u);for(auto v: adj[u]){if(--d[v]==0) q.push(v);}}return ans.size()!= numCourses ? vector<int>(): ans;}例题3：火星词典（LeetCode LCR 114）
题目链接：LCR 114. 火星词典 - 力扣（LeetCode）
思路：将题意搞清楚之后，这道题就变成了判断有向图时候有环，可以用拓扑排序解决。
如何搜集信息(如何建图)
- 两层 for 循环枚举出所有的两个字符串的组合;
- 然后利用指针，根据字典序规则找出信息。
代码如下
unordered_map<char, unordered_set<char>> edges; unordered_map<char,int> in;// 入度booladd(string &s1, string &s2){int n =min(s1.size(), s2.size());int i =0;for(; i < n; i++){if(s1[i]!= s2[i]){char a = s1[i], b = s2[i];// a -> bif(!edges.count(a)||!edges[a].count(b)){ edges[a].insert(b); in[b]++;}break;}}if(i == s2.size()&& i < s1.size())returntrue;returnfalse;} string alienOrder(vector<string>& words){// 1. 建图 + 初始化入度for(auto&s: words){for(auto&ch: s){ in[ch]=0;}}// 2. 连接int n = words.size();for(int i =0; i < n; i++){for(int j = i +1; j < n; j++){if(add(words[i], words[j]))return"";}}// 3. 拓扑排序 queue<char> q;for(auto&[a, b]: in){if(b ==0) q.push(a);} string ret;while(!q.empty()){char t = q.front(); q.pop(); ret += t;for(auto ch: edges[t]){if(--in[ch]==0) q.push(ch);}}for(auto&[a, b]: in){if(b !=0)return"";}return ret;}三、对比
| 特性 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归/非递归） | 队列 |
| 空间复杂度 | 𝑂(𝐻)（路径深度） | 𝑂(𝑉)（存储所有节点） |
| 最短路径 | 不保证（可能找到非最短解） | 保证（无权图最短路径） |
| 适用场景 | 路径存在性、回溯问题 | 最短路径、层级遍历 |
| 内存消耗 | 较低（适合深树） | 较高（适合宽图） |
经典例题对比 --解决 FloodFill 算法
例题1：图像渲染（LeetCode 733）
思路：
- 可以利用「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可
DFS 方法如下：
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};typedef pair<int,int> PII; vector<vector<int>>floodFill(vector<vector<int>>& image,int sr,int sc,int color){int target = image[sr][sc];if(target == color)return image;int m = image.size(), n = image[0].size(); queue<PII> q; q.push({sr, sc});while(!q.empty()){auto[a, b]= q.front(); q.pop(); image[a][b]= color;for(int i =0; i <4; i++){int x = a + dir[i][0], y = b + dir[i][1];if(x >=0&& x < m && y >=0&& y < n && image[x][y]== target){ q.push({x, y});}}}return image;}BFS 方法如下：
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};typedef pair<int,int> PII; vector<vector<int>>floodFill(vector<vector<int>>& image,int sr,int sc,int color){int target = image[sr][sc];if(target == color)return image;int m = image.size(), n = image[0].size(); queue<PII> q; q.push({sr, sc});while(!q.empty()){auto[a, b]= q.front(); q.pop(); image[a][b]= color;for(int i =0; i <4; i++){int x = a + dir[i][0], y = b + dir[i][1];if(x >=0&& x < m && y >=0&& y < n && image[x][y]== target){ q.push({x, y});}}}return image;}例题2：岛屿数量（LeetCode 200）
思路：
- 可以利用「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可
DFS 方法如下：
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};int n, m;bool vis[505][505];//标记该点是否用过voiddfs(vector<vector<char>>& grid,int x,int y){ vis[x][y]=true;for(int i =0; i <4; i++){int dx = x + dir[i][0], dy = y + dir[i][1];if(dx >=0&& dx < m && dy >=0&& dy < n &&!vis[dx][dy]&& grid[dx][dy]=='1'){dfs(grid, dx, dy);}}}intnumIslands(vector<vector<char>>& grid){ m = grid.size(), n = grid[0].size();int ret =0;for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(!vis[i][j]&& grid[i][j]=='1'){ ret++;dfs(grid, i, j);}}}return ret;}BFS 方法如下：
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};bool vis[305][305];int m, n;voidbfs(vector<vector<char>>& grid,int i,int j){ queue<pair<int,int>> q; q.push({ i, j }); vis[i][j]=true;while(q.size()){auto[a, b]= q.front(); q.pop();for(int k =0; k <4; k++){int x = a + dir[k][0], y = b + dy[k][1];if(x >=0&& x < m && y >=0&& y < n && grid[x][y]=='1'&&!vis[x][y]){ q.push({ x, y }); vis[x][y]=true;}}}}intnumIslands(vector<vector<char>>& grid){ m = grid.size(), n = grid[0].size();int ret =0;for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(grid[i][j]=='1'&&!vis[i][j]){ ret++;bfs(grid, i, j);// 把这块陆地全部标记⼀下}}}return ret;}例题3：岛屿的最大面积（LeetCode 695）
题目链接：695. 岛屿的最大面积 - 力扣（LeetCode）
思路：
- 遍历整个矩阵，每当遇到一块土地的时候，就用「深搜」或者「宽搜」将与这块土地相连的「整个岛屿」的面积计算出来。
- 然后在搜索得到的「所有的岛屿面积」求一个「最大值」即可。在搜索过程中，为了「防止搜到重复的土地」：可以开一个同等规模的「布尔数组」，标记一下这个位置是否已经被访问过;。
- 也可以将原始矩阵的 1修改成 0，但是这样操作会修改原始矩阵
DFS 方法如下：
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};int n, m, cnt;bool vis[505][505];//标记该点是否用过voiddfs(vector<vector<int>>& grid,int x,int y){ vis[x][y]=true; cnt++;//记录每块岛屿的面积for(int i =0; i <4; i++){int dx = x + dir[i][0], dy = y + dir[i][1];if(dx >=0&& dx < m && dy >=0&& dy < n &&!vis[dx][dy]&& grid[dx][dy]==1){dfs(grid, dx, dy);}}}intmaxAreaOfIsland(vector<vector<int>>& grid){ m = grid.size(), n = grid[0].size();int ret =0;//统计最大数量for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(!vis[i][j]&& grid[i][j]==1){ cnt =0;dfs(grid, i, j); ret =max(cnt, ret);}}}return ret;}BFS 方法如下：
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};bool vis[51][51];int m, n;intbfs(vector<vector<int>>& grid,int i,int j){int count =0; queue<pair<int,int>> q; q.push({ i, j }); vis[i][j]=true; count++;while(q.size()){auto[a, b]= q.front(); q.pop();for(int k =0; k <4; k++){int x = a + dir[k][0], y = b + dy[k][1];if(x >=0&& x < m && y >=0&& y < n && grid[x][y]==1&&!vis[x][y]){ q.push({ x, y }); vis[x][y]=true; count++;}}}return count;}intmaxAreaOfIsland(vector<vector<int>>& grid){ m = grid.size(), n = grid[0].size();int ret =0;for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(grid[i][j]==1&&!vis[i][j]){ ret =max(ret,bfs(grid, i, j));}}}return ret;}四、总结
- DFS 以深度优先，适合探索所有可能性或路径存在性问题，但对最短路径不敏感。
- BFS 以广度优先，保证最短路径，但内存消耗较大。
- 实战技巧：
- 组合使用DFS和BFS（如IDA*算法）。
- 剪枝优化（尤其在DFS中减少无效搜索）。
- 双向BFS加速最短路径搜索
使用场景如下：
- DFS适用场景：
- 路径探索：如迷宫问题、图的连通分量。
- 回溯问题：如八皇后、全排列。
- 拓扑排序：通过后序遍历逆序实现。
- 复杂状态转移：如游戏树搜索（AlphaGo）。
- BFS适用场景：
- 最短路径：如社交网络中的“六度空间”。
- 层级遍历：如二叉树按层输出。
- 扩散问题：如病毒传播模拟。
- 二分图检测：通过交替染色判断。
