一：BFS和DFS

  • 两者之间关于最短性和不具有最短性的区别，从顶点到最左下角的顶点，如果是BFS因为那条边的加入，最短路径是2，DFS的是4
  • DFS的空间复杂度很明显是树的高度决定，对于BFS很明显就是根据树的宽度决定的。

image.png

DFS的核心：递归边界，访问，递归循环，还原

二：DFS输出全排列

  1. #include <iostream>
  3. using namespace std;
  5. const int N = 10; // 题目要求的
  6. int n;
  7. int path[N], st[N]; // path存储的实际输出的内容， st存储已经被使用的点
  9. void dfs(int s){
  10.     if (s > n) // 这里根据main中dfs（）传入的值确定
  11.     {
  12.         for (int i = 1; i <= n; i++) // dfs传入的初始值是0，i就需要从0开始遍历，因为传入的是1，从1开始遍历
  13.             cout << path[i] << " "; 
  14.         cout << endl;
  15.         return;
  16.     }
  17.     for (int i = 1; i <= n; i++) // 遍历所有的数字，看哪些数字没有使用过。
  18.     {
  19.         if (!st[i]) // st的作用就是看哪些没有用到
  20.         {
  21.             path[s] = i; // 注意下标是传入的s不是i
  22.             st[i] = 1; // 用1标识这个数字已经用过了
  23.             dfs(s + 1); // 下一位的选择
  24.             st[i] = 0; // 回溯过程的体现，还原，path不用还原因为path就会被覆盖
  25.         }
  26.     }
  27. }
  29. int main()
  30. {
  31.     ios::sync_with_stdio(false);
  32.     cin >> n;
  33.     dfs(1);
  34.     return 0;
  35. }

三：DFS之N-皇后问题

image.png
image.png
首先弄清楚，如果使用下标从0开始，输出的时候不能用puts(p[i]),因为输出总是有问题，puts输出没办法控制二维，只能傻瓜式输出一维，而且puts括号内只能是指针或者数组名，puts输出的内容只要遇到/0的时候就输出错误，这也是如果初始化的时候，如果只初始化二维的第二个元素，0号位置的不管，通过puts的时候输出失败的原因。
image.png

  • 还要注意的就是斜线跟横纵坐标的关系，跟下标从什么开始也不太一样，反斜线也是有一定关系的(下标0开始：列+ n - 行 )。
  • 本质的递归边界，访问，递归，还原没有变，但是传递的起始值是发生变化的
  1. #include <iostream>
  3. using namespace std;
  5. const int N = 20; //  斜对角线的数目是行、列的 2n - 1
  6. char g[N][N];
  7. bool col[N], dg[N], udg[N]; // col记录列占用，dg记录\对角线，udg记录/对角线
  8. int n;
  10. void dfs(int u)
  11. {
  12.     if (u == n)
  13.     {
  14.         for (int i = 0; i < n; i++) puts(g[i]); // 可以通过输出一维元素输出内容
  15.         puts("");
  16.         return;
  17.     }
  19.     for (int i = 0; i < n; i++)
  20.     {
  21.         if (!col[i] && !dg[i + u] && !udg[i - u + n]) // 当前列，斜线，反斜线全部都没有被占用
  22.         {
  23.             col[i] = dg[i + u] = udg[i - u + n] = true;
  24.             g[u][i] = 'Q';
  25.             dfs(u + 1);
  26.             col[i] = dg[i + u] = udg[i - u + n] = false;
  27.             g[u][i] = '.';
  28.         }
  29.     }
  30. }
  32. int main()
  33. {
  34.     cin >> n;
  35.     for (int i = 0; i < n; i++)
  36.         for (int j = 0; j < n; j++)
  37.             g[i][j] = '.';
  39.     dfs(0);
  40.     return 0;
  41. }

四：BFS

  • 迷宫问题如果使用深度优先搜索的话，能保证搜到，但是不能保证搜到的路径是最短的。
  • 需要注意BFS虽然可以解决最短路，但是局限性在于只能解决所有边权都是1的时候

image.png

  • memset的初始化image.png
  • 基本思路就是把g图中所有的0的点依次放入队列q中，然后计算出每个点到起点的距离，因为最终只需要最右下角的点，所以只需要返回d[n - 1][m - 1];
  1. #include <iostream>
  2. #include <cstring>
  4. using namespace std;
  6. typedef pair<int, int> PII; // 用来存储x, y
  7. const int N = 110; 
  8. int g[N][N], d[N][N];  // g存储整个图形，d存储图中为0的点到原点的距离
  9. PII q[N * N]; // 作为队列，一次放入所有的0的点，计算距离
  10. int n, m; 
  12. int bfs()
  13. {
  14.     int hh = 0, rr = 0;
  15.     memset(d, -1, sizeof d); // memset初始化的时候，sizeof d就是按照d一个元素大小初始化，最小是字节
  16.     d[0][0] = 0; // 起始点距离肯定是0
  17.     q[0] = {0, 0}; 队列自然存储的是第一个点的坐标
  19.     int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; // 某个点上下左右四个点的坐标
  21.     while (hh <= rr)
  22.     {
  23.         auto u = q[hh++];
  24.         for(int i = 0; i < 4; i++)
  25.         {
  26.             int x = u.first + dx[i], y = u.second + dy[i];
  27.             if (x >= 0 && x < n && y >= 0 && y < m && d[x][y] == -1 && g[x][y] == 0) // 前四个条件不能越界，后面是g必须是0，而且距离是没有被计算
  28.             {
  29.                 d[x][y] = d[u.first][u.second] + 1;
  30.                 q[++rr] = {x, y};
  31.             }
  32.         }
  33.     }
  34.     return d[n - 1][m - 1];
  35. }
  37. int main()
  38. {
  39.     cin >> n >> m;
  40.     for (int i = 0; i < n; i++)
  41.         for (int j = 0; j < m; j++)
  42.             cin >> g[i][j];
  43.     cout << bfs() << endl;
  44.     return 0;
  45. }