Lecture 5. 图
图的表示
对于图 $G=(V,E)$，其中 $V$ 是点集，$E$ 是边集。
对于无向图和有向图，都可以用若干 邻接表（adjacency list） 或 邻接矩阵（adjacency matrix） 表示。
- 对于 稀疏（sparse） 图（$|E| \ll |V|^2$），通常选择邻接表
- 对于 稠密（dense） 图（$|E| \approx |V|^2$），或需要快速查询两点之间是否有边，则用邻接矩阵
邻接表
是 $|V|$ 个链表构成的数组。$Adj[u]$ 包含了满足 $(u,v) \in E$ 的所有节点 $v$。
- 若 $G$ 是有向图，那么所有链表的长度总和，就是 $|E|$
- 若 $G$ 是无向图，那么所有链表的长度总和，就是 $2|E|$
邻接表的缺点是无法快速查找图中是否存在一条边 $(u,v)$。
邻接矩阵
邻接矩阵 $A = (a_{ij})$ 是一个 $|V| \times |V|$ 的零一矩阵，行列标号从 $1$ 到 $|V|$：$$a_{i,j}=\begin{cases}1 & (i,j) \in E \\ 0 & (i,j) \not\in E\end{cases}$$，因此其占用的空间是 $\Theta(|V|^2)$ 级别的。
边带权图
对于边带权的图（有一个函数 $w: E \to \mathbb{R}$），只需要在邻接表里面把这个边权额外存储进去，或者把邻接矩阵的零一改成实数。
BFS
Dijkstra 最短路算法和 Prim 最小生成树算法都有用到类似 BFS 的思想。
对于图 $G = (V,E)$，指定起点 $s$，BFS 可以计算出 $s$ 到其他任意节点的距离。BFS 在遍历到距离起点 $k+1$ 的节点之前，一定会先遍历到距离 $k$ 的节点。
不论是有向图还是无向图，在 广度优先树（breadth-first tree） 当中，节点 $u$ 到 $v$ 的简单路径，都对应着原图当中 $u$ 到 $v$ 的最短路径。
伪代码
- $u.color$ 表示节点 $u$ 的状态，黑白灰三种。白表示未处理，灰表示入队，黑表示处理完毕
- $u.d$ 表示节点 $u$ 距离起点的距离
- $u.\pi$ 表示节点 $u$ 在广度优先树当中的前驱节点
效率分析
- 初始化需要 $O(V)$ 时间。
- 每个节点入队出队一次，每次入队出队需要 $O(1)$ 时间，总共需要 $O(V)$ 时间
- 需要遍历邻接表。邻接表长度 $\Theta(E)$，需要 $O(E)$ 时间
- 故总时间复杂度 $O(V+E)$
DFS
伪代码
- $u.color$ 表示节点 $u$ 的状态，黑白灰三种。白表示未处理，灰表示正在处理其子树，黑表示处理完毕
- $u.d$ 表示开始处理的时间戳，是 discovered 的缩写
- $u.f$ 表示处理完毕后的时间戳，是 finished 的缩写
效率分析
- 初始化需要 $O(V)$ 的时间
- 每个节点记录 $u.d$ 和 $u.f$，总共需要 $O(V)$ 时间
- 需要遍历邻接表。邻接表长度 $\Theta(E)$，需要 $O(E)$ 时间
- 故总时间复杂度 $O(V+E)$
括号化定理
在无向图或有向图当中，节点 $u$, $v$ 有以下可能的关系
- 深度优先森林中，$u$ 不是 $v$ 的后代，$v$ 也不是 $u$ 的后代：$[u.d, u.f]$ 与 $[v.d, v.f]$ 完全分离
- 深度优先树中，$u$ 是 $v$ 的后代，$[u.d, u.f] \subset [v.d, v.f]$
- 深度优先树中，$v$ 是 $u$ 的后代，$[v.d, v.f] \subset [u.d, u.f]$
边的分类
一条边 $(u,v)$ 有以下四种分类：
- 树边 tree edges，表示 $v$ 是由 $u$ 直接发现的
- 后向边 back edges，表示深度优先树中 $u$ 的祖先是 $v$。有向图的自环也算后向边
- 前向边 forward edges，表示深度优先树中 $u$ 的后代是 $v$
- 横叉边 cross edges，表示所有其他类型的边