图的表示与遍历

图是"节点 + 关系"的最一般形式：树是图，状态机是图，依赖关系是图，社交网络是图。本章讲图的两种表示与两种遍历——BFS 与 DFS，它们是后续一切图算法（→ 图的基本算法）的骨架。

两种表示

	邻接表	邻接矩阵
空间	$O(V+E)$	$O(V^2)$
查询"u、v 相邻吗"	$O(\deg u)$	$O(1)$
遍历邻居	$O(\deg u)$	$O(V)$
适用	稀疏图（多数真实场景）	稠密图、频繁邻接查询

邻接表为每个顶点存一个邻居列表，空间与边数成正比——真实世界的图几乎都是稀疏的（社交网络、网页链接、依赖图），因此默认选邻接表。邻接矩阵用 $V \times V$ 位矩阵，对稠密图与代数方法（矩阵乘法求路径数、Floyd-Warshall）更自然。

第三种补充：边列表（边数组），Kruskal 最小生成树与 Bellman-Ford 的自然输入格式。

广度优先搜索（BFS）

BFS 用队列逐层扩展：先访问起点所有距离为 1 的邻居，再是距离 2 的——BFS 按层序访问，天然给出无权图的单源最短路径（→ 最短路径）。

from collections import deque

def bfs(adj, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

时间与空间都是 $O(V+E)$ 。BFS 的另一个用途：无向图的二分图判定（按层交替染色，同层相遇则非二分）。

深度优先搜索（DFS）

DFS 用递归或栈沿一条路径走到底再回溯。裸 DFS 本身只是遍历，威力在于访问时间的记录：

import sys
sys.setrecursionlimit(10**6)

def dfs(adj, u, visited, order):
    visited.add(u)
    for v in adj[u]:
        if v not in visited:
            dfs(adj, v, visited, order)
    order.append(u)          # 收尾时刻：拓扑排序的原料
    return order

记录每个节点的发现时刻与收尾时刻（括号序列），DFS 能一次性回答一串问题：

环检测：有向图中遇到"正在访问中"的节点（灰色节点）即有环；
拓扑排序：收尾顺序的逆序就是 DAG 的拓扑序（→ 图的基本算法）；
连通分量：无向图中每次从新起点启动 DFS 的次数即分量数；
强连通分量：Tarjan 与 Kosaraju 都建立在 DFS 的时间戳上。

BFS 与 DFS 的选择

一句话：BFS 回答"最近的"，DFS 回答"能不能到、以及结构"。要最短路径、层级关系、最近的出口——BFS；要环检测、拓扑序、连通结构、回溯搜索——DFS。两者时间复杂度相同（ $O(V+E)$ ），区别只在数据结构（队列 vs 栈）带来的访问顺序。

本章要点

真实世界的图几乎都是稀疏的，默认选邻接表；邻接矩阵适合稠密图与代数方法
BFS 用队列按层扩展，天然给出无权最短路径；DFS 用栈/递归走到底再回溯
DFS 的时间戳（括号序列）是环检测、拓扑排序、连通分量的统一原料
BFS 回答"最近的"，DFS 回答"结构与可达"