当前位置：首页 > article >正文

算法刷题笔记——图论篇

article 2025/1/20 23:49:21

这里写目录标题

理论基础
- 图的基本概念
- - 图的种类
  - 度
- 连通性
- - 连通图
  - 强连通图
  - 连通分量
  - 强连通分量
- 图的构造
- - 邻接矩阵
  - 邻接表
- 图的遍历方式
深度优先搜索理论基础
- dfs 与 bfs 区别
- dfs 搜索过程
- 深搜三部曲
- 所有可达路径
- 广度优先搜索理论基础
- - 广搜的使用场景
  - 广搜的过程
- 岛屿数量
- 孤岛的总面积
- 沉没孤岛
- 水流问题
- 建造最大岛屿
- 字符串接龙
- 有向图的完全可达性
- 岛屿的周长
并查集理论基础
- 背景
- 原理讲解
- 路径压缩
- 代码模板
- 寻找存在的路径
- prim算法
- kruskal算法精讲
- 拓扑排序精讲
- dijkstra（朴素版）精讲
- Bellman_ford 算法精讲
- Bellman_ford 队列优化算法（又名SPFA）
- bellman_ford之判断负权回路
- bellman_ford之单源有限最短路
- Floyd 算法精讲
- A * 算法精讲（A star算法）
总结
- 深搜与广搜
- - 注意事项
- 并查集
- 最小生成树
- 拓扑排序
- 最短路算法

理论基础

图的基本概念

二维坐标中，两点可以连成线，多个点连成的线就构成了图。
当然图也可以就一个节点，甚至没有节点（空图）

图的种类

整体上一般分为有向图和无向图。
有向图是指图中边是有方向的：
在这里插入图片描述
无向图是指图中边没有方向：

加权有向图，就是图中边是有权值的，例如：

加权无向图也是同理。

度

无向图中有几条边连接该节点，该节点就有几度。
例如，该无向图中，节点4的度为5，节点6的度为3。
在这里插入图片描述
在有向图中，每个节点有出度和入度。
出度：从该节点出发的边的个数。
入度：指向该节点边的个数。
例如，该有向图中，节点3的入度为2，出度为1，节点1的入度为0，出度为2。

连通性

在图中表示节点的连通情况，我们称之为连通性。

连通图

在无向图中，任何两个节点都是可以到达的，我们称之为连通图，如图：
在这里插入图片描述
如果有节点不能到达其他节点，则为非连通图，如图：

节点1 不能到达节点4。

强连通图

在有向图中，任何两个节点是可以相互到达的，我们称之为强连通图。
这里有录友可能想，这和无向图中的连通图有什么区别，不是一样的吗？
我们来看这个有向图：
在这里插入图片描述
这个图是强连通图吗？
初步一看，好像这节点都连着呢，但这不是强连通图，节点1 可以到节点5，但节点5 不能到节点1 。
强连通图是在有向图中任何两个节点是可以相互到达
下面这个有向图才是强连通图：
在这里插入图片描述

连通分量

在无向图中的极大连通子图称之为该图的一个连通分量。
只看概念大家可能不理解，我来画个图：
在这里插入图片描述
该无向图中节点1、节点2、节点5 构成的子图就是该无向图中的一个连通分量，该子图所有节点都是相互可达到的。
同理，节点3、节点4、节点6 构成的子图也是该无向图中的一个连通分量。
那么无向图中节点3 、节点4 构成的子图是该无向图的联通分量吗？
不是！
因为必须是极大联通子图才能是连通分量，所以必须是节点3、节点4、节点6 构成的子图才是连通分量。
在图论中，连通分量是一个很重要的概念，例如岛屿问题（后面章节会有专门讲解）其实就是求连通分量。

强连通分量

在有向图中极大强连通子图称之为该图的强连通分量。
如图：
在这里插入图片描述
节点1、节点2、节点3、节点4、节点5 构成的子图是强连通分量，因为这是强连通图，也是极大图。
节点6、节点7、节点8 构成的子图不是强连通分量，因为这不是强连通图，节点8 不能达到节点6。
节点1、节点2、节点5 构成的子图也不是强连通分量，因为这不是极大图。

图的构造

我们如何用代码来表示一个图呢？
一般使用邻接表、邻接矩阵或者用类来表示。
主要是朴素存储、邻接表和邻接矩阵。

邻接矩阵

邻接矩阵使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
例如： grid[2][5] = 6，表示节点 2 连接节点5 为有向图，节点2 指向节点5，边的权值为6。
如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与节点5 相互连通，权值为6。
如图：
在这里插入图片描述
在一个 n （节点数）为8 的图中，就需要申请 8 * 8 这么大的空间。
图中有一条双向边，即：grid[2][5] = 6，grid[5][2] = 6
这种表达方式（邻接矩阵）在边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费。
而且在寻找节点连接情况的时候，需要遍历整个矩阵，即 n * n 的时间复杂度，同样造成时间浪费。

邻接矩阵的优点：

表达方式简单，易于理解
检查任意两个顶点间是否存在边的操作非常快
适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：

遇到稀疏图，会导致申请过大的二维数组造成空间浪费且遍历边的时候需要遍历整个n * n矩阵，造成时间浪费

邻接表

邻接表使用数组 + 链表的方式来表示。邻接表是从边的数量来表示图，有多少边才会申请对应大小的链表。
邻接表的构造如图：
在这里插入图片描述
这里表达的图是：

节点1 指向节点3 和节点5
节点2 指向节点4、节点3、节点5
节点3 指向节点4
节点4指向节点1

有多少边邻接表才会申请多少个对应的链表节点。
从图中可以直观看出使用数组 + 链表来表达边的连接情况。

邻接表的优点：

对于稀疏图的存储，只需要存储边，空间利用率高
遍历节点连接情况相对容易

缺点：

检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
实现相对复杂，不易理解
以上大家可能理解比较模糊，没关系，因为大家还没做过图论的题目，对于图的表达没有概念。

图的遍历方式

图的遍历方式基本是两大类：

深度优先搜索（dfs）
广度优先搜索（bfs）

在讲解二叉树章节的时候，其实就已经讲过这两种遍历方式。
二叉树的递归遍历，是dfs 在二叉树上的遍历方式。
二叉树的层序遍历，是bfs 在二叉树上的遍历方式。
dfs 和 bfs 一种搜索算法，可以在不同的数据结构上进行搜索，在二叉树章节里是在二叉树这样的数据结构上搜索。
而在图论章节，则是在图（邻接表或邻接矩阵）上进行搜索。

深度优先搜索理论基础

dfs 与 bfs 区别

提到深度优先搜索（dfs），就不得不说和广度优先搜索（bfs）有什么区别
先来了解dfs的过程，很多录友可能对dfs（深度优先搜索），bfs（广度优先搜索）分不清。
先给大家说一下两者大概的区别：

dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。
当然以上讲的是，大体可以这么理解，接下来我们详细讲解dfs，（bfs在用单独一篇文章详细讲解）

dfs 搜索过程

上面说道dfs是可一个方向搜，不到黄河不回头。那么我们来举一个例子。

如图一，是一个无向图，我们要搜索从节点1到节点6的所有路径。
在这里插入图片描述
那么dfs搜索的第一条路径是这样的：（假设第一次延默认方向，就找到了节点6），图二

此时我们找到了节点6，（遇到黄河了，是不是应该回头了），那么应该再去搜索其他方向了。如图三：

路径2撤销了，改变了方向，走路径3（红色线），接着也找到终点6。那么撤销路径2，改为路径3，在dfs中其实就是回溯的过程（这一点很重要，很多录友不理解dfs代码中回溯是用来干什么的）

又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图四中，路径4撤销（回溯的过程），改为路径5。
在这里插入图片描述
又找到了一条从节点1到节点6的路径，又到黄河了，此时再回头，下图图五，路径6撤销（回溯的过程），改为路径7，路径8 和路径7，路径9，结果发现死路一条，都走到了自己走过的节点。

那么节点2所连接路径和节点3所链接的路径都走过了，撤销路径只能向上回退，去选择撤销当初节点4的选择，也就是撤销路径5，改为路径10 。如图图六：
在这里插入图片描述
上图演示中，其实我并没有把所有的从节点1 到节点6的dfs（深度优先搜索）的过程都画出来，那样太冗余了，但已经把dfs 关键的地方都涉及到了，关键就两点：

搜索方向，是认准一个方向搜，直到碰壁之后再换方向
换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。

深搜三部曲

在二叉树递归讲解中，给出了递归三部曲。
回溯算法讲解中，给出了回溯三部曲。
其实深搜也是一样的，深搜三部曲如下：

确认递归函数，参数

void dfs(参数)

通常我们递归的时候，我们递归搜索需要了解哪些参数，其实也可以在写递归函数的时候，发现需要什么参数，再去补充就可以。

一般情况，深搜需要二维数组数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，我们可以定义一个全局变量，避免让我们的函数参数过多。

例如这样：

vector<vector<int>> result; // 保存符合条件的所有路径
vector<int> path; // 起点到终点的路径
void dfs (图，目前搜索的节点)

但这种写法看个人习惯，不强求。

确认终止条件

