代码随想录学习 54day 图论 from代码随想录

图论总结篇

从深搜广搜 到并查集，从最小生成树到拓扑排序， 最后是最短路算法系列。

至此算上本篇，一共30篇文章，图论之旅就在此收官了。

在0098.所有可达路径 ，我们接触了两种图的存储方式，邻接表和邻接矩阵，掌握两种图的存储方式很重要。

图的存储方式也是大家习惯在核心代码模式下刷题 经常忽略的 知识点。因为在力扣上刷题不需要掌握图的存储方式。

深搜与广搜

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

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

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

搜索方式：深搜是可一个方向搜，不到黄河不回头。 广搜是围绕这起点一圈一圈的去搜。

代码模板：需要熟练掌握深搜和广搜的基本写法。

应用场景：图论题目基本上可以即用深搜也可用广搜，无疑是用哪个方便而已

注意事项

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

在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 的节点，加入结果集

将该节点从图中移除

## 最短路算法

```py
至此已经讲解了四大最短路算法，分别是Dijkstra、Bellman_ford、SPFA 和 Floyd。

针对这四大最短路算法，我用了七篇长文才彻底讲清楚，分别是：

dijkstra朴素版

dijkstra堆优化版

Bellman_ford

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

bellman_ford 算法判断负权回路

bellman_ford之单源有限最短路

Floyd 算法精讲

启发式搜索：A * 算法

最短路算法比较复杂，而且各自有各自的应用场景，我来用一张表把讲过的最短路算法的使用场景都展现出来：

（因为A * 属于启发式搜索，和上面最短路算法并不是一类，不适合一起对比，所以没有放在一起）

可能有同学感觉：这个表太复杂了，我记也记不住。

其实记不住的原因还是对 这几个最短路算法没有深刻的理解。

这里我给大家一个大体使用场景的分析：

如果遇到单源且边为正数，直接Dijkstra。

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

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

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

一般情况下，直接用 SPFA。

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

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

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

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

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

最短路算法是图论中，比较复杂的算法，而且不同的最短路算法都有不同的应用场景。

我在 最短路算法总结篇 里已经做了一个高度的概括。

大家要时常温故而知新，才能透彻理解各个最短路算法。

## 总结
```py
到最后，图论终于剧终了，相信这是市面上大家能看到最全最细致的图论讲解教程。

图论也是我 《代码随想录》所有章节里 所费精力最大的一个章节。

只为了不负录友们的期待。 大家加油

原文地址：https://blog.csdn.net/qq_40445763/article/details/140501432

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！