图的基本算法

遍历（→ 图的表示与遍历）之上，图算法的工具箱包括：连通性判定、拓扑排序、强连通分量、桥与割点。本章把这些工具一次讲清——它们是后续最短路径（→ 最短路径）与网络流（→ 网络流与匹配）的底座。

连通性

无向图：BFS/DFS 从每个未访问节点启动，启动次数即连通分量数；判断 $u, v$ 连通只需一次遍历。动态合并（边不断加入）用并查集更合适（→ 并查集与字典树）。
有向图：弱连通（看成无向图连通）与强连通（ $u \to v$ 与 $v \to u$ 都可达）是两回事。强连通分量的经典应用：2-SAT（变量图上 $x$ 与 $\lnot x$ 在同一 SCC 即无解）与编译器的调用图分析。

拓扑排序

DAG（有向无环图）的顶点排序，使每条边从前往后。拓扑排序只对 DAG 有定义——有环即不存在。两个等价实现：

Kahn 算法：反复取入度为 0 的节点，删其出边——顺便能检测环（剩有入度不为 0 的节点）；
DFS 收尾逆序（→ 图的表示与遍历）。

from collections import deque

def topo_sort(n, adj):
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None   # None = 有环

应用：构建系统（make 的依赖顺序）、任务调度、DAG 上的 DP（先拓扑序再按序转移）。

强连通分量

Tarjan 算法：一遍 DFS 求 SCC，维护每个节点的 low-link 值（能回到的最早祖先），low-link 等于发现时间的节点是 SCC 的根。Kosaraju 算法：两遍 DFS（原图一遍、反图一遍），更好理解。两者都是 $O(V+E)$ 。Tarjan 一遍 DFS 求 SCC 是常数因子的胜利；Kosaraju 胜在直观。

桥与割点

桥：删除后图断开的边——网络的关键链路；
割点：删除后连通分量数增加的顶点——单点故障。

两者都用 low-link 值在一次 DFS 中求出（与 Tarjan 同一套机制）：节点 $u$ 的孩子 $v$ 满足 $\text{low}(v) > \text{disc}(u)$ 时，边 $(u,v)$ 是桥。可靠性分析、网络冗余设计（无桥 = 边双连通）的基础。

工具箱总结

工具	复杂度	回答的问题
BFS/DFS	$O(V+E)$	可达性、无权最短路、遍历
拓扑排序	$O(V+E)$	DAG 上的依赖顺序
SCC（Tarjan）	$O(V+E)$	强连通结构、2-SAT
桥/割点	$O(V+E)$	关键边/点、冗余性
并查集	$\alpha(n)$ 均摊	动态合并连通性

本章要点

连通分量数 = BFS/DFS 启动次数；动态合并用并查集
拓扑排序只对 DAG 有定义；Kahn 算法顺便检测环
Tarjan 一遍 DFS 求 SCC（low-link 值）；Kosaraju 两遍但直观
桥与割点用 low-link 值一次 DFS 求出，是网络冗余分析的基础