介绍好的电影网站模板下载,菜单设计制作app,建立一个虚拟公司的网站,企业资源管理软件这里写目录标题 理论基础图的基本概念图的种类度 连通性连通图强连通图连通分量强连通分量 图的构造邻接矩阵邻接表 图的遍历方式 深度优先搜索理论基础dfs 与 bfs 区别dfs 搜索过程深搜三部曲所有可达路径广度优先搜索理论基础广搜的使用场景广搜的过程 岛屿数量孤岛的总面积沉… 这里写目录标题 理论基础图的基本概念图的种类度 连通性连通图强连通图连通分量强连通分量 图的构造邻接矩阵邻接表 图的遍历方式 深度优先搜索理论基础dfs 与 bfs 区别dfs 搜索过程深搜三部曲所有可达路径广度优先搜索理论基础广搜的使用场景广搜的过程 岛屿数量孤岛的总面积沉没孤岛水流问题建造最大岛屿字符串接龙有向图的完全可达性岛屿的周长 并查集理论基础背景原理讲解路径压缩代码模板寻找存在的路径prim算法kruskal算法精讲拓扑排序精讲dijkstra朴素版精讲Bellman_ford 算法精讲Bellman_ford 队列优化算法又名SPFAbellman_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] 6grid[5][2] 6表示节点2 与 节点5 相互连通权值为6。 如图 在一个 n 节点数为8 的图中就需要申请 8 * 8 这么大的空间。 图中有一条双向边即grid[2][5] 6grid[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是先把本节点所连接的所有节点遍历一遍走到下一个节点的时候再把连接节点的所有节点遍历一遍搜索方向更像是广度四面八方的搜索过程。 当然以上讲的是大体可以这么理解接下来 我们详细讲解dfsbfs在用单独一篇文章详细讲解
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(参数)通常我们递归的时候我们递归搜索需要了解哪些参数其实也可以在写递归函数的时候发现需要什么参数再去补充就可以。
一般情况深搜需要 二维数组数组结构保存所有路径需要一维数组保存单一路径这种保存结果的数组我们可以定义一个全局变量避免让我们的函数参数过多。
例如这样
vectorvectorint result; // 保存符合条件的所有路径
vectorint path; // 起点到终点的路径
void dfs (图目前搜索的节点) 但这种写法看个人习惯不强求。
确认终止条件
终止条件很重要很多同学写dfs的时候之所以容易死循环栈溢出等等这些问题都是因为终止条件没有想清楚。
if (终止条件) {存放结果;return;
}终止添加不仅是结束本层递归同时也是我们收获结果的时候。
另外其实很多dfs写法没有写终止条件其实终止条件写在了 下面dfs递归的逻辑里了也就是不符合条件直接不会向下递归。这里如果大家不理解的话没关系后面会有具体题目来讲解。
处理目前搜索节点出发的路径
一般这里就是一个for循环的操作去遍历 目前搜索节点 所能到的所有节点。
for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果
}不少录友疑惑的地方都是 dfs代码框架中for循环里分明已经处理节点了那么 dfs函数下面 为什么还要撤销的呢。
如图七所示 路径2 已经走到了 目的地节点6那么 路径2 是如何撤销然后改为 路径3呢 其实这就是 回溯的过程撤销路径2走换下一个方向。
所有可达路径
本题是深度优先搜索的基础题目 深搜三部曲来分析题目 确认递归函数参数 首先我们dfs函数一定要存一个图用来遍历的需要存一个目前我们遍历的节点定义为x。 还需要存一个n表示终点我们遍历的时候用来判断当 xn 时候 标明找到了终点。 其实在递归函数的参数 不容易一开始就确定了一般是在写函数体的时候发现缺什么参加就补什么 至于 单一路径 和 路径集合 可以放在全局变量 确认终止条件 什么时候我们就找到一条路径了 当目前遍历的节点 为 最后一个节点 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(); // 回溯撤销本节点}
}#includeiostream
#includevector
using namespace std;
vectorvectorint result;
vectorint path;
void dfs(const vectorvectorint graph,int x,int n){if(xn){result.push_back(path);return;}for(int i1;in;i){if(graph[x][i]1){path.push_back(i);dfs(graph,i,n);path.pop_back();}}
}
int main(){int n,m,s,t;cinnm;vectorvectorint graph(n1,vectorint(n1,0));for(int i0;im;i){cinst;graph[s][t]1;}path.push_back(1);dfs(graph,1,n);if(result.size()0){std::cout -1 std::endl;}for(const vectorint pa:result){for(int i0;ipa.size()-1;i){coutpa[i] ;}coutpa[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(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {queuepairint, int que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] true; // 只要加入队列立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pairint ,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; // 只要加入队列立刻标记避免重复访问}}}}岛屿数量
题目中每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。也就是说斜角度链接是不算了
思路是用遇到一个没有遍历过的节点陆地计数器就加一然后把该节点陆地所能遍历到的陆地都标记上。 在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。
深搜解法
#includeiostream
#includevector
using namespace std;int dir[4][2]{0,1,1,0,-1,0,0,-1};
void dfs(const vectorvectorint grid,vectorvectorbool visited,int x,int y){for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[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;cinnm;vectorvectorint grid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}vectorvectorbool visited(n,vectorbool(m,false));int result0;for(int i0;in;i){for(int j0;jm;j){if(!visited[i][j]grid[i][j]1){visited[i][j]true;result;dfs(grid,visited,i,j);}}}std::cout result std::endl;
}广搜解法
#includeiostream
#includevector
#includequeue
using namespace std;int dir[4][2]{0,1,1,0,-1,0,0,-1};void bfs(const vectorvectorint grid,vectorvectorbool visited,int x,int y){queuepairint,int que;que.push({x,y});visited[x][y]true;while(!que.empty()){pairint,int curque.front();que.pop();int curxcur.first;int curycur.second;for(int i0;i4;i){int nextxcurxdir[i][0];int nextycurydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()){continue;}if(!visited[nextx][nexty]grid[nextx][nexty]1){que.push({nextx,nexty});visited[nextx][nexty]true;}}}}
int main(){int n,m;cinnm;vectorvectorint grid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}vectorvectorbool visited(n,vectorbool(m,false));int result0;for(int i0;in;i){for(int j0;jm;j){if(!visited[i][j]grid[i][j]1){result;bfs(grid,visited,i,j);}}}coutresultendl;
}孤岛的总面积
本题使用dfsbfs并查集都是可以的。
本题要求找到不靠边的陆地面积那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋然后再去重新遍历地图 统计此时还剩下的陆地就可以了。 在遇到地图周边陆地的时候将1都变为0此时地图为这样 然后我们再去遍历这个地图遇到有陆地的地方去采用深搜或者广搜边统计所有陆地。 dfs
#includeiostream
#includevector
using namespace std;int dir[4][2]{-1,0,0,-1,1,0,0,1};
int count;
void dfs(vectorvectorint grid,int x,int y){grid[x][y]0;count;for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()){continue;}if(grid[nextx][nexty]0){continue;}dfs(grid,nextx,nexty);}
}
int main(){int n,m;cinnm;vectorvectorint grid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}for(int i0;in;i){if(grid[i][0]1){dfs(grid,i,0);}if(grid[i][m-1]1){dfs(grid,i,m-1);}}for(int j0;jm;j){if(grid[0][j]1){dfs(grid,0,j);}if(grid[n-1][j]1){dfs(grid,n-1,j);}}count0;for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1){dfs(grid,i,j);}}}std::cout count std::endl;}沉没孤岛
思路依然是从地图周边出发将周边空格相邻的陆地都做上标记然后在遍历一遍地图遇到 陆地 且没做过标记的那么都是地图中间的 陆地 全部改成水域就行。
有的录友可能想我在定义一个 visited 二维数组单独标记周边的陆地然后遍历地图的时候同时对 数组board 和 数组visited 进行判断决定 陆地是否变成水域。
这样做其实就有点麻烦了不用额外定义空间了标记周边的陆地可以直接改陆地为其他特殊值作为标记。
步骤一深搜或者广搜将地图周边的 1 陆地全部改成 2 特殊标记
步骤二将水域中间 1 陆地全部改成 水域0
步骤三将之前标记的 2 改为 1 陆地
#includeiostream
#includevector
using namespace std;int dir[4][2]{-1,0,0,-1,1,0,0,1};
void dfs(vectorvectorint grid,int x,int y){grid[x][y]2;for(int i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxgrid.size()||nexty0||nextygrid[0].size()){continue;}if(grid[nextx][nexty]0||grid[nextx][nexty]2){continue;}dfs(grid,nextx,nexty);}return;}
int main(){int n,m;cinnm;vectorvectorint grid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}//步骤一for(int i0;in;i){if(grid[i][0]1){dfs(grid,i,0);}if(grid[i][m-1]1){dfs(grid,i,m-1);}}for(int j0;jm;j){if(grid[0][j]1){dfs(grid,0,j);}if(grid[n-1][j]1){dfs(grid,n-1,j);}}//步骤二步骤三for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1){grid[i][j]0;}if(grid[i][j]2){grid[i][j]1;}}}for(int i0;in;i){for(int j0;jm;j){std::cout grid[i][j] ;}coutendl;}}水流问题
一个比较直白的想法其实就是 遍历每个点然后看这个点 能不能同时到达第一组边界和第二组边界。
至于遍历方式可以用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(vectorvectorint 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;vectorvectorint grid(n, vectorint(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的。
#includeiostream
#includevector
#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(vectorvectorint grid,vectorvectorbool 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 i0;i4;i){int nextxxdir[i][0];int nextyydir[i][1];if(nextx0||nextxn||nexty0||nextym){continue;}dfs(grid,visited,nextx,nexty,mark);}
}
int main(){cinnm;vectorvectorint grid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}vectorvectorbool visited(n,vectorbool(m,false));unordered_mapint,int gridNum;int mark2;bool isAllGridtrue;for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]0){isAllGridfalse;}if(!visited[i][j]grid[i][j]1){count0;dfs(grid,visited,i,j,mark);gridNum[mark]count;mark;}}}if(isAllGrid){std::cout n*m std::endl;return 0;}//根据添加陆地的位置计算周边岛屿面积之和int result0;unordered_setint visitedGrid;for(int i0;in;i){for(int j0;jm;j){count1;visitedGrid.clear();if(grid[i][j]0){for(int k0;k4;k){int neariidir[k][1];int nearjjdir[k][0];if(neari0||nearin||nearj0||nearjm){continue;}if(visitedGrid.count(grid[neari][nearj])){continue;}countgridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]);}}resultmax(result,count);}}coutresultendl;
}字符串接龙
从这个图中可以看出 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_setstring strSet;cin beginStr endStr;for (int i 0; i n; i) {cin str;strSet.insert(str);}// 记录strSet里的字符串是否被访问过同时记录路径长度unordered_mapstring, int visitMap; // 记录的字符串路径长度// 初始化队列queuestring que;que.push(beginStr);// 初始化visitMapvisitMap.insert(pairstring, 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(pairstring, int(newWord, path 1));que.push(newWord);}}}}// 没找到输出0cout 0 endl;}有向图的完全可达性
本题给我们是一个有向图 意识到这是有向图很重要
这就很容易让我们想起岛屿问题只要发现独立的岛就是不可到达的。
但本题是有向图在有向图中即使所有节点都是链接的但依然不可能从0出发遍历所有边。
例如上图中节点1 可以到达节点2但节点2是不能到达节点1的。
所以本题是一个有向图搜索全路径的问题。 只能用深搜DFS或者广搜BFS来搜。
以下dfs分析 大家一定要仔细看本题有两种dfs的解法很多题解没有讲清楚。
深搜三部曲
确认递归函数参数
需要传入地图需要知道当前我们拿到的key以至于去下一个房间。 同时还需要一个数组用来记录我们都走过了哪些房间这样好知道最后有没有把所有房间都遍历的可以定义一个一维数组。
确认终止条件
遍历的时候什么时候终止呢 这里有一个很重要的逻辑就是在递归中我们是处理当前访问的节点还是处理下一个要访问的节点。 这决定 终止条件怎么写。 首先明确本题中什么叫做处理就是 visited数组来记录访问过的节点该节点默认数组里元素都是false把元素标记为true就是处理 本节点了。
如果我们是处理当前访问的节点当前访问的节点如果是 true 说明是访问过的节点那就终止本层递归如果不是true我们就把它赋值为true因为这是我们处理本层递归的节点。
如果我们是处理下一层访问的节点而不是当前层。那么就要在 深搜三部曲中第三步处理目前搜索节点出发的路径的时候对 节点进行处理。 这样的话就不需要终止条件而是在 搜索下一个节点的时候直接判断 下一个节点是否是我们要搜的节点。
可以看出如何看待 我们要访问的节点直接决定了两种不一样的写法很多录友对这一块很模糊可能做过这道题但没有思考到这个维度上。
处理目前搜索节点出发的路径
其实在上面深搜三部曲 第二部就已经讲了因为终止条件的两种写法 直接决定了两种不一样的递归写法。
这里还有细节
看上面两个版本的写法中 好像没有发现回溯的逻辑。
我们都知道有递归就有回溯回溯就在递归函数的下面 那么之前我们做的dfs题目都需要回溯操作 为什么本题就没有回溯呢
代码中可以看到dfs函数下面并没有回溯的操作。
此时就要在思考本题的要求了本题是需要判断 1节点 是否能到所有节点那么我们就没有必要回溯去撤销操作了只要遍历过的节点一律都标记上。
那什么时候需要回溯操作呢
当我们需要搜索一条可行路径的时候就需要回溯操作了因为没有回溯就没法“调头”
#includeiostream
#includevector
#includelist
using namespace std;
void dfs(const vectorlistint graph,int key,vectorbool visited){if(visited[key]){return;}visited[key]true;listint keysgraph[key];// 获取节点key的所有邻接节点for(int key:keys){dfs(graph,key,visited);}
}
int main(){int n,k;cinnk;int s,t;vectorlistint graph(n1);//邻接表while(k--){cinst;graph[s].push_back(t);//graph[s]包含所有从节点s出发的边所指向的节点}vectorbool visited(n1,false);dfs(graph,1,visited);for(int i1;in;i){if(visited[i]false){std::cout -1 std::endl;return 0;}}cout1endl;}岛屿的周长
遍历每一个空格遇到岛屿则计算其上下左右的空格情况。
如果该陆地上下左右的空格是有水域则说明是一条边如图 陆地的右边空格是水域则说明找到一条边。
如果该陆地上下左右的空格出界了则说明是一条边如图 该陆地的下边空格出界了则说明找到一条边。
#includeiostream
#includevector
using namespace std;
int main(){int n,m;cinnm;vectorvectorint grid(n,vectorint(m,0));for(int i0;in;i){for(int j0;jm;j){cingrid[i][j];}}int direction[4][2]{0,1,1,0,-1,0,0,-1};int result0;for(int i0;in;i){for(int j0;jm;j){if(grid[i][j]1){for(int k0;k4;k){int xidirection[k][0];int yjdirection[k][1];if(x0||xgrid.size()||y0||ygrid[0].size()||grid[x][y]0){result;}}}}}std::cout result std::endl;
}并查集理论基础
背景
首先要知道并查集可以解决什么问题呢
并查集常用来解决连通性问题。
大白话就是当我们需要判断两个元素是否在同一个集合里的时候我们就要想到用并查集。
并查集主要有两个功能
将两个元素添加到一个集合中。判断两个元素在不在同一个集合
接下来围绕并查集的这两个功能来展开讲解。
原理讲解
从代码层面我们如何将两个元素添加到同一个集合中呢。
此时有录友会想到可以把他放到同一个数组里或者set 或者 map 中这样就表述两个元素在同一个集合。
那么问题来了对这些元素分门别类可不止一个集合可能是很多集合成百上千那么要定义这么多个数组吗
有录友想那可以定义一个二维数组。
但如果我们要判断两个元素是否在同一个集合里的时候 我们又能怎么办 只能把而二维数组都遍历一遍。
而且每当想添加一个元素到某集合的时候依然需要把把二维数组都遍历一遍才知道要放在哪个集合里。
这仅仅是一个粗略的思路如果沿着这个思路去实现代码非常复杂因为管理集合还需要很多逻辑。
那么我们来换一个思路来看看。
我们将三个元素ABC 分别是数字放在同一个集合其实就是将三个元素连通在一起如何连通呢。
只需要用一个一维数组来表示即father[A] Bfather[B] C 这样就表述 A 与 B 与 C连通了有向连通图。
// 将vu 这条边加入并查集
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 BC 在同一个根下就是同一个集合。
给出A元素就可以通过 father[A] Bfather[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这样就方便表示 ABC 都在同一个集合里了。 所以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根据题目中节点数量而定一般比节点数量大一点就好
vectorint father vectorint (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) 判断是否是同一个根 就可以了
#includeiostream
#includevector
using namespace std;
int n;
vectorint fathervectorint(101,0);
// 并查集初始化
void init(){for(int i0;in;i){father[i]i;}
}
// 并查集里寻根的过程
int find(int u){if(ufather[u]){return u;// 如果根就是自己直接返回}else{father[u]find(father[u]);// 如果根不是自己就根据数组下标一层一层向下找return father[u];}
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u,int v){ufind(u);vfind(v);if(vu){return true;}else{return false;}
}
// 将v-u 这条边加入并查集
void join(int u,int v){ufind(u);vfind(v);if(uv){return;}father[v]u;
}
int main(){int m,s,t;int source,destination;cinnm;init();for(int i0;im;i){cinst;join(s,t);}cinsourcedestination;if(isSame(source,destination)){std::cout 1 std::endl;}else{cout0endl;}
}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 数组 累加一起。
#includeiostream
#includevector
#include climitsusing namespace std;
int main() {int v, e;int x, y, k;cin v e;// 填一个默认最大值题目描述val最大为10000vectorvectorint grid(v 1, vectorint(v 1, 10001));while (e--) {cin x y k;// 因为是双向图所以两个方向都要填上grid[x][y] k;grid[y][x] k;}// 所有节点到最小生成树的最小距离vectorint minDist(v 1, 10001);// 这个节点是否在树里vectorbool 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。
#includeiostream
#includevector
#includealgorithmusing namespace std;struct Edge{int l,r,val;
};
int n10001;
vectorint father(n,-1);void init(){for(int i0;in;i){father[i]i;}
}
int find(int u){return ufather[u]?u:father[u]find(father[u]);
}
void join(int u,int v){ufind(u);vfind(v);if(uv){return ;}father[v]u;
}
int main(){int v,e;int v1,v2,val;vectorEdge edges;int result_val0;cinve;while(e--){cinv1v2val;edges.push_back({v1,v2,val});}sort(edges.begin(),edges.end(),[](const Edge a,const Edge b){return a.valb.val;});init();for(Edge edge:edges){int xfind(edge.l);int yfind(edge.r);if(x!y){result_valedge.val;join(x,y);}}coutresult_valendl;return 0;
}拓扑排序精讲
概括来说给出一个 有向图把这个有向图转成线性的排序 就叫拓扑排序。
当然拓扑排序也要检测这个有向图 是否有环即存在循环依赖的情况因为这种情况是不能做线性排序的。
所以拓扑排序也是图论中判断有向无环图的常用方法。
拓扑排序指的是一种 解决问题的大体思路 而具体算法可能是广搜也可能是深搜。
大家可能发现 各式各样的解法纠结哪个是拓扑排序
其实只要能在把 有向无环图 进行线性排序 的算法 都可以叫做 拓扑排序。
实现拓扑排序的算法有两种卡恩算法BFS和DFS 当我们做拓扑排序的时候应该优先找 入度为 0 的节点只有入度为0它才是出发节点。 理解以上内容很重要
接下来我给出 拓扑排序的过程其实就两步
找到入度为0 的节点加入结果集将该节点从图中移除
循环以上两步直到 所有节点都在图中被移除了。
结果集的顺序就是我们想要的拓扑排序顺序 结果集里顺序可能不唯一 如果是 有向环怎么办呢 如果我们发现结果集元素个数 不等于 图中节点个数我们就可以认定图中一定有 有向环
这也是拓扑排序判断有向环的方法。
#includeiostream
#includevector
#includequeue
#includeunordered_map
using namespace std;int main(){int n,m;int s,t;cinnm;vectorint inDegree(n,0);vectorint result;unordered_mapint,vectorint umap;while(m--){cinst;inDegree[t];umap[s].push_back(t);}queueint que;for(int i0;in;i){if(inDegree[i]0){que.push(i);}}while(que.size()){int curque.front();que.pop();result.push_back(cur);//将该节点从图中移除vectorint filesumap[cur];if(files.size()){for(int i0;ifiles.size();i){inDegree[files[i]]--;if(inDegree[files[i]]0){que.push(files[i]);}}}}if(result.size()n){for(int i0;in-1;i){std::cout result[i] ;}coutresult[n-1];}else{cout-1endl;}
}dijkstra朴素版精讲
dijkstra算法在有权图权值非负数中求从起点到其他节点的最短路径算法。
需要注意两点
dijkstra 算法可以同时求 起点到所有节点的最短路径 权值不能为负数
dijkstra 算法 同样是贪心的思路不断寻找距离 源点最近的没有访问过的节点。
这里我也给出 dijkstra三部曲
第一步选源点到哪个节点近且该节点未被访问过 第二步该最近节点被标记访问过 第三步更新非访问节点到源点的距离即更新minDist数组
minDist数组 用来记录 每一个节点距离源点的最小距离。
理解这一点很重要也是理解 dijkstra 算法的核心所在。
#includeiostream
#includevector
#includeclimits
using namespace std;
int main(){int n,m;int s,e,v;cinnm;std::vectorvectorint grid(n1,vectorint(n1,INT_MAX));for(int i0;im;i){cinsev;grid[s][e]v;}int start1;int endn;vectorint minDist(n1,INT_MAX);vectorbool visited(n1,false);minDist[start]0;for(int i1;in;i){int minvalINT_MAX;int cur1;for(int v1;vn;v){if(!visited[v]minDist[v]minval){minvalminDist[v];curv;}}visited[cur]true;for(int v1;vn;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 条边。 #includeiostream
#includevector
#includelist
#includeclimits
using namespace std;int main(){int m,n,p1,p2,val;cinnm;vectorvectorint grid;for(int i0;im;i){cinp1p2val;grid.push_back({p1,p2,val});}int start1;int endn;vectorint minDist(n1,INT_MAX);minDist[start]0;for(int i1;in;i){for(vectorint side:grid){int fromside[0];int toside[1];int priceside[2];if(minDist[from]!INT_MAXminDist[to]minDist[from]price){minDist[to]minDist[from]price;}}}if(minDist[end]INT_MAX){std::cout unconnected std::endl;}else{coutminDist[end]endl;}
}Bellman_ford 队列优化算法又名SPFA
Bellman_ford 算法每次松弛 都是对所有边进行松弛。
但真正有效的松弛是基于已经计算过的节点在做的松弛。 所以 Bellman_ford 算法 每次都是对所有边进行松弛其实是多做了一些无用功。
只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。
基于以上思路如何记录 上次松弛的时候更新过的节点呢
用队列来记录。其实用栈也行对元素顺序没有要求
用visited数组记录已经在队列里的元素已经在队列的元素不用重复加入
#includeiostream
#includevector
#includequeue
#includelist
#includeclimits
using namespace std;struct Edge{int to;int val;Edge(int t,int w){tot;valw;}
};
int main(){int n,m;cinnm;int s,t,v;vectorlistEdge grid(n1);vectorbool isInQuree(n1);for(int i0;im;i){cinstv;grid[s].push_back(Edge(t,v));}int start1;int endn;vectorint minDist(n1,INT_MAX);minDist[start]0;queueint que;que.push(start);while(!que.empty()){int nodeque.front();que.pop();isInQuree[node]false;for(Edge edge:grid[node]){int fromnode;int toedge.to;int valueedge.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{coutminDist[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数组 是否发生变化。
#includeiostream
#includevector
#includelist
#includeclimits
using namespace std;int main(){int m,n;cinnm;int s,t,v;vectorvectorint grid;for(int i0;im;i){cinstv;grid.push_back({s,t,v});}int start1;int endn;vectorint minDist(n1,INT_MAX);minDist[start]0;bool flagfalse;for(int i1;in;i){for(vectorint side:grid){int fromside[0];int toside[1];int valside[2];if(in){if(minDist[from]!INT_MAXminDist[to]minDist[from]val){minDist[to]minDist[from]val;}}else{if(minDist[from]!INT_MAXminDist[to]minDist[from]val){flagtrue;}}}}if(flag){coutcircleendl;}else if(minDist[end]INT_MAX){std::cout unconnected std::endl;}else{coutminDist[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 应该在对所有边第二次松弛的时候才更新。 这因为当时是基于已经计算好的 节点2minDist[2]来做计算了。
minDist[2]在计算边节点1 - 节点2的时候刚刚被赋值为 -1。
这样就造成了一个情况即计算minDist数组的时候基于了本次松弛的 minDist数值而不是上一次 松弛时候minDist的数值。 所以在每次计算 minDist 时候要基于 对所有边上一次松弛的 minDist 数值才行所以我们要记录上一次松弛的minDist。
#includeiostream
#includevector
#includelist
#includeclimits
using namespace std;int main(){int n,m;cinnm;int s,t,v;int src,dst,k;vectorvectorint grid;vectorint minDist(n1,INT_MAX);vectorint minDist_copy(n1);for(int i0;im;i){cinstv;grid.push_back({s,t,v});}cinsrcdstk;minDist[src]0;for(int i1;ik1;i){minDist_copyminDist;for(vectorint depth:grid){int fromdepth[0];int todepth[1];int valdepth[2];if(minDist_copy[from]!INT_MAXminDist[to]minDist_copy[from]val){minDist[to]minDist_copy[from]val;}}}if(minDist[dst]INT_MAX){std::cout unreachable std::endl;}else{coutminDist[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] 3k需要填什么呢
把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循环分别遍历ij 和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 循环的先后顺序无所谓。
#includeiostream
#includevector
#includeclimits
#includelist
using namespace std;
int main(){int n,m,p1,p2,val;cinnm;
vectorvectorvectorint grid(n1,vectorvectorint(n1,vectorint(n1,10005)));
for(int i0;im;i){cinp1p2val;grid[p1][p2][0]val;grid[p2][p1][0]val;
}
for(int k1;kn;k){for(int i0;in;i){for(int j0;jn;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;
cinz;
while(z--){cinstartend;if(grid[start][end][n]10005){std::cout -1 std::endl;}else{coutgrid[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()){curque.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;// 开始计算Fnext.g cur.g 5; // 统一不开根号这样可以提高精度马走日1 * 1 2 * 2 5next.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 * 算法。