终止条件很重要，很多同学写dfs的时候，之所以容易死循环，栈溢出等等这些问题，都是因为终止条件没有想清楚。

if (终止条件) {
    存放结果;
    return;
}

终止添加不仅是结束本层递归，同时也是我们收获结果的时候。

另外，其实很多dfs写法，没有写终止条件，其实终止条件写在了，下面dfs递归的逻辑里了，也就是不符合条件，直接不会向下递归。这里如果大家不理解的话，没关系，后面会有具体题目来讲解。

处理目前搜索节点出发的路径

一般这里就是一个for循环的操作，去遍历目前搜索节点所能到的所有节点。

for (选择：本节点所连接的其他节点) {
    处理节点;
    dfs(图，选择的节点); // 递归
    回溯，撤销处理结果
}

不少录友疑惑的地方，都是 dfs代码框架中for循环里分明已经处理节点了，那么 dfs函数下面为什么还要撤销的呢。

如图七所示，路径2 已经走到了目的地节点6，那么路径2 是如何撤销，然后改为路径3呢？其实这就是回溯的过程，撤销路径2，走换下一个方向。
在这里插入图片描述

所有可达路径

本题是深度优先搜索的基础题目

深搜三部曲来分析题目：
确认递归函数，参数
首先我们dfs函数一定要存一个图，用来遍历的，需要存一个目前我们遍历的节点，定义为x。
还需要存一个n，表示终点，我们遍历的时候，用来判断当 x==n 时候标明找到了终点。
（其实在递归函数的参数不容易一开始就确定了，一般是在写函数体的时候发现缺什么，参加就补什么）
至于单一路径和路径集合可以放在全局变量
确认终止条件
什么时候我们就找到一条路径了？
当目前遍历的节点为最后一个节点 n 的时候就找到了一条从出发点到终止点的路径。
处理目前搜索节点出发的路径
接下来是走当前遍历节点x的下一个节点。
首先是要找到 x节点指向了哪些节点呢？遍历方式是这样的：

for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
    if (graph[x][i] == 1) { // 找到 x指向的节点，就是节点i
    }
}

接下来就是将选中的x所指向的节点，加入到单一路径来。

path.push_back(i); // 遍历到的节点加入到路径中来

进入下一层递归

dfs(graph, i, n); // 进入下一层递归

最后就是回溯的过程，撤销本次添加节点的操作。

为什么要有回溯，我在图论深搜理论基础也有详细的讲解。

该过程整体代码：

for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
    if (graph[x][i] == 1) { // 找到 x链接的节点
        path.push_back(i); // 遍历到的节点加入到路径中来
        dfs(graph, i, n); // 进入下一层递归
        path.pop_back(); // 回溯，撤销本节点
    }
}

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void dfs(const vector<vector<int>>& graph,int x,int n){
    if(x==n){
        result.push_back(path);
        return;
    }
    for(int i=1;i<=n;i++){
        if(graph[x][i]==1){
            path.push_back(i);
            dfs(graph,i,n);
            path.pop_back();
        }
    }
}
int main(){
    int n,m,s,t;
    cin>>n>>m;
    vector<vector<int>> graph(n+1,vector<int>(n+1,0));
    for(int i=0;i<m;i++){
        cin>>s>>t;
        graph[s][t]=1;
    }
    path.push_back(1);
    dfs(graph,1,n);
    if(result.size()==0){
        std::cout << -1 << std::endl;
    }
    for(const vector<int> &pa:result){
        for(int i=0;i<pa.size()-1;i++){
            cout<<pa[i]<<" ";
        }
        cout<<pa[pa.size()-1]<<endl;
    }
}

广度优先搜索理论基础

广搜的使用场景

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路。

当然，也有一些问题是广搜和深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。

广搜的过程

上面我们提过，BFS是一圈一圈的搜索过程，但具体是怎么一圈一圈来搜呢。

我们用一个方格地图，假如每次搜索的方向为上下左右（不包含斜上方），那么给出一个start起始位置，那么BFS就是从四个方向走出第一步。
在这里插入图片描述
如果加上一个end终止位置，那么使用BFS的搜索过程如图所示：

我们从图中可以看出，从start起点开始，是一圈一圈，向外搜索，方格编号1为第一步遍历的节点，方格编号2为第二步遍历的节点，第四步的时候我们找到终止点end。

正是因为BFS一圈一圈的遍历方式，所以一旦遇到终止点，那么一定是一条最短路径。
在第五步，第六步我只把关键的节点染色了，其他方向周边没有去染色，大家只要关注关键地方染色的逻辑就可以。

从图中可以看出，如果添加了障碍，我们是第六步才能走到end终点。

只要BFS只要搜到终点一定是一条最短路径，大家可以参考上面的图，自己再去模拟一下。
这一圈一圈的搜索过程是怎么做到的，是放在什么容器里，才能这样去遍历。

很多网上的资料都是直接说用队列来实现。

其实，我们仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。

用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。

因为队列是先进先出，加入元素和弹出元素的顺序是没有改变的。

如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。

因为栈是先进后出，加入元素和弹出元素的顺序改变了。

那么广搜需要注意转圈搜索的顺序吗？不需要！

所以用队列，还是用栈都是可以的，但大家都习惯用队列了，所以下面的讲解用我也用队列来讲，只不过要给大家说清楚，并不是非要用队列，用栈也可以。
下面给出广搜代码模板，该模板针对的就是，上面的四方格的地图：（详细注释）

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
    while(!que.empty()) { // 开始遍历队列里的元素
        pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
        int curx = cur.first;
        int cury = cur.second; // 当前节点坐标
        for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过
            if (!visited[nextx][nexty]) { // 如果节点没被访问过
                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }

}

岛屿数量

题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。也就是说斜角度链接是不算了

思路是用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。
在遇到标记过的陆地节点和海洋节点的时候直接跳过。这样计数器就是最终岛屿的数量。

深搜解法

#include<iostream>
#include<vector>
using namespace std;

int dir[4][2]={0,1,1,0,-1,0,0,-1};
void dfs(const vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){
    for(int i=0;i<4;i++){
        int nextx=x+dir[i][0];
        int nexty=y+dir[i][1];
        if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){
            continue;
        }
        if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){
            visited[nextx][nexty]=true;
            dfs(grid,visited,nextx,nexty);
        }
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    vector<vector<bool>> visited(n,vector<bool>(m,false));
    int result=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visited[i][j]&&grid[i][j]==1){
                visited[i][j]=true;
                result++;
                dfs(grid,visited,i,j);
            }
        }
    }
    std::cout << result << std::endl;
}

广搜解法

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int dir[4][2]={0,1,1,0,-1,0,0,-1};

void bfs(const vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y){
    queue<pair<int,int>> que;
    que.push({x,y});
    visited[x][y]=true;
    while(!que.empty()){
        pair<int,int> cur=que.front();
        que.pop();
        int curx=cur.first;
        int cury=cur.second;
        for(int i=0;i<4;i++){
            int nextx=curx+dir[i][0];
            int nexty=cury+dir[i][1];
            if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){
                continue;
            }
            if(!visited[nextx][nexty]&&grid[nextx][nexty]==1){
                    que.push({nextx,nexty});
                    visited[nextx][nexty]=true;
            
            }
        }
    }
    
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    vector<vector<bool>> visited(n,vector<bool>(m,false));
    int result=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visited[i][j]&&grid[i][j]==1){
            result++;
            bfs(grid,visited,i,j);
            }
        }
    }
    cout<<result<<endl;
}

孤岛的总面积

本题使用dfs，bfs，并查集都是可以的。

本题要求找到不靠边的陆地面积，那么我们只要从周边找到陆地然后通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图统计此时还剩下的陆地就可以了。
在这里插入图片描述
在遇到地图周边陆地的时候，将1都变为0，此时地图为这样：

然后我们再去遍历这个地图，遇到有陆地的地方，去采用深搜或者广搜，边统计所有陆地。
dfs

#include<iostream>
#include<vector>
using namespace std;

int dir[4][2]={-1,0,0,-1,1,0,0,1};
int count;
void dfs(vector<vector<int>>& grid,int x,int y){
    grid[x][y]=0;
    count++;
    for(int i=0;i<4;i++){
        int nextx=x+dir[i][0];
        int nexty=y+dir[i][1];
        if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){
            continue;
        }
        if(grid[nextx][nexty]==0){
            continue;
        }
        dfs(grid,nextx,nexty);
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    for(int i=0;i<n;i++){
        if(grid[i][0]==1){
            dfs(grid,i,0);
        }
        if(grid[i][m-1]==1){
            dfs(grid,i,m-1);
        }
    }
    for(int j=0;j<m;j++){
        if(grid[0][j]==1){
            dfs(grid,0,j);
        }
        if(grid[n-1][j]==1){
            dfs(grid,n-1,j);
        }
    }
    count=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]==1){
                dfs(grid,i,j);
            }
        }
    }
    std::cout << count << std::endl;
    
}

沉没孤岛

思路依然是从地图周边出发，将周边空格相邻的陆地都做上标记，然后在遍历一遍地图，遇到陆地且没做过标记的，那么都是地图中间的陆地，全部改成水域就行。

有的录友可能想，我在定义一个 visited 二维数组，单独标记周边的陆地，然后遍历地图的时候同时对数组board 和数组visited 进行判断，决定陆地是否变成水域。

