# 图论总结篇

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

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

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

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

# 深搜与广搜

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

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

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

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

# 注意事项

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

0099.岛屿的数量深搜.md0105.有向图的完全可达性,涉及到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算法,我自创了三部曲,来帮助大家理解:

  1. 第一步,选距离生成树最近节点
  2. 第二步,最近节点加入生成树
  3. 第三步,更新非生成树节点到生成树的距离(即更新minDist数组)

大家只要理解这三部曲, prim算法 至少是可以写出一个框架出来,然后在慢慢补充细节,这样不至于 自己在写prim的时候 两眼一抹黑 完全凭感觉去写。

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

kruscal的主要思路:

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

而判断节点是否在一个集合 以及将两个节点放入同一个集合,正是并查集的擅长所在。

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

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

# 拓扑排序

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

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

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

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

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

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

# 最短路算法

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

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

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

# 总结

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

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

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

上次更新:: 8/22/2024, 9:07:28 PM
@2021-2024 代码随想录 版权所有 粤ICP备19156078号