数据结构（五）：图

拓扑排序

• 0207 课程表

• 0210 课程表 II

• 0269 火星词典

• 0684 冗余连接

• 0310 最小高度树

• 0802 找到最终的安全状态

• 2115 从给定原材料中找到所有可以做出的菜

• 1203 项目管理

• 1591 奇怪的打印机 II

• 1857 有向图中最大颜色值

最短路径

• 带你发明 Floyd 算法：从记忆化搜索到递推

bfs

• 0126 单词接龙 II
• 0317 离建筑物最近的距离
• 0675 为高尔夫比赛砍树

floyd

• 1334 阈值距离内邻居最少的城市

dij

• 0499 迷宫 III
• 0743 网络延迟时间
• 0778 水位上升的泳池中游泳
• 0787 K 站中转内最便宜的航班
• 0847 访问所有节点的最短路径
• 0882 细分图中的可到达结点
• 1514 概率最大的路径
• 1786 从第一个节点出发到最后一个节点的受限路径数
• 1976 到达目的地的方案数
• 2045 到达目的地的第二短时间
• 2203 得到要求路径的最小带权子图
• lcp35 电动车游城市

01bfs

• 1368 使网格图至少有一条有效路径的最小代价

最小生成树

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

环

• 0765 情侣牵手

基环树

欧拉图

• 0332 重新安排行程
• 0753 破解保险箱
• 2097 合法重新排列数对

连通分量/割点/桥

• 1192 查找集群内的「关键连接」
• 1489 找到最小生成树里的关键边和伪关键边
• 1568 使陆地分离的最少天数

图匹配

• 最大匹配，匈牙利算法
• 最大权匹配，KM算法、bfs版KM算法

网络流

• 最大流
• 最小费用最大流