跳转到内容

图的基本算法

基于 BFS/DFS 的连通分量、二分图判定、拓扑排序、Tarjan/Kosaraju 强连通分量、桥与割点。本章是后续图算法的工具箱。

  • 拓扑排序只对 DAG 有定义
  • Tarjan 一遍 DFS 求 SCC
  • 桥与割点用 low-link 值