1.bfs
给定一个 n×n 的二维数组，如下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
数据保证至少存在一条从左上角走到右下角的路径。
对于上图则输出如下路径：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
思想
模板都是用数组模拟邻接表，也可以用vector<vector<>>模拟邻接表。
二叉树中有bfs的详细代码，就是二叉树层序遍历，那是比较普遍的写法。
bfs就是一次将所有子结点入队，依次出队扩展新的子节点入队，同时要标记已入队的结点，避免重复入队。
模板
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
PII pre[N][N];//保存搜索过程中上一步的坐标
bool g[N][N];
int n;
void bfs(PII start){
int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};//四个方向
queue<PII> q;
q.push(start);
memset(pre,-1,sizeof pre);//为-1表示此处还没搜过
pre[n-1][n-1] = {n-1,n-1};
while(q.size()){
PII t = q.front();//当前位置
q.pop();
int tx = t.first, ty = t.second;
for(int i = 0; i < 4; i++){//向四个方向探索下一步
int x = tx + dx[i], y = ty + dy[i];
if(x<0||x>=n||y<0||y>=n||g[x][y]||pre[x][y].first!=-1) continue;
q.push({x,y}),pre[x][y] = {tx,ty};//保存该步信息
}
}
PII end({0,0});
while(true){
int x = end.first, y = end.second;
printf("%d %d\n",x,y);
if(x==n-1&&y==n-1) break;
end = pre[x][y];
}
}
int main(){
scanf("%d",&n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) scanf("%d",&g[i][j]);
PII end({n-1,n-1});
bfs(end);//逆着搜(从终点向起点搜) 方便输出路径
return 0;
}
2.有向图的拓扑排序
给定一个n个点m条边的有向图，请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。
若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。
输入样例：
3 3（指3个点3条边）
1 2
2 3
1 3
输出样例：
1 2 3
思想
- 首先，拓扑排序是有向图的排序。我们用数组模拟队列，将所有入度为0的结点序号入队，然后将这些结点依次出队，并将它们的相邻边减去，即将相邻边的入度减一，如果入度减为零的话，则将该相邻边入队。重复这一过程，直到队列为空。
如果模拟队列的数组中元素个数为n个，即队尾指向下标n-1，队头指向下标n，则结点全部入队，说明无环，即所有结点的入度减为0。否则有环，因为环上任意结点入队都依赖环的前一个结点的出边被减去，而前一个结点依赖于后一结点，互相依赖，都不能入队，队列中入队元素的个数小于n。 - 可以把dfs转化为一颗树来考虑，即可大致理解这一算法。
bfs 不断删除入度为0的点
bool topsort(){
int hh = 0, tt = -1;//数组模拟队列
for(int i = 1; i <= n; i++){//将所有入度为0的入队
if(!ind[i]) q[++tt] = i;//ind[i]表示节点i的入度
}
while(hh<=tt){
int t = q[hh++];
for(int i = h[t]; i!=-1; i = ne[i]){
int j = e[i];
if(--ind[j]==0) q[++tt] = j;
}
}
return tt==n-1;//如果节点全部入队 说明无环
//若返回true,则可输出拓扑序列，即入队顺序
//for(int i = 0; i < n; i++) cout<<q[i]<<" ";
}
dfs 利用dfs序 按dfs序从大到小输出点
int dfstime = 0;//dfs序(即dfs过程中 搜索结束的时间)
vector<pair<int,int> > ans;
int st[N];// -1 表示搜索完毕 1表示该轮dfs还没结束
bool dfs(int u){//给出dfs序以及返回是否有环
if(st[u]==-1) return false;//对于已经搜索完毕了点 无需搜
if(st[u]==1) return true;//因为该点在当前轮搜到过 而现在又来了 第二次到达 说明存在环
st[u] = 1;//当前轮开始访问
dfstime++;//时间+1 到达u
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(dfs(j)) return true;//邻接点存在环
}
st[u] = -1;//以u为起点的dfs访问完毕
ans.push_back({-dfstime,u});//记录该点的退出时间(dfs序) 变为负数 方便从大到小排序
return false;//不存在环
}
bool topsort_dfs(){
for(int i = 1; i <= n; i++){
if(st[i]!=-1){
if(dfs(i)) return false;//发现该连通分量有环 拓扑失败
}
}
sort(ans.begin(),ans.end());
for(auto v : ans){
cout<<v.second<<" ";
}
return true;
}
3.Dijkstra求最短路
给定一个n个点m条边的有向图, 请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
思想
- dijkstra是基于贪心的，所谓贪心，就是只要当前元素的局部最优，不管整体是否最优。显然，贪心很少达成整体最优，但是dijkstra是整体最优的。
- 流程往往是手动模拟的，我们只需把手动模拟的过程与之对应即可。
- 这是朴素版的dijkstra算法，可以用堆优化dijkstra算法，原因如下：
①堆可以动态维护一个集合中的最小值。
②堆动态支持插入、删除、改变一个数。
时间复杂度：O(mlog n)
朴素版的dijkstra适用于稠密图，即边多的图，常用邻接矩阵存储。堆优化版的适用于稀疏图，即边少的图，常用邻接表存储。
int n/*点数*/,m /*边数*/;
int g[N][N];//邻接矩阵，存储边
int dist[N];//存储每条边到原点的距离
bool st[N];//记录当前点是否已被用来更新
int dijkstra(){
memset(dist,0x3f,sizeof(dist));//每条边到原点的距离初始化成正无穷
dist[1]=0;
for(int i=0;i<n-1;i++){
//找出剩下点中距离原点最小的点
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
st[t]=true;
//从1号点到j号点的距离能否用经过t的一条路径来更新
//即1->j能否用1->t和t->j路径来更新
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
4.最小生成树
给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。输出最小生成树的权重之和
思想
- prim算法非常类似于dijkstra算法，因为它们的思想都是贪心。kruskal算法也运用了贪心，它对所有的边进行排序，确保小的边先被合并。
- kruskal算法是基于并查集，快速判断当前边的两个结点是否在同一集合内，若该条边上两个结点不在同一集合内，则将其所在的两个集合合并。
prim算法
const int INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
int d[N];//每个点距离生成树的距离
bool st[N];
int prim(){
memset(d,0x3f,sizeof d);
int res = 0;//最小生成树的权重之和
for(int i = 0; i < n; i++){
int t = -1;
for(int j = 1; j <= n; j++)
if(!st[j]&&(t==-1||d[t] > d[j])) t = j; //找出剩下点中距离最小的点
if(i&&d[t]==INF) return -1;//说明不联通,则不存在
st[t] = true;
if(i) res += d[t];//纳入该边权重，除了起点
for(int j = 1; j <= n; j++){
if(!st[j]&&d[j] > g[t][j]) d[j] = g[t][j];
}
}
return res;
}
kruskal算法
struct Edge{//边集
int a,b,w;
bool operator < (const Edge &E) const{//按权重从小到大排序
return w < E.w;
}
}e[N];
int n,m;
int p[N/2];//并查集数组 若p[i]=j 则表示i的父节点为j
int find(int x){//并查集 寻找x的根
if(x!=p[x]) p[x] = find(p[x]);//路径压缩版
return p[x];
}
int kruskal(){
sort(e,e+m);//把边按权重从小到大排序
int res = 0,cnt = 0;//最小生成树的权重之和，选择的边数
for(int i = 1; i <= n; i++) p[i] = i;//并查集初始化
for(int i = 0; i < m; i++){//从小到大选边
int x = find(e[i].a), y = find(e[i].b);
if(x!=y){//若该条边上两个结点不在同一集合内，则将其所在的两个集合合并
p[x] = y;
cnt++;
res += e[i].w;//纳入该边
}
}
return cnt==n-1 ? res:0x3f3f3f3f;//最终要选够n-1条边
}
5.floyd求最短路
求出所有点对之间的最短距离
思想
这个算法基于动态规划思想，看起来简单，实际上很复杂。所以略过，一般不需要掌握，可以背下来。
int d[N][N];//邻接矩阵，保存任意两点间的最短距离
int n,m;
void floyd(){
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j= 1; j <= n; j++){
d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
}
}
}
}