这样做其实就有点麻烦了，不用额外定义空间了，标记周边的陆地，可以直接改陆地为其他特殊值作为标记。

步骤一：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）

步骤二：将水域中间 1 （陆地）全部改成水域（0）

步骤三：将之前标记的 2 改为 1 （陆地）
在这里插入图片描述

#include<iostream>
#include<vector>
using namespace std;

int dir[4][2]={-1,0,0,-1,1,0,0,1};
void dfs(vector<vector<int>>& grid,int x,int y){
    grid[x][y]=2;
    for(int i=0;i<4;i++){
        int nextx=x+dir[i][0];
        int nexty=y+dir[i][1];
        if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size()){
            continue;
        }
        if(grid[nextx][nexty]==0||grid[nextx][nexty]==2){
            continue;
        }
        dfs(grid,nextx,nexty);
    }
    return;
   
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    //步骤一
    for(int i=0;i<n;i++){
        if(grid[i][0]==1){
            dfs(grid,i,0);
        }
        if(grid[i][m-1]==1){
            dfs(grid,i,m-1);
        }
    }
    for(int j=0;j<m;j++){
        if(grid[0][j]==1){
            dfs(grid,0,j);
        }
        if(grid[n-1][j]==1){
            dfs(grid,n-1,j);
        }
    }
    //步骤二，步骤三
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]==1){
                grid[i][j]=0;
            }
            if(grid[i][j]==2){
                grid[i][j]=1;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            std::cout << grid[i][j] << " ";
        }
        cout<<endl;
    }
    
}

水流问题

一个比较直白的想法，其实就是遍历每个点，然后看这个点能不能同时到达第一组边界和第二组边界。

至于遍历方式，可以用dfs，也可以用bfs，以下用dfs来举例。
遍历每一个节点，是 m * n，遍历每一个节点的时候，都要做深搜，深搜的时间复杂度是： m * n

那么整体时间复杂度就是 O(m^2 * n^2) ，这是一个四次方的时间复杂度。

从第一组边界上的节点逆流而上，将遍历过的节点都标记上。

同样从第二组边界的边上节点逆流而上，将遍历过的节点也标记上。

然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。

从第一组边界边上节点出发，如图：
在这里插入图片描述
从第二组边界上节点出发，如图：

#include <iostream>
#include <vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
void dfs(vector<vector<int>>& grid, int x, int y) {
    grid[x][y] = 2;
    for (int i = 0; i < 4; i++) { // 向四个方向遍历
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        // 超过边界
        if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
        // 不符合条件，不继续遍历
        if (grid[nextx][nexty] == 0 || grid[nextx][nexty] == 2) continue;
        dfs (grid, nextx, nexty);
    }
    return;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    // 步骤一：
    // 从左侧边，和右侧边 向中间遍历
    for (int i = 0; i < n; i++) {
        if (grid[i][0] == 1) dfs(grid, i, 0);
        if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);
    }

    // 从上边和下边 向中间遍历
    for (int j = 0; j < m; j++) {
        if (grid[0][j] == 1) dfs(grid, 0, j);
        if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);
    }
    // 步骤二、步骤三
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) grid[i][j] = 0;
            if (grid[i][j] == 2) grid[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}

最终时间复杂度为 O(n * m) 。
空间复杂度为：O(n * m)

建造最大岛屿

每次深搜遍历计算最大岛屿面积，我们都做了很多重复的工作。

只要用一次深搜把每个岛屿的面积记录下来就好。

第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积

第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出选一个0变成1 之后的最大面积。

拿如下地图的岛屿情况来举例：（1为陆地）
在这里插入图片描述
第一步，则遍历题目，并将岛屿到编号和面积上的统计，过程如图所示：

第二步过程如图所示：

也就是遍历每一个0的方格，并统计其相邻岛屿面积，最后取一个最大值。

这个过程的时间复杂度也为 n * n。

所以整个解法的时间复杂度，为 n * n + n * n 也就是 n^2。

当然这里还有一个优化的点，就是可以不用 visited数组，因为有mark来标记，所以遍历过的grid[i][j]是不等于1的。

#include<iostream>
#include<vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int n,m;
int count;
int dir[4][2]={0,1,1,0,-1,0,0,-1};
void dfs(vector<vector<int>>& grid,vector<vector<bool>>& visited,int x,int y,int mark){
    if(visited[x][y]||grid[x][y]==0){
        return;
    }
    visited[x][y]=true;
    grid[x][y]=mark;
    count++;
    for(int i=0;i<4;i++){
        int nextx=x+dir[i][0];
        int nexty=y+dir[i][1];
        if(nextx<0||nextx>=n||nexty<0||nexty>=m){
            continue;
        }
        dfs(grid,visited,nextx,nexty,mark);
    }
}
int main(){
    cin>>n>>m;
    vector<vector<int>> grid(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    vector<vector<bool>> visited(n,vector<bool>(m,false));
    unordered_map<int,int> gridNum;
    int mark=2;
    bool isAllGrid=true;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]==0){
                isAllGrid=false;
            }
            if(!visited[i][j]&&grid[i][j]==1){
                count=0;
                dfs(grid,visited,i,j,mark);
                gridNum[mark]=count;
                mark++;
            }
        }
    }
    if(isAllGrid){
        std::cout << n*m << std::endl;
        return 0;
    }
    //根据添加陆地的位置，计算周边岛屿面积之和
    int result=0;
    unordered_set<int> visitedGrid;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            count=1;
            visitedGrid.clear();
            if(grid[i][j]==0){
                for(int k=0;k<4;k++){
                    int neari=i+dir[k][1];
                    int nearj=j+dir[k][0];
                    if(neari<0||neari>=n||nearj<0||nearj>=m){
                        continue;
                    }
                    if(visitedGrid.count(grid[neari][nearj])){
                        continue;
                    }
                    count+=gridNum[grid[neari][nearj]];
                    visitedGrid.insert(grid[neari][nearj]);
                }
            }
            result=max(result,count);
        }
    }
    cout<<result<<endl;
}

字符串接龙

从这个图中可以看出 abc 到 def的路线不止一条，但最短的一条路径上是4个节点。
在这里插入图片描述
本题只需要求出最短路径的长度就可以了，不用找出具体路径。

所以这道题要解决两个问题：

图中的线是如何连在一起的
起点和终点的最短路径长度

首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个。

所以判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。

然后就是求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。

本题如果用深搜，会比较麻烦，要在到达终点的不同路径中选则一条最短路。而广搜只要达到终点，一定是最短路。

另外需要有一个注意点：

本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
使用set来检查字符串是否出现在字符串集合里更快一些

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;
int main() {
    string beginStr, endStr, str;
    int n;
    cin >> n;
    unordered_set<string> strSet;
    cin >> beginStr >> endStr;
    for (int i = 0; i < n; i++) {
        cin >> str;
        strSet.insert(str);
    }

    // 记录strSet里的字符串是否被访问过，同时记录路径长度
    unordered_map<string, int> visitMap; // <记录的字符串，路径长度>

    // 初始化队列
    queue<string> que;
    que.push(beginStr);

    // 初始化visitMap
    visitMap.insert(pair<string, int>(beginStr, 1));

    while(!que.empty()) {
        string word = que.front();
        que.pop();
        int path = visitMap[word]; // 这个字符串在路径中的长度

        // 开始在这个str中，挨个字符去替换
        for (int i = 0; i < word.size(); i++) {
            string newWord = word; // 用一个新字符串替换str，因为每次要置换一个字符

            // 遍历26的字母
            for (int j = 0 ; j < 26; j++) {
                newWord[i] = j + 'a';
                if (newWord == endStr) { // 发现替换字母后，字符串与终点字符串相同
                    cout <<  path + 1 << endl; // 找到了路径 
                    return 0;
                }
                // 字符串集合里出现了newWord，并且newWord没有被访问过
                if (strSet.find(newWord) != strSet.end()
                        && visitMap.find(newWord) == visitMap.end()) {
                    // 添加访问信息，并将新字符串放到队列中
                    visitMap.insert(pair<string, int>(newWord, path + 1));
                    que.push(newWord);
                }
            }
        }
    }

    // 没找到输出0
    cout << 0 << endl;

}

有向图的完全可达性

本题给我们是一个有向图，意识到这是有向图很重要！

这就很容易让我们想起岛屿问题，只要发现独立的岛，就是不可到达的。

但本题是有向图，在有向图中，即使所有节点都是链接的，但依然不可能从0出发遍历所有边。

例如上图中，节点1 可以到达节点2，但节点2是不能到达节点1的。

所以本题是一个有向图搜索全路径的问题。只能用深搜（DFS）或者广搜（BFS）来搜。

以下dfs分析大家一定要仔细看，本题有两种dfs的解法，很多题解没有讲清楚。

深搜三部曲：

确认递归函数，参数

需要传入地图，需要知道当前我们拿到的key，以至于去下一个房间。
同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。

确认终止条件

遍历的时候，什么时候终止呢？
这里有一个很重要的逻辑，就是在递归中，我们是处理当前访问的节点，还是处理下一个要访问的节点。
这决定终止条件怎么写。
首先明确，本题中什么叫做处理，就是 visited数组来记录访问过的节点，该节点默认数组里元素都是false，把元素标记为true就是处理本节点了。

