ch6 图¶

1. 基本概念¶

【邻接】同一条边的两个顶点，彼此邻接。

【自环】同一顶点自我邻接，构成自环。

【简单图】不含自环及重边，即为简单图。

【度】顶点与其所属的便，彼此关联，与同一顶点关联的边数称为该顶点的度。

【无向边】若邻接顶点 \(u\) 和 \(v\) 的次序无所谓，则 \((u,v)\) 为无向边。

【无向图】所有边均为无方向的图，即为无向图。

【有向边与有向图】有向图中均为有向边，\(u\)、\(v\) 分别称作边 \((u,v)\) 的尾、头。

【混合图】无向边、有向边并存的图，称作混合图。

【平面图】可嵌入于平面的图。

【路径】\(\pi = <v_0, v_1,..., v_k>\)，长度 \(|\pi| = k\)。

【简单路径】\(v_i\ne v_j\)，除非 \(i=j\)。

【环 / 环路】\(v_0 = v_k\)。

【欧拉环路】\(|\pi| = |E|\)，即各边恰好出现一次。

【哈密尔顿环路】\(|\pi| = |V|\)，即各顶点恰好出现一次。

【支撑树】图 \(G = (V;E)\) 的子图 \(T = (V;F)\) 若是树，即为其支撑树。同一图的支撑树，通常并不唯一。

【带权网络】各边 \(e\) 均有对应的权值 \(wt(e)\)，则为带权网络。

【最小支撑树】同一网络的支撑树中，总权重最小者为最小支撑树（\(\tt MST\)）。

【欧拉公式】\(v-e+f-c=1\)

【邻接矩阵】记录顶点之间的邻接关系。矩阵元素与图中可能存在的边一一对应：

\(A(v,u) = 1\)，若顶点 \(v\) 与 \(u\) 之间存在一条边；
\(A(v,u) = 0\)，若顶点 \(v\) 与 \(u\) 之间不存在边。
在只考察简单图的情况下，对角线统一设置为 \(0\)。
优点：直观，易于理解和实现；适用范围广泛，尤其适用于稠密图；判断两点之间是否存在边 \(\cal{O} (1)\)；获取顶点的度数 \(\cal{O}(1)\)，添加 / 删除边后更新度数 \(\cal{O}(1)\)。
缺点：空间复杂度为 \(\Theta(n^2)\)，与图中实际的边数无关；平面图的边数 \(e \le 3n-6\)，此时空间利用率约为 \(1/n\)，即稀疏图空间利用率低。
适用于：经常检测边的存在；经常做边的插入 / 删除；图的规模固定；稠密图。

【关联矩阵】记录顶点与边之间的关联关系。

【邻接表】将邻接矩阵的各行组织为链表，只记录存在的边。

空间复杂度：有向图 \(\cal{O}(n+e)\)；无向图 \(\cal{O}(n+2e) = O(n+e)\)；平面图 \(\cal{O}(n+3n) = O(n)\)。
适用于：经常计算顶点的度数；顶点数目不确定；经常做遍历；稀疏图。

【广度优先遍历】始自顶点 \(s\) 的广度优先遍历

访问顶点 \(s\)；
依次访问 \(s\) 所有尚未访问的邻接顶点；
依次访问它们尚未访问的邻接顶点，如此反复，直至没有尚未访问的邻接顶点。
适用于：连通图的 BFS 支撑树；非连通图的 BFS 支撑森林；连通性检测；无向图环路检测 / 二分图判定；顶点之间可达性检测 / 路径求解；顶点之间的最短距离；直径/ 半径 / 围长 / 中心。

【深度优先遍历】始自顶点 \(s\) 的深度优先遍历

访问顶点 \(s\)；
若 \(s\) 尚有未被访问的邻居，则任取其一 \(u\)，递归执行 \(\tt DFS(u)\)，否则返回。
若此时尚有顶点未被访问，任取这样的一个顶点作起始点，如此反复，直至所有顶点都被访问到。
适用于：连通图的 DFS 支撑树；非连通图的 DFS 支撑森林；连通性检测；无向图环路检测 / 二分图判定；有向图环路检测；顶点之间可达性检测 / 路径求解；欧拉回路；拓扑排序；双连通分量分解；强连通分量分解。

【有向无环图应用】

【拓扑排序】任给有向图，尝试将所有顶点排成一个线性序列，使其次序须与原图相容，即每一顶点都不会通过边指向前驱顶点。

每个 DAG 对应于一个偏序集；拓扑排序对应于一个全序集。所谓的拓扑排序，即构造一个与指定偏序集相容的全序集。
可以拓扑排序的有向图，必定无环。任何 DAG，都存在至少一种拓扑排序。
有限偏序集必有极值元素。
零出度算法：对图 G 做 DFS，其间
- 每当有顶点被标记为 VISITED，则将其压入栈 \(S\)，
- 一旦发现有后向边，则报告 NOT_A_DAG 并退出。
DFS 结束后，顺序弹出栈 \(S\) 中的各个顶点。各顶点按 \(fTime\) 逆序排列，即是拓扑排序。