广度优先搜索算法和深度优先搜索算法
目录
广度优先搜索算法和深度优先搜索算法深度优先搜索算法3、升级：用栈模拟深度优先，因为栈具有==先进先出==性质广度优先算法理解升级:用队列实现广度搜索例子总结深度优先搜索算法
1、一种遍历图/搜索树的算法
2、以图为例，沿着树的深度遍历树的节点，尽可能深的搜索树的分直。当节点S的所有边都被探寻过或者在搜寻是节点不满足条件，搜索将回溯到发现节点S那条边的起始节点。整个过程反复进行直到所有节点都被访问。时间复杂度O(!n)
注：口诀：一插到底慢慢拔，有借有还再借不难。第一句说的是，直接搜索树的深度尽可能到底，第二句说得是，回溯后要返回之前的状态。
3、升级：用栈模拟深度优先，因为栈具有先进先出性质
注：拓展：用栈模拟深度优先算法，并且保存最优解。
例子：走迷宫，找最短路径
迷宫的最短路径:给定一个大小为N × M N\times MN×M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。第一行输入一个整数N NN第二行输入一个整数M MM接下来的N NN行M MM列为迷宫矩阵，“#”表示墙壁，“.”表示通道，“S”表示起点，“G”表示终点限制条件 :N, M ≤ 100 N, M \leq 100N, M≤100输入：1010#S######.# ......#..#.#.##.##.#.#........##.##.####....#....#.#######.#....#......####.###.....#...G#
代码：
#include <iostream>#include <string>#include <queue>#include <stack>using namespace std;using PII = pair<int, int>;#define MAX_LEN 20class Solution {public:char m_map[MAX_LEN][MAX_LEN];int m_dis[MAX_LEN][MAX_LEN];int m_rows, m_cols;vector<PII> m_rou;Solution() {m_cols = m_rows = 0;m_rou.clear();}int dirs[4][2] = {{1,0},{-1,0},{0,-1},{0,1} };vector<PII> dfs() {//初始化int srow, scol, erow, ecol;for (int i = 0; i < m_rows; i++) {for (int j = 0; j < m_cols; j++) {m_dis[i][j] = INT_MAX;if (m_map[i][j] == 'S') {srow = i; scol = j;}if (m_map[i][j] == 'G') {erow = i; ecol = j;}}}stack<PII> sta;sta.push(PII(srow, scol));m_dis[srow][scol] = 0;vector<PII> minRoutine;int minsize = INT_MAX;vector<PII> curRoutine;vector<vector<bool>> visited(m_rows, vector<bool>(m_cols, false));//22222stack<PII> staCurRoutine;//sdfswhile (!sta.empty()) {PII pos = sta.top();sta.pop();curRoutine.push_back(pos);visited[pos.first][pos.second] = true;if (pos == PII(erow, ecol)) {visited[pos.first][pos.second] = false;if (curRoutine.size() < minsize) {minRoutine = curRoutine; minsize = curRoutine.size(); }curRoutine.pop_back();continue;}//判断是否穷途末路int flag = 0;for (int i = 0; i < 4; i++) {int newx = pos.first + dirs[i][0], newy = pos.second + dirs[i][1];if (newx >= 0 && newx < m_rows && newy >= 0 && newy < m_cols&& m_map[newx][newy] != '#'&&!visited[newx][newy]) {sta.push(PII(newx, newy));//visited[newx][newy] = true;}else {flag++;}}if (flag == 4) {//说明没有下一次迭代了（主栈没有新的成员）已经穷途末路//需要回溯//添加死路回溯条件while (true) {PII last = curRoutine.back();flag = 0;for (int i = 0; i < 4; i++) {int newx = last.first + dirs[i][0], newy = last.second + dirs[i][1];if (newx < 0 || newx >= m_rows || newy < 0 || newy >= m_cols || m_map[newx][newy] == '#' || visited[newx][newy]) {flag++;}}cout << "(" << last.first << "," << last.second << ")" << " FALG: " << flag << endl;if (flag == 4) {curRoutine.pop_back(); }else {break; }}}}return minRoutine;}};int main() {Solution so;cin >> so.m_rows >> so.m_cols;for (int i = 0; i < so.m_rows; i++) {for (int j = 0; j < so.m_cols; j++) {cin >> so.m_map[i][j];}}vector<PII> res = so.dfs();if (res.empty()) {cout << "无法到达终点！" << endl;}else {cout << "可以到达，最短距离为:" << endl;for (int i = 0; i < res.size(); i++) {cout << res[i].first << ',' << res[i].second << endl;}}cout << res.size() << endl;system("pause");return 0;}
注意：先往栈里扔状态，一直扔。重复检测栈顶状态->往栈里扔状态的过程。但是一旦遇到目的地，就要处理；或者遇到死路或者遍历过的路，所谓走投无路，就要抽身出来，一步一步回溯到有分支的那个状态去。
广度优先算法
优先遍历根节点所有的子节点，在依次遍历每个子节点的子节点
理解
1、理解为树的层序遍历
2、广度优先搜索是一种由近及远的搜索方式，用人话将就是我走的啥路我不知道，但是我知道我走了几步
升级:用队列实现广度搜索
因为队列具有FIFO特性。
例子
迷宫的最短路径:给定一个大小为N × M N\times MN×M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。第一行输入一个整数N NN第二行输入一个整数M MM接下来的N NN行M MM列为迷宫矩阵，“#”表示墙壁，“.”表示通道，“S”表示起点，“G”表示终点限制条件 :N, M ≤ 100 N, M \leq 100N, M≤100输入：1010#S######.# ......#..#.#.##.##.#.#........##.##.####....#....#.#######.#....#......####.###.....#...G#
代码：
/* 迷宫的最短路径:给定一个大小为N × M N\times MN×M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。第一行输入一个整数N NN第二行输入一个整数M MM接下来的N NN行M MM列为迷宫矩阵，“#”表示墙壁，“.”表示通道，“S”表示起点，“G”表示终点限制条件 :N, M ≤ 100 N, M \leq 100N, M≤1001010#S######.# ......#..#.#.##.##.#.#........##.##.####....#....#.#######.#....#......####.###.....#...G#*/#include <iostream>#include <string>#include <queue>#include <stack>using namespace std;using PII = pair<int, int>;#define MAX_LEN 20class Solution {public:char m_map[MAX_LEN][MAX_LEN];int m_dis[MAX_LEN][MAX_LEN];int m_rows, m_cols;vector<PII> m_rou;Solution() {m_cols = m_rows = 0;m_rou.clear();}int dirs[4][2] = {{1,0},{-1,0},{0,-1},{0,1} };int bfs() {//初始化int srow, scol, erow, ecol;for (int i = 0; i < m_rows; i++) {for (int j = 0; j < m_cols; j++) {m_dis[i][j] = INT_MAX;if (m_map[i][j] == 'S') {srow = i; scol = j;}if (m_map[i][j] == 'G') {erow = i; ecol = j;}}}queue<PII> que;que.push(PII(srow, scol));m_dis[srow][scol] = 0;while (!que.empty()) {PII pos = que.front();que.pop();if (pos == PII(erow, ecol)) break;//相比较于深度优先搜索算法要回到初始状态，就是所谓的有借有还for (int i = 0; i < 4; i++) {int newx = pos.first + dirs[i][0], newy = pos.second + dirs[i][1];if (newx >= 0 && newx < m_rows && newy >= 0 && newy < m_cols&& m_map[newx][newy] != '#'&& m_dis[newx][newy] == INT_MAX) {que.push(PII(newx, newy));//m_rou.push_back(PII(newx, newy));m_dis[newx][newy] = m_dis[pos.first][pos.second] + 1;}}}return m_dis[erow][ecol];}};int main() {Solution so;cin >> so.m_rows >> so.m_cols;for (int i = 0; i < so.m_rows; i++) {for (int j = 0; j < so.m_cols; j++) {cin >> so.m_map[i][j];}}int res = so.bfs();//输出ressystem("pause");return 0;}
注意：广度优先算法没法输出路径，因为他自己也不知道他咋走过来的，只知道为啥走过了。不过硬要输出也可以，神麻烦，我记得博客里有琦玉写了方法方法
总结
两种遍历搜索都需要一个或者多个数组存贮搜索状态是否经过，或者存储一些别的要求。这个是很重要的。