如果我们是处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。

如果我们是处理下一层访问的节点，而不是当前层。那么就要在深搜三部曲中第三步：处理目前搜索节点出发的路径的时候对节点进行处理。
这样的话，就不需要终止条件，而是在搜索下一个节点的时候，直接判断下一个节点是否是我们要搜的节点。

可以看出，如何看待我们要访问的节点，直接决定了两种不一样的写法，很多录友对这一块很模糊，可能做过这道题，但没有思考到这个维度上。

处理目前搜索节点出发的路径

其实在上面，深搜三部曲第二部，就已经讲了，因为终止条件的两种写法，直接决定了两种不一样的递归写法。

这里还有细节：

看上面两个版本的写法中，好像没有发现回溯的逻辑。

我们都知道，有递归就有回溯，回溯就在递归函数的下面，那么之前我们做的dfs题目，都需要回溯操作，为什么本题就没有回溯呢？

代码中可以看到dfs函数下面并没有回溯的操作。

此时就要在思考本题的要求了，本题是需要判断 1节点是否能到所有节点，那么我们就没有必要回溯去撤销操作了，只要遍历过的节点一律都标记上。

那什么时候需要回溯操作呢？

当我们需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”

#include<iostream>
#include<vector>
#include<list>
using namespace std;
void dfs(const vector<list<int>>& graph,int key,vector<bool>& visited){
    if(visited[key]){
        return;
    }
    visited[key]=true;
    list<int> keys=graph[key];// 获取节点key的所有邻接节点
    for(int key:keys){
        dfs(graph,key,visited);
    }
}
int main(){
    int n,k;
    cin>>n>>k;
    int s,t;
    vector<list<int>> graph(n+1);//邻接表
    while(k--){
        cin>>s>>t;
        graph[s].push_back(t);//graph[s]包含所有从节点s出发的边所指向的节点
    }
    vector<bool> visited(n+1,false);
    dfs(graph,1,visited);
    for(int i=1;i<=n;i++){
        if(visited[i]==false){
            std::cout << -1 << std::endl;
            return 0;
        }
    }
    cout<<1<<endl;
    
}

岛屿的周长

遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。

如果该陆地上下左右的空格是有水域，则说明是一条边，如图：
在这里插入图片描述
陆地的右边空格是水域，则说明找到一条边。

如果该陆地上下左右的空格出界了，则说明是一条边，如图：
在这里插入图片描述
该陆地的下边空格出界了，则说明找到一条边。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n,vector<int>(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
        }
    }
    int direction[4][2]={0,1,1,0,-1,0,0,-1};
    int result=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]==1){
                for(int k=0;k<4;k++){
                    int x=i+direction[k][0];
                    int y=j+direction[k][1];
                    if(x<0||x>=grid.size()||y<0||y>=grid[0].size()||grid[x][y]==0){
                        result++;
                    }
                }
            }
        }
    }
    std::cout << result << std::endl;
}

并查集理论基础

背景

首先要知道并查集可以解决什么问题呢？

并查集常用来解决连通性问题。

大白话就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。

并查集主要有两个功能：

将两个元素添加到一个集合中。
判断两个元素在不在同一个集合

接下来围绕并查集的这两个功能来展开讲解。

原理讲解

从代码层面，我们如何将两个元素添加到同一个集合中呢。

此时有录友会想到：可以把他放到同一个数组里或者set 或者 map 中，这样就表述两个元素在同一个集合。

那么问题来了，对这些元素分门别类，可不止一个集合，可能是很多集合，成百上千，那么要定义这么多个数组吗？

有录友想，那可以定义一个二维数组。

但如果我们要判断两个元素是否在同一个集合里的时候我们又能怎么办？只能把而二维数组都遍历一遍。

而且每当想添加一个元素到某集合的时候，依然需要把把二维数组都遍历一遍，才知道要放在哪个集合里。

这仅仅是一个粗略的思路，如果沿着这个思路去实现代码，非常复杂，因为管理集合还需要很多逻辑。

那么我们来换一个思路来看看。

我们将三个元素A，B，C （分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通呢。

只需要用一个一维数组来表示，即：father[A] = B，father[B] = C 这样就表述 A 与 B 与 C连通了（有向连通图）。

// 将v，u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

可能有录友想，这样我可以知道 A 连通 B，因为 A 是索引下标，根据 father[A]的数值就知道 A 连通 B。那怎么知道 B 连通 A呢？

我们的目的是判断这三个元素是否在同一个集合里，知道 A 连通 B 就已经足够了。

这里要讲到寻根思路，只要 A ，B，C 在同一个根下就是同一个集合。

给出A元素，就可以通过 father[A] = B，father[B] = C，找到根为 C。

给出B元素，就可以通过 father[B] = C，找到根也为为 C，说明 A 和 B 是在同一个集合里。大家会想第一段代码里find函数是如何实现的呢？其实就是通过数组下标找到数组元素，一层一层寻根过程，代码如下：

// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u; // 如果根就是自己，直接返回
    else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找
}

如何表示 C 也在同一个元素里呢？我们需要 father[C] = C，即C的根也为C，这样就方便表示 A，B，C 都在同一个集合里了。
所以father数组初始化的时候要 father[i] = i，默认自己指向自己。
代码如下：

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

最后我们如何判断两个元素是否在同一个集合里，如果通过 find函数找到两个元素属于同一个根的话，那么这两个元素就是同一个集合，代码如下：

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

路径压缩

在实现 find 函数的过程中，我们知道，通过递归的方式，不断获取father数组下标对应的数值，最终找到这个集合的根。

搜索过程像是一个多叉树中从叶子到根节点的过程，如图：
在这里插入图片描述
如果这棵多叉树高度很深的话，每次find函数去寻找根的过程就要递归很多次。

我们的目的只需要知道这些节点在同一个根下就可以，所以对这棵多叉树的构造只需要这样就可以了，如图：
在这里插入图片描述
除了根节点其他所有节点都挂载根节点下，这样我们在寻根的时候就很快，只需要一步，

如果我们想达到这样的效果，就需要路径压缩，将非根节点的所有节点直接指向根节点。那么在代码层面如何实现呢？

我们只需要在递归的过程中，让 father[u] 接住递归函数 find(father[u]) 的返回结果。

因为 find 函数向上寻找根节点，father[u] 表述 u 的父节点，那么让 father[u] 直接获取 find函数返回的根节点，这样就让节点 u 的父节点变成根节点。

代码如下，注意看注释，路径压缩就一行代码：

// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u;
    else return father[u] = find(father[u]); // 路径压缩
}

以上代码在C++中，可以用三元表达式来精简一下，代码如下：

int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}

相信不少录友在学习并查集的时候，对上面这三行代码实现的 find函数很熟悉，但理解上却不够深入，仅仅知道这行代码很好用，不知道这里藏着路径压缩的过程。

所以对于算法初学者来说，直接看精简代码学习是不太友好的，往往忽略了很多细节。

代码模板

那么此时并查集的模板就出来了，整体模板C++代码如下：

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

通过模板，我们可以知道，并查集主要有三个功能。

寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点

寻找存在的路径

本题是并查集基础题目。

并查集可以解决什么问题呢？

主要就是集合问题，两个节点在不在一个集合，也可以将两个节点添加到一个集合中。

为什么说这道题目是并查集基础题目，题目中各个点是双向图链接，那么判断一个顶点到另一个顶点有没有有效路径其实就是看这两个顶点是否在同一个集合里。

如何算是同一个集合呢，有边连在一起，就算是一个集合。

此时我们就可以直接套用并查集模板。

使用 join(int u, int v)将每条边加入到并查集。

最后 isSame(int u, int v) 判断是否是同一个根就可以了

#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> father=vector<int>(101,0);
// 并查集初始化
void init(){
    for(int i=0;i<=n;i++){
        father[i]=i;
    }
}
// 并查集里寻根的过程
int find(int u){
    if(u==father[u]){
        return u;// 如果根就是自己，直接返回
    }else{
        father[u]=find(father[u]);// 如果根不是自己，就根据数组下标一层一层向下找
        return father[u];
    }
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u,int v){
    u=find(u);
    v=find(v);
    if(v==u){
        return true;
    }else{
        return false;
    }
}
// 将v->u 这条边加入并查集
void join(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v){
        return;
    }
    father[v]=u;
}
int main(){
    int m,s,t;
    int source,destination;
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        cin>>s>>t;
        join(s,t);
    }
    cin>>source>>destination;
    if(isSame(source,destination)){
        std::cout << 1 << std::endl;
    }else{
        cout<<0<<endl;
    }
}

prim算法

最小生成树可以使用 prim算法也可以使用 kruskal算法计算出来。

本篇我们先讲解 prim算法。

最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。

图中有n个节点，那么一定可以用 n - 1 条边将所有节点连接到一起。

那么如何选择这 n-1 条边就是最小生成树算法的任务所在。
例如本题示例中的无向有权图为：
在这里插入图片描述

那么在这个图中，如何选取 n-1 条边使得图中所有节点连接到一起，并且边的权值和最小呢？

