【算法】复习搜索与图论

🍎 博客主页：🌙@披星戴月的贾维斯
🍎 欢迎关注：👍点赞🍃收藏🔥留言
🍇系列专栏：🌙 蓝桥杯
🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得，但是请相信，世界上总有一些美好值得我们全力以赴，哪怕粉身碎骨！🌙
🍉一起加油，去追寻、去成为更好的自己！

提示：以下是本篇文章正文内容，下面案例可供参考

---

前言

    深度遍历算法（depth first search）俗称dfs和 广度优先遍历（broad first search）俗称bfs以及我们常听到的图论里面的最短路问题，借着这篇文章我们一起深入了解一下这些算法的逻辑和解法。

🍎1.中国象棋中的马的行动

题目描述

在中国象棋中，马的行动方式是“日”字形。假设我们有一个 8x8 的棋盘，棋盘的左上角是(0,0)，右下角是(7,7)。马开始时位于给定的位置(x,y)，你的任务是计算马需要多少步才能到达目标位置(a,b)。如果马不能到达目标位置，就返回-1。

注意：马只能按照“日”字形行动，即先向上或向下移动两步，然后向左或向右移动一步，或者先向左或向右移动两步，然后向上或向下移动一步。

输入格式

输入共两行，每行包含两个整数。第一行是马的初始位置(x,y)，第二行是马的目标位置(a,b)。所有的整数都在0到7之间。

输出格式

输出一个整数，表示马到达目标位置需要的最少步数。如果不能到达，就输出-1。
输入输出样例
0 0；
7 7；

输出样例：
6

老规矩， 我们要养成一个好的写程序习惯，那就是先写思路，再写实现过程

解题思路：
    首先，我们可以通过看数据范围大致判断这一题用到的算法，数据范围才8，可以支持dfs,bfs,dp等等各种算法，而且我们读题可以知道，🐎的行动方式是“日”字形，即可以画图得出它的方向图

即我们可以设置一个距离数组，通过bfs去枚举这八个方向，算出初始点到各个可能到达点的距离，我们通过队列来存储可能到达的下一个点，如果队列里面没有数字了就代表遍历结束，返回值。
代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define x first
#define y second
bool st[10][10];
int d[10][10];
int a1, b1, a2, b2;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int bfs(int x, int y)
{queue<pii> q;q.push({x, y});//把点放入队列st[x][y] = true;//标记while(q.size()){auto t = q.front();q.pop();if(t.x == a2 && t.y == b2) return d[a2][b2];//如果找到直接返回距离数组for(int i = 0; i < 8; i++){int ax = t.x + dx[i], ay = t.y + dy[i];if(ax < 0 || ax > 7  || ay < 0 || ay > 7 || st[ax][ay] == true) continue;st[ax][ay] = true;d[ax][ay]=d[t.x][t.y]+1;q.push({ax, ay});}}return -1;//如果找不到就返回-1
}
int main ()
{cin >> a1 >> b1;cin >> a2 >> b2;int t = bfs(a1, b1);cout << t << endl; return 0;
}

写法2：dfs深度搜索

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define x first
#define y second
bool st[10][10];
int dist[10][10];
int a1, b1, a2, b2;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
void dfs(int x, int y)
{if(x == a2 && y == b2) return;//判断结束条件for(int i = 0; i <= 7; i++){int tx = x + dx[i];int ty = y + dy[i];if(tx < 0 || tx > 7 || ty < 0 || ty > 7)continue;if(dist[tx][ty] > dist[x][y] + 1){dist[tx][ty] = dist[x][y] + 1;dfs(tx, ty);}}return;
}
int main ()
{cin >> a1 >> b1;cin >> a2 >> b2;memset(dist, 0x3f, sizeof dist); //先将方向数组置为0x3fdist[a1][b1] = 0;dfs(a1, b1);if(dist[a2][b2] == 0x3f3f3f3f) cout << "-1" << endl;//如果没有搜到就输出-1else cout << dist[a2][b2] << endl;//否则输出距离return 0;
}

学习搜索我还推荐大家去看走迷宫和红与黑这两题，都是比较经典的。

🍎2.Dijkstra求最短路 I(图论)

题目描述

由于题目复制会乱码，所以博主干脆用图片代替。

图论问题和dp问题的区别

