8.1 图和图遍历
给定图\(G=(V, E)\)，V是顶点集，边集\(E \subseteq V \times V\)表示顶点之间的某种二元关系。如果\(E\)是一种对称关系，则称图\(G\)为无向图；如果\(E\)是非对称关系，则称\(G\)为无向图。
用于图表示的数据结构主要有两种，一种是邻接链表，一种是邻接矩阵。
图遍历是对图的一种最基本但也是最重要的处理，它遵循节点之间的关联关系，按某种顺序依次处理图中所有的点和边。
8.2 有向图上的深度优先遍历
基本思想：从一个节点出发，如果它有未探索的邻居节点，则选择其中的某一个深入探索（其他可探索的节点暂时不管），每到一个新的节点则递归地进行上述深入探索的过程。当探索无法继续时，则沿着探索的路径回退。此时该节点可能还有其他邻居节点未被探索过，需要递归地对该邻居节点进行深入探索。
8.2.1 遍历框架
8.2.2 深度优先遍历树
8.2.3 活动区间
8.3 有向图上深度优先遍历的应用
8.3.1 拓扑排序
Def 8.2（拓扑排序） 如果为图中每个顶点 \(v_1, v_2, \dots , v_n\) 分配一个序号 \(\tau_1, \tau_2 ,\dots , \tau_n\) 满足：
- 所有序号为正整数1到n的某个排列（理论上是全序集即可）
- 对任意有向边\(i \to j\)（从\(v_i\)指向\(v_j\)的有向边），满足 \(\tau_i \lt \tau_j\)
则 \(\tau_1, \tau_2 ,\dots , \tau_n\) 为图\(G\)中顶点 \(v_1, v_2, \dots , v_n\) 的一个拓扑排序。（若要求 \(\tau_i \lt \tau_j\) 则成为逆拓扑排序）。
拓扑排序只限制有向边的两个节点上序号的大小关系，通过传递性来保证整个图上的“拓扑关系”。
Lemma 8.1 如果有向图 \(G=(V, E)\) 中有环，则图\(G\)不存在拓扑排序。
反证可推出环上任意节点的拓扑序号都严格大于自身。
此引理揭示了有向图中环的存在性与拓扑排序的存在性之间的重要关联。
Lemma 8.2 如果有向图 \(G=(V, E)\) 为有向无环图，则图\(G\)必然存在拓扑排序。