（图中为n为7，即7个节点，那么只需要 n-1 即 6条边就可以讲所有顶点连接到一起）

prim算法是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中。

prim算法核心就是三步，我称为prim三部曲，大家一定要熟悉这三步，代码相对会好些很多：

第一步，选距离生成树最近节点
第二步，最近节点加入生成树
第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
在prim算法中，有一个数组特别重要，这里我起名为：minDist。

刚刚我有讲过 “每次寻找距离最小生成树最近的节点并加入到最小生成树中”，那么如何寻找距离最小生成树最近的节点呢？

这就用到了 minDist 数组，它用来作什么呢？

minDist数组用来记录每一个节点距离最小生成树的最近距离。理解这一点非常重要，这也是 prim算法最核心要点所在

1、prim三部曲，第一步：选距离生成树最近节点

选择距离最小生成树最近的节点，加入到最小生成树，刚开始还没有最小生成树，所以随便选一个节点加入就好（因为每一个节点一定会在最小生成树里，所以随便选一个就好），那我们选择节点1 （符合遍历数组的习惯，第一个遍历的也是节点1）

2、prim三部曲，第二步：最近节点加入生成树

此时节点1 已经算最小生成树的节点。

3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）

接下来，我们要更新所有节点距离最小生成树的距离，如图：

注意下标0，我们就不管它了，下标 1 与节点 1 对应，这样可以避免大家把节点搞混。

此时所有非生成树的节点距离最小生成树（节点1）的距离都已经跟新了。

节点2 与节点1 的距离为1，比原先的距离值10001小，所以更新minDist[2]。

节点3 和节点1 的距离为1，比原先的距离值10001小，所以更新minDist[3]。

节点5 和节点1 的距离为2，比原先的距离值10001小，所以更新minDist[5]。

注意图中我标记了 minDist数组里更新的权值，是哪两个节点之间的权值，例如 minDist[2] =1 ，这个 1 是节点1 与节点2 之间的连线，清楚这一点对最后我们记录最小生成树的权值总和很重要。

最后我们就生成了一个最小生成树，绿色的边将所有节点链接到一起，并且保证权值是最小的，因为我们在更新 minDist 数组的时候，都是选距离最小生成树最近的点加入到树中。

讲解上面的模拟过程的时候，我已经强调多次 minDist数组是记录了所有非生成树节点距离生成树的最小距离。

最后，minDist数组也就是记录的是最小生成树所有边的权值。

我在图中，特别把每条边的权值对应的是哪两个节点标记出来（例如minDist[7] = 1，对应的是节点5 和节点7之间的边，而不是节点6 和节点7），为了就是让大家清楚， minDist里的每一个值对应的是哪条边。

那么我们要求最小生成树里边的权值总和就是把最后的 minDist 数组累加一起。

#include<iostream>
#include<vector>
#include <climits>

using namespace std;
int main() {
    int v, e;
    int x, y, k;
    cin >> v >> e;
    // 填一个默认最大值，题目描述val最大为10000
    vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
    while (e--) {
        cin >> x >> y >> k;
        // 因为是双向图，所以两个方向都要填上
        grid[x][y] = k;
        grid[y][x] = k;

    }
    // 所有节点到最小生成树的最小距离
    vector<int> minDist(v + 1, 10001);

    // 这个节点是否在树里
    vector<bool> isInTree(v + 1, false);

    // 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起
    for (int i = 1; i < v; i++) {

        // 1、prim三部曲，第一步：选距离生成树最近节点
        int cur = -1; // 选中哪个节点 加入最小生成树
        int minVal = INT_MAX;
        for (int j = 1; j <= v; j++) { // 1 - v，顶点编号，这里下标从1开始
            //  选取最小生成树节点的条件：
            //  （1）不在最小生成树里
            //  （2）距离最小生成树最近的节点
            if (!isInTree[j] &&  minDist[j] < minVal) {
                minVal = minDist[j];
                cur = j;
            }
        }
        // 2、prim三部曲，第二步：最近节点（cur）加入生成树
        isInTree[cur] = true;

        // 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
        // cur节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即minDist数组）需要更新一下
        // 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢
        for (int j = 1; j <= v; j++) {
            // 更新的条件：
            // （1）节点是 非生成树里的节点
            // （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小
            // 很多录友看到自己 就想不明白什么意思，其实就是 cur 是新加入 最小生成树的节点，那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入，需要更新一下数据了
            if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                minDist[j] = grid[cur][j];
            }
        }
    }
    // 统计结果
    int result = 0;
    for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边
        result += minDist[i];
    }
    cout << result << endl;

}

kruskal算法精讲

Kruskal，同样可以求最小生成树。

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。

上来就这么说，大家应该看不太懂，这里是先让大家有这么个印象，带着这个印象在看下文，理解的会更到位一些。

kruscal的思路：

边的权值排序，因为要优先选最小的边加入到生成树里
遍历排序后的边
如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

下面我们画图举例说明kruscal的工作过程。
在这里插入图片描述

将图中的边按照权值有小到大排序，这样从贪心的角度来说，优先选权值小的边加入到最小生成树中。

排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]

(1,2) 表示节点1 与节点2 之间的边。权值相同的边，先后顺序无所谓。

开始从头遍历排序后的边。

在代码中，如果将两个节点加入同一个集合，又如何判断两个节点是否在同一个集合呢？

这里就涉及到我们之前讲解的并查集。

我们在并查集开篇的时候就讲了，并查集主要就两个功能：

将两个元素添加到一个集合中
判断两个元素在不在同一个集合
大家发现这正好符合 Kruskal算法的需求，这也是为什么我要先讲并查集，再讲 Kruskal。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Edge{
    int l,r,val;
};
int n=10001;
vector<int> father(n,-1);

void init(){
    for(int i=0;i<n;i++){
        father[i]=i;
    }
}
int find(int u){
    return u==father[u]?u:father[u]=find(father[u]);
}
void join(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v){
        return ;
    }
    father[v]=u;
}
int main(){
    
    int v,e;
    int v1,v2,val;
    vector<Edge> edges;
    int result_val=0;
    cin>>v>>e;
    while(e--){
        cin>>v1>>v2>>val;
        edges.push_back({v1,v2,val});
    }
    sort(edges.begin(),edges.end(),[](const Edge& a,const Edge& b){
        return a.val<b.val;
    });
    
    init();
    
    for(Edge edge:edges){
        int x=find(edge.l);
        int y=find(edge.r);
        if(x!=y){
            result_val+=edge.val;
            join(x,y);
        }
    }
    cout<<result_val<<endl;
    return 0;
}

拓扑排序精讲

概括来说，给出一个有向图，把这个有向图转成线性的排序就叫拓扑排序。

当然拓扑排序也要检测这个有向图是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。

所以拓扑排序也是图论中判断有向无环图的常用方法。

拓扑排序指的是一种解决问题的大体思路，而具体算法，可能是广搜也可能是深搜。

大家可能发现各式各样的解法，纠结哪个是拓扑排序？

其实只要能在把有向无环图进行线性排序的算法都可以叫做拓扑排序。

实现拓扑排序的算法有两种：卡恩算法（BFS）和DFS
当我们做拓扑排序的时候，应该优先找入度为 0 的节点，只有入度为0，它才是出发节点。理解以上内容很重要！

接下来我给出拓扑排序的过程，其实就两步：

找到入度为0 的节点，加入结果集
将该节点从图中移除

循环以上两步，直到所有节点都在图中被移除了。

结果集的顺序，就是我们想要的拓扑排序顺序（结果集里顺序可能不唯一）
如果是有向环怎么办呢？
如果我们发现结果集元素个数不等于图中节点个数，我们就可以认定图中一定有有向环！

这也是拓扑排序判断有向环的方法。

#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
using namespace std;

int main(){
    int n,m;
    int s,t;
    cin>>n>>m;
    vector<int> inDegree(n,0);
    vector<int> result;
    unordered_map<int,vector<int>> umap;
    
    while(m--){
        cin>>s>>t;
        inDegree[t]++;
        umap[s].push_back(t);
    }
    queue<int> que;
    for(int i=0;i<n;i++){
        if(inDegree[i]==0){
            que.push(i);
        }
    }
    while(que.size()){
        int cur=que.front();
        que.pop();
        result.push_back(cur);
        //将该节点从图中移除
        vector<int> files=umap[cur];
        if(files.size()){
            for(int i=0;i<files.size();i++){
                inDegree[files[i]]--;
                if(inDegree[files[i]]==0){
                    que.push(files[i]);
                }
            }
        }
    }
    if(result.size()==n){
        for(int i=0;i<n-1;i++){
            std::cout <<result[i] << " ";
        }
        cout<<result[n-1];
    }else{
        cout<<-1<<endl;
    }
}

dijkstra（朴素版）精讲

dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

需要注意两点：

dijkstra 算法可以同时求起点到所有节点的最短路径
权值不能为负数

dijkstra 算法同样是贪心的思路，不断寻找距离源点最近的没有访问过的节点。

这里我也给出 dijkstra三部曲：

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新minDist数组）

minDist数组用来记录每一个节点距离源点的最小距离。