dp是选择下一个数（选择下一个状态）

图论是选择这个小的点去更新后继的节点

如下图例子：

在这个例子中，我们把已经确定的最短的距离标为绿色，这时候我们t = 2这个节点，发现3这个节点 的距离到原点是4大于2 + 1，更新3和节点1的最短距离。
代码示例：

dist数组存储的是第一个节点到第 j个节点的距离是累加的

#include<bits/stdc++.h>
using namespace std;
//存稠密图用邻接矩阵
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];int dijkstar()
{memset(dist, 0x3f, sizeof dist); // 1、先初始化距离dist[1] = 0; //1号点到自己的距离为0for(int i = 0; i < n; i++){int t = -1;for(int j = 1; j <= n; j++) //遍历所有点{if(!st[j] && (t == -1 || dist[t] > dist[j]))//如果j没有遍历过和t == -1或者t这点的距离>j的距离，更新tt = j;}st[t] = true;for(int j = 1; j <= n; j++){dist[j] = min(dist[j], dist[t] + g[t][j]);//g的ab是a 到b 点的距离}}if(dist[n] == 0x3f3f3f3f) return -1;else return dist[n];}
int main ()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m; //n个点m条边memset(g, 0x3f, sizeof g);while(m --){int a, b, c;cin >> a >> b >> c;g[a][b] = min(g[a][b], c);}int h = dijkstar();cout << h << endl;return 0;
}

🍎3.Dijkstra求最短路 II

思路：n的数据范围从500 到了 1.5 * 10的五次方，数据量一下子变得很大，用邻接矩阵去存储很容易爆内存，而且会超时，所以要用邻接表去存。而且为了提高效率，我们要用优先级队列。
时间复杂度m*logn

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define x first
#define y secondtypedef pair<int, int> pii;
int h[N], ne[N], e[N], idx, w[N];
int n, m;
bool st[N];
int dist[N];
void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] =idx++;
}
int dijkstart()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<pii, vector<pii>, greater<pii>> q;q.push({0, 1}); //1号点，距离是0，编号是1while(q.size()){auto t = q.top();q.pop();int ver = t.y, d = t.x; if(st[ver]) continue; //说明遍历过了st[ver] = true; //标记for(int i = h[ver]; i!= -1; i = ne[i]){int j = e[i];//当前节点if(dist[j] > d + w[i]){dist[j] = d + w[i];q.push({dist[j], j});}}}if(dist[n] == 0x3f3f3f3f) return -1;else return dist[n];
}
int main ()
{memset(h, -1, sizeof h);cin >> n >> m;while(m --){int a, b, c;cin >> a >> b >> c;add(a, b, c);}int h = dijkstart();cout << h << endl;return 0;
}

🍎4. spfa求最短路

如果说边的距离全部都是正的，我们用dijkstart算法，那么如果存在负边权，那么我们可以采用spfa算法，而且spfa算法效率会高很多，时间复杂度是0(n * m)。同样，我们可以用spfa算法解决之前dijkstart算法的题，spfa的写法很像上一道题，利用邻接表去存储，然后利用队列把距离短的点存储起来，然后去更新后继节点。但是我可能会比较嫌弃邻接表写法比较复杂，我们可以用vector<结构体>这样的形式来存储图。
代码示例：

#include<bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m;
struct Node
{int node;int w;
};
int dist[N];
bool st[N];vector<Node> g[N];//二维的数组
int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q; //队列存储所有待更新的点q.push(1); //把1号点放入队列st[1] = true;// st数组存当前这个点是否在队列当中while(q.size()){int t = q.front();//每次取出队头q.pop();st[t] = false;//更新所有领边for(int i = 0; i < g[t].size(); i ++){int j = g[t][i].node;if(dist[j] > dist[t] + g[t][i].w){dist[j] = dist[t] +  g[t][i].w;if(!st[j]){q.push(j);st[j] = true;}}}}return dist[n];
}
int main ()
{cin >> n >> m;while(m --){int a, b, c;cin >> a >> b >> c;g[a].push_back({b, c});}int t = spfa();if(t == 0x3f3f3f3f) cout << "impossible";else cout << t << endl;return 0;
}

🍎总结

    本文和大家介绍了几题搜索和图论的题目，既帮助了自己复习，也希望对读者有所帮助！