算法图论

图论题目汇总

字数统计: 941字   |   阅读时长: 3分

本文总结了力扣上 2000 题以内的关于图论的 40 道题。将场景相同的放到了一起。

图论是数学的一个分支，以图为研究对象。图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

在计算机中，图论算法提供的是一种对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。

图论的基础算法有下面这些：拓扑排序、最短路径、最小生成树、二分图判定、连通分量、桥和割点、环、欧拉路径、哈密顿路径、异构图、传递闭包、超级源。

本文的题目主要按照各个基础算来聚合，每个基础算法会给出一个我个人网站上的链接，上面有对相应的图的基础算法、题目、题解。

刷完这份题目列表，力扣上的图论的问题可以说刷爆了。

$1 拓扑排序

(1) BFS 拓扑排序

1
https://chengzhaoxi.xyz/22315.html

(2) DFS 拓扑排序

1
https://chengzhaoxi.xyz/1afad3ab.html

$2 最短路径

最短路径

1
https://chengzhaoxi.xyz/47644.html

模板题: 743. 网络延迟时间

1
https://chengzhaoxi.xyz/52291.html

815. 公交路线
864. 获取所有钥匙的最短路径
882. 细分图中的可到达结点
787. K 站中转内最便宜的航班
1334. 阈值距离内邻居最少的城市
882. 细分图中的可到达结点

$3 最小生成树

1
https://chengzhaoxi.xyz/9acb5cb3.html
  • 邻接表

1135. 最低成本联通所有城市

  • 邻接矩阵

1584. 连接所有点的最小费用

$4 二分图判定

1
https://chengzhaoxi.xyz/9f3bb921.html

785. 判断二分图
886. 可能的二分法

$5 连通分量

(1) 无向图的连通分量

1
https://chengzhaoxi.xyz/21790.html
  • 最大连通分量

695. 岛屿的最大面积

  • 连通分量个数

200. 岛屿数量

  • 枚举连通分量

1202. 交换字符串中的元素

(2) 有向图的连通分量

1
https://chengzhaoxi.xyz/26198.html

802. 找到最终的安全状态

$6 桥和割点

(1) 无向图的桥

1
https://chengzhaoxi.xyz/37771.html

1192. 查找集群内的「关键连接」
1489. 找到最小生成树里的关键边和伪关键边

(2) 无向图的割点

1
https://chengzhaoxi.xyz/32360.html

1568. 使陆地分离的最少天数

$7 环

(1) 无向图的环

1
https://chengzhaoxi.xyz/b085148b.html
  • 环判定

684. 冗余连接

  • 环长度

1559. 二维网格图中探测环

(2) 有向图的环

1
https://chengzhaoxi.xyz/f91ac9ea.html

207. 课程表
517. 信息传递
854. 相似度为 K 的字符串
1059. 从始点到终点的所有路径

$8 欧拉路径

1
https://chengzhaoxi.xyz/37137.html

753. 破解保险箱
332. 重新安排行程

$9 哈密顿路径

1
https://chengzhaoxi.xyz/48009.html

$10 异构图

1203. 项目管理

$11 传递闭包

1462. 课程安排 IV

$12 超级源

1
https://chengzhaoxi.xyz/6f904e7f.html

1168. 水资源分配优化

Share