力扣总结 数据结构（八）：图

• 图是一种比树形结构更复杂的非线性数据结构
  • 树形结构中的结点是一对多的关系，且有明显的层次关系
  • 图中的顶点是多对多的关系，无明显的层次关系。
• 按顶点连线（边）是否有方向，可以将图分为有向图和无向图
• 有些图的边还附带数据信息（权），被称为网或网络
• 图的遍历和树的遍历相似，但图中可能出现回路
  • 因此常用一个辅助数组或哈希表 vis 记录访问过的顶点
• 图最常见的问题有：
  • 最小生成树，常用 并查集
  • 拓扑排序，常用 bfs
  • 最短路径， dijkstra、Bellman-Ford、floyd
  • 割点和桥， tarjan
  • 欧拉图， Hierholzer
  • 二分图
    • 最大匹配，匈牙利算法
    • 最大权匹配，KM算法、bfs版KM算法
  • 网络流
    • 最大流
    • 最小费用最大流
• 图的模板

1 基础

• 0133 克隆图
• 0797 所有可能的路径
• 0841 钥匙和房间
• 0997 找到小镇的法官

2 拓扑排序

2.1 基础

• 0207 课程表
• 0210 课程表 II
• 0684 冗余连接

2.2 进阶

• 0310 最小高度树
• 0802 找到最终的安全状态
• 2115 从给定原材料中找到所有可以做出的菜

2.3 挑战

• 1203 项目管理
• 1591 奇怪的打印机 II
• 1857 有向图中最大颜色值

3 最短路径

3.1 基础

• 0743 网络延迟时间
• 1334 阈值距离内邻居最少的城市
• 1514 概率最大的路径

3.2 进阶

• 0787 K 站中转内最便宜的航班
• 0847 访问所有节点的最短路径
• 0882 细分图中的可到达结点
• 1368 使网格图至少有一条有效路径的最小代价
• lcp35 电动车游城市

3.3 挑战

• 1786 从第一个节点出发到最后一个节点的受限路径数
• 1976 到达目的地的方案数
• 2045 到达目的地的第二短时间
• 2203 得到要求路径的最小带权子图

4 最小生成树

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

*5 欧拉图

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

*6 割点和桥

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