理解这一点很重要，也是理解 dijkstra 算法的核心所在。

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int main(){
    int n,m;
    int s,e,v;
    cin>>n>>m;
    std::vector<vector<int>> grid(n+1,vector<int>(n+1,INT_MAX));
    for(int i=0;i<m;i++){
        cin>>s>>e>>v;
        grid[s][e]=v;
    }
    int start=1;
    int end=n;
    
    vector<int> minDist(n+1,INT_MAX);
    
    vector<bool> visited(n+1,false);
    
    minDist[start]=0;
    
    for(int i=1;i<=n;i++){
        int minval=INT_MAX;
        int cur=1;
        for(int v=1;v<=n;v++){
            if(!visited[v]&&minDist[v]<minval){
                minval=minDist[v];
                cur=v;
            }
        }
        visited[cur]=true;
        for(int v=1;v<=n;v++){
            if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
                minDist[v]=minDist[cur]+grid[cur][v];
            }
        }
    }
    if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
    else cout << minDist[end] << endl; // 到达终点最短路径
}

Bellman_ford 算法精讲

本题依然是单源最短路问题，求从节点1 到节点n 的最小费用。但本题不同之处在于边的权值是有负数了。

从节点1 到节点n 的最小费用也可以是负数，费用如果是负数则表示运输的过程中政府补贴大于运输成本。

在求单源最短路的方法中，使用dijkstra 的话，则要求图中边的权值都为正数。

我们在 dijkstra朴素版中专门有讲解：为什么有边为负数使用dijkstra就不行了。

Bellman_ford算法的核心思想是对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。

每条边有起点、终点和边的权值。例如一条边，节点A 到节点B 权值为value
在这里插入图片描述

minDist[B] 表示到达B节点最小权值，minDist[B] 有哪些状态可以推出来？

状态一： minDist[A] + value 可以推出 minDist[B] 状态二： minDist[B]本身就有权值（可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）

minDist[B] 应为如何取舍。

本题我们要求最小权值，那么这两个状态我们就取最小的

if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value

也就是说，如果通过 A 到 B 这条边可以获得更短的到达B节点的路径，即如果 minDist[B] > minDist[A] + value，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。

以上讲了这么多，其实都是围绕以下这句代码展开：

if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value

这句代码就是 Bellman_ford算法的核心操作。

以上代码也可以这么写：minDist[B] = min(minDist[A] + value, minDist[B])

如果大家看过代码随想录的动态规划章节，会发现无论是背包问题还是子序列问题，这段代码（递推公式）出现频率非常高的。

其实 Bellman_ford算法也是采用了动态规划的思想，即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。

（如果理解不了动态规划的思想也无所谓，理解我上面讲的松弛操作就好）

对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离。
节点数量为n，那么起点到终点，最多是 n-1 条边相连。

那么无论图是什么样的，边是什么样的顺序，我们对所有边松弛 n-1 次就一定能得到起点到达终点的最短距离。

其实也同时计算出了，起点到达所有节点的最短距离，因为所有节点与起点连接的边数最多也就是 n-1 条边。


#include<iostream>
#include<vector>
#include<list>
#include<climits>
using namespace std;

int main(){
    int m,n,p1,p2,val;
    cin>>n>>m;
    vector<vector<int>> grid;
    for(int i=0;i<m;i++){
        cin>>p1>>p2>>val;
        grid.push_back({p1,p2,val});
    }
    int start=1;
    int end=n;
    vector<int> minDist(n+1,INT_MAX);
    minDist[start]=0;
    for(int i=1;i<n;i++){
        for(vector<int> &side:grid){
            int from=side[0];
            int to=side[1];
            int price=side[2];
        
        if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+price){
            minDist[to]=minDist[from]+price;
        }
        }
    }
    if(minDist[end]==INT_MAX){
        std::cout << "unconnected" << std::endl;
    }else{
        cout<<minDist[end]<<endl;
    }
}

Bellman_ford 队列优化算法（又名SPFA）

Bellman_ford 算法每次松弛都是对所有边进行松弛。

但真正有效的松弛，是基于已经计算过的节点在做的松弛。
所以 Bellman_ford 算法每次都是对所有边进行松弛，其实是多做了一些无用功。

只需要对上一次松弛的时候更新过的节点作为出发节点所连接的边进行松弛就够了。

基于以上思路，如何记录上次松弛的时候更新过的节点呢？

用队列来记录。（其实用栈也行，对元素顺序没有要求）

用visited数组记录已经在队列里的元素，已经在队列的元素不用重复加入

#include<iostream>
#include<vector>
#include<queue>
#include<list>
#include<climits>
using namespace std;

struct Edge{
    int to;
    int val;
    Edge(int t,int w){
        to=t;
        val=w;
    }
};
int main(){
    int n,m;
    cin>>n>>m;
    int s,t,v;
    
    vector<list<Edge>> grid(n+1);
    vector<bool> isInQuree(n+1);
    for(int i=0;i<m;i++){
        cin>>s>>t>>v;
        grid[s].push_back(Edge(t,v));
    }
    int start=1;
    int end=n;
    vector<int> minDist(n+1,INT_MAX);
    minDist[start]=0;
    queue<int> que;
    que.push(start);
    while(!que.empty()){
        int node=que.front();
        que.pop();
        isInQuree[node]=false;
        for(Edge edge:grid[node]){
            int from=node;
            int to=edge.to;
            int value=edge.val;
            if(minDist[to]>minDist[from]+value){
                minDist[to]=minDist[from]+value;
                if(isInQuree[to]==false){
                    que.push(to);
                    isInQuree[to]=true;
                }
            }
        }
    }
    if(minDist[end]==INT_MAX){
        std::cout << "unconnected" << std::endl;
    }else{
        cout<<minDist[end]<<endl;
    }
}

bellman_ford之判断负权回路

在没有负权回路的图中，松弛 n 次以上，结果不会有变化。

但本题有负权回路，如果松弛 n 次，结果就会有变化了，因为有负权回路就是可以无限最短路径（一直绕圈，就可以一直得到无限小的最短距离）。

那么每松弛一次，都会更新最短路径，所以结果会一直有变化。
我们拿题目中示例来画一个图：
在这里插入图片描述

图中节点1 到节点4 的最短路径是多少（题目中的最低运输成本）（注意边可以为负数的）

节点1 -> 节点2 -> 节点3 -> 节点4，这样的路径总成本为 -1 + 1 + 1 = 1

而图中有负权回路：

那么我们在负权回路中多绕一圈，我们的最短路径是不是就更小了（也就是更低的运输成本）

节点1 -> 节点2 -> 节点3 -> 节点1 -> 节点2 -> 节点3 -> 节点4，这样的路径总成本 (-1) + 1 + (-1) + (-1) + 1 + (-1) + 1 = -1

如果在负权回路多绕两圈，三圈，无穷圈，那么我们的总成本就会无限小，如果要求最小成本的话，你会发现本题就无解了。

那么解决本题的核心思路，就是在 bellman_ford的基础上，再多松弛一次，看minDist数组是否发生变化。

#include<iostream>
#include<vector>
#include<list>
#include<climits>
using namespace std;

int main(){
    int m,n;
    cin>>n>>m;
    int s,t,v;
    vector<vector<int>> grid;
    for(int i=0;i<m;i++){
        cin>>s>>t>>v;
        grid.push_back({s,t,v});
    }
    int start=1;
    int end=n;
    vector<int> minDist(n+1,INT_MAX);
    minDist[start]=0;
    bool flag=false;
    for(int i=1;i<=n;i++){
        for(vector<int> &side:grid){
            int from=side[0];
            int to=side[1];
            int val=side[2];
            if(i<n){
                if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+val){
                    minDist[to]=minDist[from]+val;
                }
            }else{
                if(minDist[from]!=INT_MAX&&minDist[to]>minDist[from]+val){
                    flag=true;
                }
            }
        }
    }
    if(flag){
        cout<<"circle"<<endl;
    }else if(minDist[end]==INT_MAX){
        std::cout << "unconnected" << std::endl;
    }else{
        cout<<minDist[end]<<endl;
    }
}

bellman_ford之单源有限最短路

本题为单源有限最短路问题，同样是 kama94.城市间货物运输I 延伸题目。

注意题目中描述是最多经过 k 个城市的条件下，而不是一定经过k个城市，也可以经过的城市数量比k小，但要最短的路径。

在 kama94.城市间货物运输I 中我们讲了：对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离。

节点数量为n，起点到终点，最多是 n-1 条边相连。那么对所有边松弛 n-1 次就一定能得到起点到达终点的最短距离。

（如果对以上讲解看不懂，建议详看 kama94.城市间货物运输I ）

本题是最多经过 k 个城市，那么是 k + 1条边相连的节点。
在这里插入图片描述
图中，节点1 最多已经经过2个节点到达节点4，那么中间是有多少条边呢，是 3 条边对吧。

所以本题就是求：起点最多经过k + 1 条边到达终点的最短距离。

对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离，那么对所有边松弛 k + 1次，就是求起点到达与起点k + 1条边相连的节点的最短距离。

理论上来说，对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离。

对所有边松弛两次，相当于计算起点到达与起点两条边相连的节点的最短距离。

对所有边松弛三次，以此类推。

题目中有副权回路的情况下：

