图 | Ziuch の Blog

type

status

date

slug

summary

0 本节习题预览

图的定义习题1: 2508. 添加边使所有节点度数都为偶数

图的定义习题2: 2497. 图中最大星和

DFS习题1: 797. 所有可能的路径

DFS习题2: 37. 解数独

BFS习题1: 994. 腐烂的橘子

BFS习题2: 1311. 获取你好友已观看的视频

联通块问题1: 695. 岛屿的最大面积

联通块问题2: 547. 省份数量

联通块问题3: 2492. 两个城市间路径的最小分数

联通块问题4: 463. 岛屿的周长

Dijkstra习题1: 743. 网络延迟时间

Dijkstra习题2: 2203. 得到要求路径的最小带权子图

拓扑排序习题1: 207. 课程表

拓扑排序习题2: 210. 课程表 II

拓扑排序习题3: 1203. 项目管理

最小生成树习题1：1584. 连接所有点的最小费用

最小生成树习题2: 1489. 找到最小生成树里的关键边和伪关键边

并查集习题1: 1971. 寻找图中是否存在路径

并查集习题2: 721. 账户合并

并查集习题3: 959. 由斜杠划分区域

1 图的定义

💡

图用来描述两个数据元素多对多的关系

💡

图分为有向图和无向图，无向图可以理解为每条无向边是由两条有向边构成的

💡

从图中取出一部分点和对应的边的图，叫做子图

💡

图不一定都是联通的，可能由多个联通块(联通分量)构成

💡

一个顶点的度为以它为端点的边的数量，在有向图内还有入度和出度的概念

图的定义习题1: 2508. 添加边使所有节点度数都为偶数

图的定义习题2: 2497. 图中最大星和

2 图的存储

2.1 邻接矩阵

💡

二维矩阵存储是否可达或两点距离

💡

可以在O(1)内得到任意两点是否可达或两点距离，空间复杂度O(n^2)

2.2 邻接表

💡

数组存图顶点，每个顶点后接链表表示可达点(可含距离)

💡

题目一般给出的被称为边集数组，数组内为二元祖或三元组，其中三元组包含边权

3 图的遍历

3.1 DFS 深度优先遍历

3.2 BFS 广度优先遍历

DFS习题1: 797. 所有可能的路径

DFS习题2: 37. 解数独

BFS习题1: 994. 腐烂的橘子

BFS习题2: 1311. 获取你好友已观看的视频

联通块问题1: 695. 岛屿的最大面积

联通块问题2: 547. 省份数量

联通块问题3: 2492. 两个城市间路径的最小分数

联通块问题4: 463. 岛屿的周长

4 最短路问题

4.1 Dijkstra 单源最短路 /

💡

确定起点，每次从未访问过的点中选取距离起点最短的点，标记为已访问，并用它去更新其余未访问过的点，重复以上过程直到所有点都访问过

💡

可用堆加速查找距离最短的点

朴素版代码实现：

堆优化版代码实现：

Dijkstra习题1: 743. 网络延迟时间

Dijkstra习题2: 2203. 得到要求路径的最小带权子图

4.2 Floyd 任意点最短路径

💡

在两点间加入一个点进行中转，取二者最小

代码实现：

4.3 bellman-ford 有边数限制的最短路

4.4 SFPA 含负环的最短路

SPFA判断是否存在负环

💡

全部元素都入队，初始dist都为0，为了防止某些点是无法到达负环的

💡

cnt数组存储最短路径经过的边数，当边数大于等于n了说明必然存在负环

5 拓扑排序

💡

求有向无环图的合理遍历序列

💡

从入度为零的点开始，随后删除该点并更新其能到达点的入度，直到找不到入度为0的点

💡

可用来判断图内是否有环，或求一种合法方案

代码模板：

拓扑排序习题1: 207. 课程表

拓扑排序习题2: 210. 课程表 II

拓扑排序习题3: 1203. 项目管理

6 最小生成树

💡

定义：图中边权和最小的生成树(边数为n-1的联通子图)

6.1 Kruskal算法

💡

将所有边按权从小到大排序，每次加入前都先判断加入后是否会成环(避圈法)

💡

多关键字排序+并查集

代码实现：

6.2 Prim算法 /

💡

选定初始点后，将点分为两个部分，每次取能将两个部分连接起来的最短的边(加点法)

💡

可用堆加速找最短的边

代码实现：

最小生成树习题1：1584. 连接所有点的最小费用

最小生成树习题2: 1489. 找到最小生成树里的关键边和伪关键边

7 并查集

💡

处理不相交集合的合并及查询问题，快速判断两点是否处于同一联通块，是否可达

7.1 初始化

7.2 合并

7.3 路径压缩

💡

最坏形成一条单链，查询时间复杂度是O(n)

💡

对于在同一集合内的元素来说，父亲具体是谁其实并不重要

💡

可以把树形结构压缩成“刺猬”结构。路径压缩后，每次查询的时间复杂度约为O(1)

7.4 查询

7.5 判断是否是根节点

💡

这个需要在合并时选择较大或者较小的点作为父节点才有意义，否则集合中那个点作为根节点都是可以的

并查集习题1: 1971. 寻找图中是否存在路径

并查集习题2: 721. 账户合并

并查集习题3: 959. 由斜杠划分区域