【算法学习】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的父节点node
q.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优势与局限
优点：
空间效率高（仅存储当前路径）。
适合寻找所有解（如回溯算法）。
缺点：
可能陷入无限深的分支（需设置最大深度）。
递归实现有栈溢出风险（可改用显式栈）。