理论上来说节点3 应该在对所有边第二次松弛的时候才更新。这因为当时是基于已经计算好的节点2（minDist[2]）来做计算了。

minDist[2]在计算边：（节点1 -> 节点2）的时候刚刚被赋值为 -1。

这样就造成了一个情况，即：计算minDist数组的时候，基于了本次松弛的 minDist数值，而不是上一次松弛时候minDist的数值。
所以在每次计算 minDist 时候，要基于对所有边上一次松弛的 minDist 数值才行，所以我们要记录上一次松弛的minDist。

#include<iostream>
#include<vector>
#include<list>
#include<climits>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int s,t,v;
    int src,dst,k;
    vector<vector<int>> grid;
    vector<int> minDist(n+1,INT_MAX);
    vector<int> minDist_copy(n+1);
    for(int i=0;i<m;i++){
        cin>>s>>t>>v;
        grid.push_back({s,t,v});
    }
    cin>>src>>dst>>k;
    minDist[src]=0;
    for(int i=1;i<=k+1;i++){
        minDist_copy=minDist;
        for(vector<int> &depth:grid){
            int from=depth[0];
            int to=depth[1];
            int val=depth[2];
            if(minDist_copy[from]!=INT_MAX&&minDist[to]>minDist_copy[from]+val){
                minDist[to]=minDist_copy[from]+val;
            }
        }
    }
    if(minDist[dst]==INT_MAX){
        std::cout << "unreachable" << std::endl;
    }else{
        cout<<minDist[dst]<<endl;
    }
}

Floyd 算法精讲

本题是经典的多源最短路问题。

在这之前我们讲解过，dijkstra朴素版、dijkstra堆优化、Bellman算法、Bellman队列优化（SPFA）都是单源最短路，即只能有一个起点。

而本题是多源最短路，即求多个起点到多个终点的多条最短路径。

通过本题，我们来系统讲解一个新的最短路算法-Floyd 算法。

Floyd 算法对边的权值正负没有要求，都可以处理。

Floyd算法核心思想是动态规划。

例如我们再求节点1 到节点9 的最短距离，用二维数组来表示即：grid[1][9]，如果最短距离是10 ，那就是 grid[1][9] = 10。

那节点1 到节点9 的最短距离是不是可以由节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成呢？

即 grid[1][9] = grid[1][5] + grid[5][9]

节点1 到节点5的最短距离是不是可以有节点1 到节点3的最短距离 + 节点3 到节点5 的最短距离组成呢？

即 grid[1][5] = grid[1][3] + grid[3][5]

以此类推，节点1 到节点3的最短距离可以由更小的区间组成。

那么这样我们是不是就找到了，子问题推导求出整体最优方案的递归关系呢。

节点1 到节点9 的最短距离可以由节点1 到节点5的最短距离 + 节点5到节点9的最短距离组成，也可以有节点1 到节点7的最短距离 + 节点7 到节点9的最短距离的距离组成。

那么选哪个呢？

是不是要选一个最小的，毕竟是求最短路。

此时我们已经接近明确递归公式了。

之前在讲解动态规划的时候，给出过动规五部曲：

确定dp数组（dp table）以及下标的含义

确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

那么接下来我们还是用这五部来给大家讲解 Floyd。

1、确定dp数组（dp table）以及下标的含义

这里我们用 grid数组来存图，那就把dp数组命名为 grid。

grid[i][j][k] = m，表示节点i 到节点j 以[1…k] 集合中的一个节点为中间节点的最短距离为m。

可能有录友会想，凭什么就这么定义呢？

节点i 到节点j 的最短距离为m，这句话可以理解，但以[1…k]集合为中间节点就理解不辽了。

节点i 到节点j 的最短路径中一定是经过很多节点，那么这个集合用[1…k] 来表示。

你可以反过来想，节点i 到节点j 中间一定经过很多节点，那么你能用什么方式来表述中间这么多节点呢？

所以这里的k不能单独指某个节点，k 一定要表示一个集合，即[1…k] ，表示节点1 到节点k 一共k个节点的集合。

2、确定递推公式

在上面的分析中我们已经初步感受到了递推的关系。

我们分两种情况：

节点i 到节点j 的最短路径经过节点k
节点i 到节点j 的最短路径不经过节点k
对于第一种情况，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]

节点i 到节点k 的最短距离是不经过节点k，中间节点集合为[1…k-1]，所以表示为grid[i][k][k - 1]

节点k 到节点j 的最短距离也是不经过节点k，中间节点集合为[1…k-1]，所以表示为 grid[k][j][k - 1]

第二种情况，grid[i][j][k] = grid[i][j][k - 1]

如果节点i 到节点j的最短距离不经过节点k，那么中间节点集合[1…k-1]，表示为 grid[i][j][k - 1]

因为我们是求最短路，对于这两种情况自然是取最小值。

即： grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

3、dp数组如何初始化

grid[i][j][k] = m，表示节点i 到节点j 以[1…k] 集合为中间节点的最短距离为m。

刚开始初始化k 是不确定的。

例如题目中只是输入边（节点2 -> 节点6，权值为3），那么grid[2][6][k] = 3，k需要填什么呢？

把k 填成1，那如何上来就知道节点2 经过节点1 到达节点6的最短距离是多少呢。

所以只能把k 赋值为 0，本题节点0 是无意义的，节点是从1 到 n。

这样我们在下一轮计算的时候，就可以根据 grid[i][j][0] 来计算 grid[i][j][1]，此时的 grid[i][j][1] 就是节点i 经过节点1 到达节点j 的最小距离了。

红色的底部一层是我们初始化好的数据，注意：从三维角度去看初始化的数据很重要，下面我们在聊遍历顺序的时候还会再讲。

grid数组中其他元素数值应该初始化多少呢？

本题求的是最小值，所以输入数据没有涉及到的节点的情况都应该初始为一个最大数。

这样才不会影响，每次计算去最小值的时候初始值对计算结果的影响。

4、确定遍历顺序

从递推公式：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1]) 可以看出，我们需要三个for循环，分别遍历i，j 和k

而 k 依赖于 k - 1， i 和j 的到并不依赖与 i - 1 或者 j - 1 等等。

那么这三个for的嵌套顺序应该是什么样的呢？

我们来看初始化，我们是把 k =0 的 i 和j 对应的数值都初始化了，这样才能去计算 k = 1 的时候 i 和 j 对应的数值。

这就好比是一个三维坐标，i 和j 是平层，而k 是垂直向上的。

遍历的顺序是从底向上一层一层去遍历。

所以遍历k 的for循环一定是在最外面，这样才能一层一层去遍历。

至于遍历 i 和 j 的话，for 循环的先后顺序无所谓。

#include<iostream>
#include<vector>
#include<climits>
#include<list>
using namespace std;
int main(){
    int n,m,p1,p2,val;
    cin>>n>>m;
vector<vector<vector<int>>> grid(n+1,vector<vector<int>>(n+1,vector<int>(n+1,10005)));
for(int i=0;i<m;i++){
    cin>>p1>>p2>>val;
    grid[p1][p2][0]=val;
    grid[p2][p1][0]=val;
}
for(int k=1;k<=n;k++){
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            grid[i][j][k]=min(grid[i][j][k-1],grid[i][k][k-1]+grid[k][j][k-1]);
        }
    }
}
int z,start,end;
cin>>z;
while(z--){
    cin>>start>>end;
    if(grid[start][end][n]==10005){
        std::cout << -1 << std::endl;
    }else{
        cout<<grid[start][end][n]<<endl;
    }
}
}

A * 算法精讲（A star算法）

我们看到这道题目的第一个想法就是广搜，这也是最经典的广搜类型题目。

提交后，大家会发现，超时了。

因为本题地图足够大，且 n 也有可能很大，导致有非常多的查询。

我们来看一下广搜的搜索过程，如图，红色是起点，绿色是终点，黄色是要遍历的点，最后从起点找到达到终点的最短路径是棕色。
在这里插入图片描述
可以看出广搜中，做了很多无用的遍历，黄色的格子是广搜遍历到的点。

这里我们能不能让便利方向，向这终点的方向去遍历呢？

这样我们就可以避免很多无用遍历。

Astar 是一种广搜的改良版。有的是 Astar是 dijkstra 的改良版。

其实只是场景不同而已我们在搜索最短路的时候，如果是无权图（边的权值都是1）那就用广搜，代码简洁，时间效率和 dijkstra 差不多（具体要取决于图的稠密）

如果是有权图（边有不同的权值），优先考虑 dijkstra。

而 Astar 关键在于启发式函数，也就是影响广搜或者 dijkstra 从容器（队列）里取元素的优先顺序。

以下，我用BFS版本的A * 来进行讲解。

在BFS中，我们想搜索，从起点到终点的最短路径，要一层一层去遍历。
如果使用A * 的话，其搜索过程是这样的，如图，图中着色的都是我们要遍历的点。
在这里插入图片描述
BFS 是没有目的性的一圈一圈去搜索，而 A * 是有方向性的去搜索。
那么 A * 为什么可以有方向性的去搜索，它的如何知道方向呢？

其关键在于启发式函数。

启发式函数要影响的就是队列里元素的排序！

这是影响BFS搜索方向的关键。

对队列里节点进行排序，就需要给每一个节点权值，如何计算权值呢？

