【算法学习】DFS与BFS

一，深度优先搜索

1，DFS

2，图的DFS遍历

(1)，递归实现（隐士栈）

(2)，显示栈实现（非递归）

二，广度优先搜索

1，BFS

2，图的BFS遍历

3，路径记录

小结：

最短路径问题（BFS）

BFS(广度优先搜索）和DFS（深度优先搜索）

BFS和DFS树是图/树遍历的两种基础算法，核心在于探索顺序和适用场景的不同。

一，深度优先搜索

1，DFS

DFS即Depth First Search，深度优先搜索。遍历顺序为：沿分支深入到底再回溯，优先探索最新发现的节点。简单来说，就是一条路走到黑。比如对下面一颗树的遍历。

从A开始遍历，再到B，有两种情况，意味着这条路还没有走完，接着走到D，之后就没路了。然后我就回溯到B，因为B还有情况没走完，接着再走到E，之后没路了，就回溯到B，发现B的两种情况以及那个走完了，就再回溯到A，然后走到C......

简单理解就是：一条路走动黑，直到没路可走了，再回溯回去，尝试其他路径。

2，图的DFS遍历

DFS的实现方式有两种，一种是递归实现，但递归实现有时会产生栈溢出的风险，可改用显示栈实现。

(1)，递归实现（隐士栈）

#include <iostream>
#include <vector>
using namespace std;void DFS(vector<vector<int>>& graph, int node, vector<bool>& visited)
{visited[node] = true;cout << node << " ";    //前序遍历for (int neighbors : graph[node]){if (!visited[neighbors])DFS(graph, neighbors, visited);}}int main()
{//邻接表表示(无向图）vector<vector<int>> graph = {{1,2},      //节点0的邻居是1 2{0,3,4},	//节点1的邻居是0 3 4{0,5},		//节点2的邻居是0 5{1},        //节点3的邻居是1{1},        //节点4的邻居是1{2}         //节点5的邻居是2};//记录访问过的节点vector<bool> visited(graph.size(), false);cout << "DFS结果为:";DFS(graph, 0, visited);return 0;
}

(2)，显示栈实现（非递归）


#include <iostream>
#include <stack>
#include <vector>
using namespace std;
void DFS_Stack(vector<vector<int>>& graph, int start)
{vector<bool> visited(graph.size(), false);stack<int> s;s.push(start);visited[start] = true;while (!s.empty()){int node = s.top();s.pop();cout << node << " ";//逆序入栈 以保证和递归顺序一致for (auto it = graph[node].rbegin(); it != graph[node].rend(); it++){int neighbors = *it;if (!visited[neighbors]){visited[neighbors] = true;s.push(neighbors);}}}
}
int main()
{//邻接表表示(无向图）vector<vector<int>> graph = {{1,2},      //节点0的邻居是1 2{0,3,4},	//节点1的邻居是0 3 4{0,5},		//节点2的邻居是0 5{1},        //节点3的邻居是1{1},        //节点4的邻居是1{2}         //节点5的邻居是2};cout << "栈实现遍历结果为:" << endl;DFS_Stack(graph, 0);return 0;
}

二，广度优先搜索

1，BFS

BFS即Breadth First Search，即广度优先搜索。DFS是一条路走到黑，那么 BFS就可以理解成是在每个岔路口都向前走一步。也可以理解成是一层一层遍历。

从A开始遍历，有两种情况B，C。将B，C遍历完后，再遍历D,E,F。一层一层的遍历。

上述是对树的BFS，然而树也是一种图。不难发现，我们每次搜索的位置都是离当前节点最近的点。因此，BFS是具有最短路性质的。这里用到的贪心策略是：想要找到最短路径，保证每次在选节点时，也就是每次前进的时候，都是距离上一个节点最近的点。

因此，BFS也可以求解最短路问题。

2，图的BFS遍历

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>using namespace std;// BFS 遍历函数
void BFS(const vector<vector<int>>& graph, int start) {vector<bool> visited(graph.size(), false); // 访问标记数组queue<int> q;q.push(start);visited[start] = true;while (!q.empty()) {int node = q.front();q.pop();cout << node << " "; // 输出当前节点（可替换为自定义操作）// 遍历所有邻接节点for (int neighbor : graph[node]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}
}int main() {// 示例图的邻接表表示（无向图）vector<vector<int>> graph = {{1, 2},     // 节点0的邻居是1和2{0, 3, 4},  // 节点1的邻居是0、3、4{0, 5},     // 节点2的邻居是0、5{1},        // 节点3的邻居是1{1},        // 节点4的邻居是1{2}         // 节点5的邻居是2};cout << "BFS遍历结果：";BFS(graph, 0); // 从节点0开始遍历// 输出：0 1 2 3 4 5 return 0;
}

3，路径记录

在图中寻找一条从开始到目标target的路径。

vector<int> BFS_Path(vector<vector<int>>& graph, int start, int target)
{vector<bool> visited(graph.size(), false);  //记录访问过的节点vector<int> parent(graph.size(), -1);  //记录父节点queue<int> q;q.push(start);visited[start] = true;while (!q.empty()){int node = q.front();q.pop();if (node == target)break;for (int neighbors : graph[node]){if (!visited[neighbors]){visited[neighbors] = true;parent[neighbors] = node; //neighbors的父节点nodeq.push(neighbors);}}}vector<int> path;for (int at = target; at != -1; at = parent[at])path.push_back(at);reverse(path.begin(), path.end());return path;
}

最短路径问题（BFS）

【题目描述】

给的那个一个n*m的二维整数数组，用来表示迷宫，数组中只包含1和0，0表示可以走的路，1表示不可以通过的墙壁。

最初，有一个人位于左上角(1,1)处，已知改人每次可以向上，下，做，右任意一个方向移动一个位置。请问：改人从左上角移动到右下角(n,m），至少需要移动多少次。数据保证（0，0）和（n,m）的位置均为0。且一定至少存在一条通路。

【输入格式】

第一行包含两个整数n和m。

接下来n行，每行包含m个整数（0或1），表示迷宫。

【输出格式】

表示最少移动次数。

本题求的是最短路，所以可以用bfs从当前节点出发，每次向四周扩展。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;typedef pair<int, int> PII;//方向数组
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
const int N = 110;
int map[N][N];  //迷宫
int mark[N][N];  //标记数组
int n, m;void BFS()
{memset(mark, -1, sizeof(mark));queue<PII> q;q.push({ 0,0 });mark[0][0] = 0;while (!q.empty()){PII top = q.front();q.pop();for (int i = 0; i < 4; i++){int x = top.first + dx[i];int y = top.second + dy[i];if (x >= 0 && x < n && y >= 0 && y < m && mark[x][y] == -1 && map[x][y] == 0){q.push({ x,y });mark[x][y] = mark[top.first][top.second] + 1;}}}cout<<mark[n - 1][m - 1]<<endl;
}
int main()
{cin >> n >> m;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> map[i][j];BFS();return 0;
}

小结：

BFS优势与局限

优点：

保证找到最短路径（无权图）。

避免深度过大的栈溢出风险。

缺点：

空间消耗大（存储整层节点）。

不适合目标节点在深层的情况（效率低）。

DFS优势与局限

优点：

空间效率高（仅存储当前路径）。

适合寻找所有解（如回溯算法）。

缺点：

可能陷入无限深的分支（需设置最大深度）。

递归实现有栈溢出风险（可改用显式栈）。