408数据结构-图论

1. 基本概念

• 图 $G$ 由顶点集 $V$ 和边集 $E$ 组成，记为 $G = \left(V,E\right)$

• $V(G)$ 表示 $G$ 中顶点的有限非空集（线性表可以是空表，树可以是空树，图不能是空图，顶点集必须是非空的），$|V|$ 表示图中的顶点数。

• $E(G)$ 表示 $G$ 中顶点之间的关系/边集合（边集可以为空），$|E|$ 表示图中的边数。

简单图/多重图

如果图满足：

1. 不存在重复边
2. 不存在顶点到自身的边

则称为简单图，反之则称为多重图

子图

如果有两个图 $G = \left(V,E\right)$ 和 $G' = \left(V', E'\right)$ ，若 $V' \subset V$ 且 $E' \subset E$，则称 $G'$ 为 $G$ 的子图。

若满足 $V(G') = V(G)$，则 $G'$ 为 $G$ 的生成子图。

注意，并非 $V$ 和 $E$ 的任何子集都能构成 $G$ 的子图，比如 $E$ 中的边涉及到的边的点没有在 $V$ 中。

权/网

一个图中，每条边都可以标上具有某种含义的数值，表示边的权值，边上有权值的图为带权图/网。

稠密图/稀疏图

边数很少的图叫做稀疏图，反之叫做稠密图。稀疏和稠密是模糊的概念，并且是相对而言的。一般来说，满足 $|E| < |V| \log |V|$ 的图叫做稀疏图。

路径

顶点 $v_p$ 到顶点 $v_q$ 之间的路径指的是一个顶点序列。关联的边也可以理解为路径的构成要素。

路径上的边的数目称为路径长度。

第一个顶点和最后一个顶点相同的路径称为回路/环。如果一个图有 $n$ 个顶点，且有大于 $n-1$ 条边，则该图一定存在环。

简单路径、简单回路

在路径序列中，顶点不重复出现的路径称为简单路径。

除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

距离

从顶点 $u$ 出发到顶点 $v$ 的最短路径如果存在，那么这个路径的长度就称为 $u$ 到 $v$ 的距离。

如果 $u$ 到 $v$ 不存在路径，那么距离记为无穷 $\infin$。

1.1 有向图

• 有向边也称为弧，记为 $\left<v,w\right>$
  • $v$ 称为弧尾，$w$ 称为弧头
  • $\left<v,w\right>$ 称为从 $v$ 到 $w$ 的弧，也称 $v$ 邻接到 $w$

完全图

对于有向图，$|E|$ 取值范围为 $[0,n(n-1)]$，有 $n(n-1)$ 条弧的有向图称为有向完全图。有向完全图中任意两个顶点之间都存在方向相反的两条弧。

强连通

• 强连通：若 $v$ 到 $w$ 和 $w$ 到 $v$ 都有路径存在，则 $v$ 和 $w$ 是强连通的。
• 强连通图：如果图中任意两个点都是强连通的，则称图是强连通图。
• 强连通分量/极大强连通子图

度

点 $v$ 有出度和入度，出度是以点 $v$ 为起点的有向边数目，记为 $OD(v)$。入度是以点 $v$ 为终点的有向边数目，记为 $ID(v)$。点 $v$ 的度等于其入度和出度之和，即 $TD(v) = ID(v) + OD(v)$。

有向图满足 $\sum ID(v_i) = \sum OD(v_i) = |E|$。

有向树

一个顶点的入度为 $0$，其余顶点的入度均为 $1$ 的有向图，称为有向树。

1.2 无向图

• 无向边简称为边，记为 $(v,w)$
  • $w$ 和 $v$ 互为邻接点
  • $(v,w)$ 依附于 $w$ 和 $v$
  • $(v,w)$ 和 $v$，$w$ 相关联

完全图

对于无向图，$|E|$ 取值为 $[0,\frac{n(n-1)}{2}]$，有 $\frac{n(n-1)}{2}$ 条边的无向图称为无向完全图。无向完全图中任意两个顶点之间都存在边。

连通

• 连通：若 $v$ 到 $w$ 有路径存在，则 $v$ 和 $w$ 是连通的。
• 连通图/非连通图：如果图中任意两个点都是连通的，则称图是连通图，反之则成为非联通图。
• 连通分量/极大连通子图：相当于图中的连通块。

（无向图中讨论连通性，在有向图中讨论强连通性）

生成树/生成森林

连通图中，包含全部顶点，的极小连通子图。如果图中点数有 $n$，则生成树有 $n-1$ 条边。

在非连通图中，每一个连通分量的生成树构成了整个非连通图的生成森林。

度

无向图中，点 $v$ 的度是依附于点 $v$ 的边的条数，记为 $TD(v)$。

$\sum TD(v_i) = 2|E|$。

2. 图的存储

2.1 邻接矩阵法

对于非带权图：

$$A_{i,j} = \begin{cases} 1, & \left(v_i, v_j\right) \text{ 或 } \left<v_i, v_j\right> \text{ 是 } E(G) \text { 中的边 } \\ 0, & \left(v_i, v_j\right) \text{ 或 } \left<v_i, v_j\right> \text{ 不是 } E(G) \text { 中的边 } \end{cases}$$

对于带权图：

$$A_{i,j} = \begin{cases} w_{i,j}, & \left(v_i, v_j\right) \text{ 或 } \left<v_i, v_j\right> \text{ 是 } E(G) \text { 中的边 } \\ 0 \text{ 或 } \infin, & \left(v_i, v_j\right) \text{ 或 } \left<v_i, v_j\right> \text{ 不是 } E(G) \text { 中的边 } \end{cases}$$

注意第二个点：

无向图的邻接矩阵是对称矩阵，这是充要的，如果一个邻接矩阵不是对称的那么必然是有向图：

邻接矩阵表示图一定是唯一的。

对于无向图，第 $i$ 行或者第 $j$ 列非 $0$ 或是 $\infin$ 元素个数正好是点 $TD(v_i)$。

对于有向图，第 $i$ 行非 $0$ 或是 $\infin$ 元素个数正好是 $OD(v_i)$，第 $i$ 列非 $0$ 或是 $\infin$ 元素个数正好是 $ID(v_i)$。

枚举的时候需要注意枚举顺序，枚举行的话相当于是对列进行求和：

稠密图适合用邻接矩阵。

设图的邻接矩阵为 $A$，那么 $A^n$ 的元素 $A^n_{i,j}$ 表示从 $i$ 到 $j$ 长度恰好为 $n$ 的路径数目。

2.2 邻接表法

邻接表有两个东西，一个是顶点表一个是边表，表中节点分别是顶点表结点和边表结点，其中顶点表结点包含顶点域和边表头指针，边表结点包含邻接点域和指针域：

对于无向图，空间复杂度为 $O(|V| + 2|E|)$。对于有向图，空间复杂度为 $O(|V| + |E|)$。

邻接表法时候存储稀疏图。

2.3 十字链表

十字链表专门用于存储有向图，有两个部分：弧结点和顶点结点。

$firstout$ 去跟连出去的边，$firstin$ 去跟连进来的边。

$tailvex$ 和 $headvex$ 构成了一个边。

$tlink$ 连接弧尾相同的边，相当于邻接表法的表示。$hlink$ 连接弧头相同的边。

2.4 邻接多重表

邻接多重表专门用于无向图，也有两部分：边结点和顶点结点。

总的来说还是类似于邻接表，相比于十字链表少维护了 $firstin$ （而对于无向图也没必要维护这个），然后边之间依然是头相同的连接在一块，尾相同的也连接在一块。

3. 图的遍历

图的遍历要对图中所有的点访问一次，且仅访问一次。

使用邻接表存储时，DFS 和 BFS 的时间复杂度均为 $O(|V|+|E|)$。使用邻接矩阵存储时，DFS 和 BFS 的时间复杂度均为 $O(|V|^2)$。

广度优先生成树/森林：根据 BFS 的顺序构建出来的树/森林

深度优先搜索树/森林：根据 DFS 的顺序构建出来的树/森林

DFS和BFS序列就是 DFS 和 BFS 到每个点的顺序。值得注意的是，遍历必须遵循规则，比如 DFS 必须往前走不了了才能回溯，BFS 必须遍历完同层并且按上一层的遍历顺序继续展开下一层。

对同样的一个图，基于邻接矩阵的遍历得到的 DFS 和 BFS 序是唯一的，基于邻接表的遍历得到的是不唯一的，因为邻接表存储顺序和边的输入次序有关。但是如果邻接表是给定的，那么遍历顺序就固定了：

4. 图的应用

4.1 最小生成树

若图 $G$ 存在权值相同的边，则 $G$ 的最小生成树可能不唯一。当图 $G$ 中的各边权值互不相等时，$G$ 的最小生成树是唯一的。

最小生成树中所有边的权值之和最小，但不能保证任意两个顶点之间和路径是最短路径。

4.1.1 Prim

将当前所有的结点分成两部分：已经被选入的和未被选入的。然后每次将未被选入的点选入，选择已经被选入的点距离最近的那个未被选入的点。

时间复杂度 $O(|V|^2)$，不依赖 $|E|$，因此比较适合求边稠密的图的最小生成树。

4.1.2 Kruskal

将所有边的边权从小到大排序，然后逐个选择。如果要选择的边的两端点已经在同一个连通块内了，则跳过，选下一个。

时间复杂度是 $O(|E|\log_2|E|)$，不依赖于 $O(|V|)$，因此 Kruskal 算法适用于边稀疏而顶点多的图。

4.2 最短路

如果一个图有负环（换上各个边的权值相加为负数），那么这个图上的最短路是没有定义的。

4.2.1 Dijkstra

类似 Prim，也是把当前结点分成已经选择的和未被选择的。每次选择一个结点后，不同于 Prim 那样把该结点连出去的结点到该节点的边权作为后续选择的依据，而是将连出去的结点到原点的距离作为后续选择的依据。

Prim 相当于每次选择权值最小的边，将其连接到已经构建的生成树上。而 Dijkstra 是每次找到离源点距离最近的点接入到已经构建的最短路树上，同时以这个点为基础再去更新源点到其他顶点的距离。

在 408 中认为 Dijkstra 默认是没有堆优化的，所以时间复杂度是 $O(|V|^2)$ 的（对于邻接矩阵表示是这样，对于邻接表表示也是这样（因为要选取离源点距离最近的点，这个过程占大头））

Dijkstra 不适用于含有负权的图。

4.2.2 Floyd

Floyd 的最外层循环相当于是一个不断迭代的过程，每迭代一次，就从最短路径上多考虑了一个点，经过 $n$ 次迭代就可以得出最短路。

我们称 $path_k$ 表示已经考虑了前 $k$ 个点之后的最短路径。那么有 $path_{k-1}$ 路径上的点一定是 $path_{k}$ 路径上的点的子集。

跑完 Floyd 算法之后，我们可以对每个点 $i$，判断点 $i$ 到点 $i$ 之间的最短距离是否为 $0$，如果 $<0$ 的话说明存在负环。

Floyd 算法的时间复杂度为 $O(|V|^3)$。

4.3 有向无环图

4.3.1 拓扑排序

AOV网：在有向无环图中，整个图表示一个工程，顶点表示一个活动，并且每个边没有权值，仅表示活动之间先后的依赖关系。这种有向无环图被称为 AOV 网。

拓扑排序：指的是一个有向无环图顶点组成的序列，其满足：

• 每个顶点出现且仅出现一次
• 如果顶点 $A$ 排在顶点 $B$ 前面，那么不存在从 $B$ 到 $A$ 的路径。

使用邻接表存储时，拓扑排序的时间复杂度为 $O(|V|+|E|)$。使用邻接矩阵存储时，拓扑排序的时间复杂度为 $O(|V|^2)$。

求拓扑排序有两种方法：

• 第一种基于 BFS，即每次选择当前入度为 $0$ 的点，然后把这个点连出去的边去掉，更新其他点的入度，然后再继续选择。如果改为每次选择出度为 $0$ 的点，那么得到的序列叫做逆拓扑排序。
• 第二种基于 DFS，即对入度为 $0$ 的点进行 DFS，在回溯时，把当前遍历到的点输出。这样的到的是逆拓扑排序。

对于一个图来说，如果其邻接矩阵是一个三角矩阵，那么就存在拓扑排序。但是反之不一定成立，比如：

如果这里没有说是“有序”的拓扑排序序列，那么邻接矩阵就会使一般的了，需要重新编号才能使得其邻接矩阵变为三角矩阵。

4.3.2 关键路径

AOE网：在有向无环图中，每个顶点一个事件，每个有向边表示一个活动，并且有向边有权值，表示完成这个活动所需要的时间。这种有向无环图被称为 AOE 网。在 AOE 网中，仅有一个入度为 $0$ 的点，被称为开始顶点/源点，仅有一个出度为 $0$ 的点，表示结束顶点/汇点。

AOE 网用边表示活动，AOV 网用顶点表示活动。

关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。

事件最早发生时间

对于事件 $v_k$，其最早发生时间是指从源点 $v_1$ 到顶点 $v_k$ 的最长路径长度，表示为 $v_e(k)$。

可以在拓扑排序的基础上计算 $v_e$ 的值。初始时有 $v_e(i) = 0$（$i = 1\dots n$）。然后每次遍历到一个入度为 $0$ 的点 $v_j$ 时，对于其后继顶点 $v_k$，令 $v_e(k) = \min(v_e(j) + Weight(v_j, v_k), v_e(k))$。

事件最迟发生时间

对于事件 $v_k$，其最迟发生时间表示该事件最多可以延后进行且不会影响整个工程完成的时间，表示为 $v_l(k)$。

可以在逆拓扑排序的基础上计算。初始时有 $v_l(i) = v_e(n)$（$i = 1\dots n$）。对于遍历到的每一个出度为 $0$ 的点 $v_j$，对于其前驱结点 $v_k$，令 $v_l(k) = v_l(j) - Weight(v_k, v_j)$。

活动最早开始时间

如果边 $\left<v_k, v_j\right>$ 表示活动 $a_i$，则 $e(i)$ 表示其最早开始时间，且 $e(i) = v_e(k)$。

活动最迟开始时间

如果边 $\left<v_k, v_j\right>$ 表示活动 $a_i$，则 $l(i)$ 表示其最晚开始时间，且 $l(i) = v_l(j) - Weight(v_k, v_j)$。

活动的时间容量

表示在不增加完成整个工程所需总时间的情况下，活动可以拖延的时间。对于活动 $a_i$，其时间容量为 $l(i) - e(i)$。

如果一个活动的时间容量为 $0$，那么这个活动就是一个关键活动。

由于求关键路径的过程中使用了拓扑排序，因此求关键路径也可以算作判环的方法。

4.3.3 公共子式

可以用有向无环图来描述含有公共子式的表达式。比如：

在表达式的有向无环图表示中，不可能出现重复的操作数顶点。

5. 做题

5.1 归类

如果一个无向图有 $n$ 个点：

• 若边数小于 $n-1$，则图必然是非连通图。
• 如果是非连通图，则最多有 $\frac{(n-1)(n-2)}{2}$ 边。（$n-1$ 个点构成完全图，然后另一个点孤立）（$n$ 个点的图，如果有 $\frac{(n-1)(n-2)}{2} + 1$ 条边，那么必然是连通的）（如果问给定边数的图非连通的话，最少有多少个点，也是按这种方法求）

如果一个有向图有 $n$ 个点：

• 在强连通的条件下最少有 $n$ 条边，构成一个环路

5.2 错题

在邻接表上遍历所有边的时候，还会遍历所有点

• （X）若有向图不存在回路，即使不使用访问标志位，同一结点也不会被访问两次

一个反例：

A：如果不是简单路径的话，那么路径上就会存在相同的点，那么就说明从一个点出发然后再回来，路径长度反而缩短了，这意味着出现了负环，而在存在负环的图上最短路径是没有定义的。

D：对于路径，如果我们说路径 $p_1$ 是路径 $p_2$ 的子集，并不意味着 $p_1$ 上的点的集合是 $p_2$ 上的点的集合的子集，而是意味着 $p_1$ 是 $p_2$ 的前缀。

Ⅱ：注意是对每对顶点都求最短路

Ⅲ：这里的含有负边的回路指的是最小环

对于Ⅲ的一个反例：

仅含有一个点的图（且边集为空）也应该被视为是一个强连通图，在这上面应该是可以进行拓扑排序的。但是这道题却没考虑这一点。这似乎存在争议。

Ⅲ：有可能较小边权两端点已经被选择，于是可能出现某条边的权值超过未选边的权值

Ⅳ：一个反例如下：

2）由于一个点也可以视为一个强连通分量，因此有 $7$ 个