每个节点的权值为F，给出公式为：F = G + H

G：起点达到目前遍历节点的距离

H：目前遍历的节点到达终点的距离

起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离就是起点到达终点的距离。

本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：

曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
欧氏距离（欧拉距离），计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))
x1, x2 为起点坐标，y1, y2 为终点坐标，abs 为求绝对值，sqrt 为求开根号，

选择哪一种距离计算方式也会导致 A * 算法的结果不同。

本题，采用欧拉距离才能最大程度体现点与点之间的距离。

所以使用欧拉距离计算和广搜搜出来的最短路的节点数是一样的。（路径可能不同，但路径上的节点数是相同的）

计算出来 F 之后，按照 F 的大小，来选去出队列的节点。

可以使用优先级队列帮我们排好序，每次出队列，就是F最小的节点。

在游戏开发设计中，保证运行效率的情况下，A * 算法中的启发式函数设计往往不是最短路，而是接近最短路的次短路设计。

void astar(const Knight& k)
{
    Knight cur, next;
	que.push(k);
	while(!que.empty())
	{
		cur=que.top(); que.pop();
		if(cur.x == b1 && cur.y == b2)
		break;
		for(int i = 0; i < 8; i++)
		{
			next.x = cur.x + dir[i][0];
			next.y = cur.y + dir[i][1];
			if(next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000)
			continue;
			if(!moves[next.x][next.y])
			{
				moves[next.x][next.y] = moves[cur.x][cur.y] + 1;

                // 开始计算F
				next.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5
                next.h = Heuristic(next);
                next.f = next.g + next.h;
                que.push(next);
			}
		}
	}
}

总结

深搜与广搜

在二叉树章节中，其实我们讲过了深搜和广搜在二叉树上的搜索过程。

在图论章节中，深搜与广搜就是在图这个数据结构上的搜索过程。

深搜与广搜是图论里基本的搜索方法，大家需要掌握三点：

搜索方式：深搜是可一个方向搜，不到黄河不回头。广搜是围绕这起点一圈一圈的去搜。
代码模板：需要熟练掌握深搜和广搜的基本写法。
应用场景：图论题目基本上可以即用深搜也可用广搜，无疑是用哪个方便而已

注意事项

需要注意的是，同样是深搜模板题，会有两种写法。

在0099.岛屿的数量深搜.md 和 0105.有向图的完全可达性，涉及到dfs的两种写法。

我们对dfs函数的定义是是处理当前节点还是处理下一个节点很重要，决定了两种dfs的写法。

这也是为什么很多录友看到不同的dfs写法，结果发现提交都能过的原因。

而深搜还有细节，有的深搜题目需要用到回溯的过程，有的就不用回溯的过程，

一般是需要计算路径的问题需要回溯，如果只是染色问题（岛屿问题系列）就不需要回溯。

例如： 0105.有向图的完全可达性深搜就不需要回溯，而 0098.所有可达路径中的递归就需要回溯，文章中都有详细讲解

注意：以上说的是不需要回溯，不是没有回溯，只要有递归就会有回溯，只是我们是否需要用到回溯这个过程，这是需要考虑的。

很多录友写出来的广搜可能超时了，例如题目：0099.岛屿的数量广搜

根本原因是只要加入队列就代表走过，就需要标记，而不是从队列拿出来的时候再去标记走过。

具体原因，我在0099.岛屿的数量广搜中详细讲了。

在深搜与广搜的讲解中，为了防止惯性思维，我特别加入了题目 0106.岛屿的周长，提醒大家，看到类似的题目，也不要上来就想着深搜和广搜。

还有一些图的问题，在题目描述中，是没有图的，需要我们自己构建一个图，例如 0110.字符串接龙，题目中连线都没有，需要我们自己去思考什么样的两个字符串可以连成线。

并查集

并查集相对来说是比较复杂的数据结构，其实他的代码不长，但想彻底学透并查集，需要从多个维度入手，

我在理论基础篇的时候讲解如下重点：

为什么要用并查集，怎么不用个二维数据，或者set、map之类的。
并查集能解决那些问题，哪些场景会用到并查集
并查集原理以及代码实现
并查集写法的常见误区
带大家去模拟一遍并查集的过程
路径压缩的过程
时间复杂度分析
上面这几个维度大家都去思考了，并查集基本就学明白了。

其实理论基础篇就算是给大家出了一道裸的并查集题目了，所以在后面的题目安排中，会稍稍的拔高一些，重点在于并查集的应用上。

例如并查集可以判断这个图是否是树，因为树的话，只有一个根，符合并查集判断集合的逻辑，题目：0108.冗余连接。

在0109.冗余连接II 中对有向树的判断难度更大一些，需要考虑的情况比较多。

最小生成树

最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。

最小生成树算法，有prim 和 kruskal。

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。

在稀疏图中，用Kruskal更优。在稠密图中，用prim算法更优。

边数量较少为稀疏图，接近或等于完全图（所有节点皆相连）为稠密图

Prim 算法时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。

Kruskal算法时间复杂度为 O(nlogn)，其中n 为边的数量，适用稀疏图。

关于 prim算法，我自创了三部曲，来帮助大家理解：

第一步，选距离生成树最近节点
第二步，最近节点加入生成树
第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
大家只要理解这三部曲， prim算法至少是可以写出一个框架出来，然后在慢慢补充细节，这样不至于自己在写prim的时候两眼一抹黑完全凭感觉去写。

minDist数组是prim算法的灵魂，它帮助 prim算法完成最重要的一步，就是如何找到距离最小生成树最近的点。

kruscal的主要思路：

边的权值排序，因为要优先选最小的边加入到生成树里
遍历排序后的边
如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
而判断节点是否在一个集合以及将两个节点放入同一个集合，正是并查集的擅长所在。

所以 Kruskal 是需要用到并查集的。

这也是我在代码随想录图论编排上为什么要先讲解并查集在讲解最小生成树。

拓扑排序

拓扑排序是在图上的一种排序。

概括来说，给出一个有向图，把这个有向图转成线性的排序就叫拓扑排序。

同样，拓扑排序也可以检测这个有向图是否有环，即存在循环依赖的情况。

拓扑排序的一些应用场景，例如：大学排课，文件下载依赖等等。

只要记住如下两步拓扑排序的过程，代码就容易写了：

找到入度为0 的节点，加入结果集
将该节点从图中移除

最短路算法

最短路算法是图论中，比较复杂的算法，而且不同的最短路算法都有不同的应用场景。
在这里插入图片描述
如果遇到单源且边为正数，直接Dijkstra。

至于使用朴素版还是堆优化版还是取决于图的稠密度，多少节点多少边算是稠密图，多少算是稀疏图，这个没有量化，如果想量化只能写出两个版本然后做实验去测试，不同的判题机得出的结果还不太一样。

一般情况下，可以直接用堆优化版本。

如果遇到单源边可为负数，直接 Bellman-Ford，同样 SPFA 还是 Bellman-Ford 取决于图的稠密度。

一般情况下，直接用 SPFA。

如果有负权回路，优先 Bellman-Ford，如果是有限节点最短路也优先 Bellman-Ford，理由是写代码比较方便。

如果是遇到多源点求最短路，直接 Floyd。

除非源点特别少，且边都是正数，那可以多次 Dijkstra 求出最短路径，但这种情况很少，一般出现多个源点了，就是想让你用 Floyd 了。

对于A * ，由于其高效性，所以在实际工程应用中使用最为广泛，由于其结果的不唯一性，也就是可能是次短路的特性，一般不适合作为算法题。

游戏开发、地图导航、数据包路由等都广泛使用 A * 算法。

查看全文

http://www.kler.cn/a/511341.html

基于Python的心电图报告解析与心电吸引子绘制

Redis瓶颈和调优

什么是长连接？Netty如何设置进行长连接？

C#表达式和运算符

HTML中如何保留字符串的空白符和换行符号的效果

纯代码实现给WordPress添加文章复制功能

Java反射、静态代理、动态代理

以单用户模式启动 Linux 的方法

调试Hadoop源代码

020：为什么 Resnet 如此重要？

K8S 容器重启策略

C#中如何使用异步编程

Mysql--实战篇--@Transactional失效场景及避免策略（@Transactional实现原理，失效场景，内部调用问题等）

深度学习 DAY1：RNN 神经网络及其变体网络（LSTM、GRU）

Spring AI入门示例HelloWorld

基于微信小程序的购物系统设计与实现（LW+源码+讲解）

【江西新能源科技职业学院主办 | JPCS(ISSN: 1742-6588)出版，快速见刊检索】2025年可再生能源与节能国际会议（REEC 2025）

Windows中安装RabbitMQ

TrueNas Webui页面自定义

2024年度总结：从后端Java到全栈成长的蜕变

python3GUI--仿崩坏三二次元登录页面（附下载地址） By:PyQt5

如何优化前端性能，减少页面加载时间？

解决 IntelliJ IDEA 项目包后出现“% classes”和“% lines covered”的问题

在 Ubuntu 上安装 Nginx 的详细指南

智能阅读时代：基于NLP的自动新闻摘要技术解析

【VRChat · 改模】Unity工程导入人物模型；并添加着色器教程；