图

常见概念

顶点的度

• 无向图的顶点的度定义为经由某顶点$v$ 的边的数量
• 有向图的顶点的度分为入度与出度，分别定义为从顶点$v$ 进入的有向边与离开的有向边的数量。度定义为入度$\mathrm{ID}(v)$ 与出度$\mathrm{OD}(v)$的和

无向图的顶点度之和等于边数的两倍，因为每一条边都占据了两侧顶点的度。

强连通图与强连通分量

对于有向图的顶点$u,v$ ，如果从$u$到$v$与从$v$到$u$都有路径，则称这两个顶点是强连通的。如果一个图的任意顶点都强连通，则称这个有向图是强连通图。有向图的极大强连通子图称为强连通分量。

如果一个有向图存在某个顶点只有出度或者只有入度，那么这个顶点单独也构成一个强连通分量。

生成树

包含所有顶点的极小连通子图称为这个连通图的生成树

稠密图与稀疏图

一般认为图$G$满足

$$|E|<|V|\log_2|V|$$

可视为稀疏图

• 完全无向图的度总边数:

  假设$n$阶完全图的总边数为$A_n$ , 满足递推:

  $$\begin{cases} A_1 = 1 \\ A_n = A_{n-1} +n-1 \end{cases}$$

  求和得

  $$A_n = \frac{n(n-1)}{2}$$

图的存储方式

邻接矩阵

$$A[i][j] = \begin{cases} 1&(v_i,v_j)\in E\\ 0&(v_i,v_j)\notin E \end{cases}$$

对于带权的图，通常将邻接矩阵的元存为权，将不含边的位置存为$0$ 或 $\infty$

$$A[i][j] = \begin{cases} w_{ij}&(v_i,v_j)\in E\\ 0\,\text{or}\,\infty&(v_i,v_j)\notin E \end{cases}$$

Corollary: 设图$G$的邻接矩阵为$A$， $A^n$的元素$A^n[i][j]$ 代表从顶点$i$到顶点$j$的，长度为$n$的路径数量

$$A^2[i][j] = \sum_{k\in V}\delta_{ik}\delta_{kj}$$

代表从顶点$i$到 途经点$k$再到顶点$j$ 的有效路径个数

$$A^n[i][j] = \sum_{k1,\cdots,k_{n-1}\in V}\delta_{ik_1}\left(\prod{\delta_{k_rk_s}}\right)\delta_{k_n j}$$

• 有向图的邻接矩阵的出边对应行的元素，入边对应列的元素
• 邻接矩阵适合用于稠密图的存储。存储稀疏图时比较浪费空间。邻接矩阵的空间复杂度总为 $\mathcal{O}(|V|^2)$

邻接表

邻接表由顶点表与边表组成，顶点表是一个线性表，存储顶点信息与边表的头指针；边表是一个链表，两个指针域分别存储当前出边(无向表为经过顶点的边)指针与指向下一个出边的结点指针

• 对于稀疏图，邻接表可以极大节省空间复杂度，存储的空间负责度为$\mathcal{O}(|V|+|E|)$(有向图)， $\mathcal{O}(|V|+2|E|)$(无向图)
• 邻接表的边删除，求顶点出度/入度等操作都需要遍历整个邻接表，时间复杂度为$\mathcal{O}(|V|+|E|)$
• 建立邻接表的时间复杂度为 $\mathcal{O}(|V|+|E|)$

十字链表

十字链表是一种使用两个链表存储有向图的数据结构。分别为顶点链表与弧链表

• 顶点链表由data数据域、firstin指向第一个以该顶点为弧头的弧的指针、firstout指向第一个以该顶点为弧尾的弧的指针三个数据域构成。
• 弧指针由tailvex弧尾顶点、headvex弧头顶点、hlink指向相同弧头的弧的指针、tlink指向相同弧尾的指针、info存储弧的相关数据域五个数据域构成。

邻接多重表

邻接多重表的顶点表与邻接表类似，边表与十字链表类似。

图的遍历

广度优先搜索(BFS)

BFS类似于树的层序遍历，基本思想为以相邻结点作为"层"，从起始结点出发后依次访问相邻的结点，指导所有可达结点都访问完为止。

BFS的实现思路为:

• 暂存当前层的下一级相邻结点
• 访问当前层的结点
• 进入下一层

因此，BFS的时间复杂度为 $\mathcal{O}(V)$,空间复杂度在最坏的情况下是 $\mathcal{O}(|V|)$。 如果使用邻接矩阵进行存储时，查询每个顶点的邻接点的时间复杂度为 $\mathcal{O}(|V|)$，总时间复杂度为 $\mathcal{O}(|V|^2)$

BFS可以实现的算法

• 单源最短路径问题

• 广度优先生成树

深度优先搜索(DFS)

DFS的实现方式类似于树的先序遍历，尽可能深的搜索并访问图。

• DFS的实现思路为递归，空间复杂度最坏的情况下为 $\mathcal{O}(|V|)$。
• 不管是BFS还是DFS, 遍历整个图的时间与空间开销都是相同且取决于图存储方式的，使用邻接矩阵的总时间复杂度为 $\mathcal{O}(|V|^2)$, 采用邻接表的总时间复杂度为$\mathcal{O}(|V|+|E|)$。

图的应用

最小生成树算法

对于带权连通无向图 $G$，具有最小总权重的生成树称为图 $G$的最小生成树(MST)

最小生成树有以下特征:

• 如果图有权值相同的边，那么最小生成树可能不唯一；如果图的任意两条边权值都不同，那么最小生成树唯一。
• 不同的最小生成树的总权值仍相等且为最小值
• 最小生成树的边等于顶点数减一(树的性质)

Prim 算法

Prim算法 -- 从选定的一个顶点出发，基于贪婪算法选择已经过的顶点的相邻顶点的最短边相连

Kruskal算法

Kruskal算法 -- 按照最短边相连的原则将最短边相连，连接前判断是否构成环，如果不构成环就进行连接，如果构成了环就进行更长的边的连接。 Kruskal算法中的环检索不是通过DFS实现，而是通过并查集检索先序元素是否出现实现。

最短路径问题

松弛化操作:

对于图，寻找到一个顶点满足两弧之和小于第三弧，再进行最短距离更新到操作，称为松弛化。

d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);

Dijkstra算法

Dijkstra算法通过贪心算法+更新最短路径表实现，每一步走过当前结点的最短出边后更新最短路径表。

因此，Dijkstra不适用于负边权的图，存在负边权则无法发现最短边。

Floyd算法

Floyd算法维护了一个矩阵，在初始化的时候为邻接矩阵，再遍历所有点，每一个点都进行松弛化操作得到相对较短的路径，全部遍历完后的矩阵就是最短路径表。

Floyd算法能对于负边权图适用，但是不允许存在负边权环

两个算法的空间复杂度都为$\mathcal{O}(|V|^3)$

有向无环图(DAG)

二叉树与DAG的转换

二叉树与DAG的转换相当于把相同的子树结构商去

拓扑排序

拓扑排序基于AOV网： 不含权的有向无环图，每一个顶点代表一个活动，并使用有向边表示活动先后顺序。

• 每一个AOV网存在一个或者多个拓扑排序
• 有向环没有拓扑排序，只有DAG才能形成拓扑排序。

拓扑排序的执行思路为(Kahn算法):

• 选择入度为0的顶点进入队列
• 删除这个顶点与相连的边
• 进入下一轮

拓扑排序和其他图遍历的时间复杂度类似，都与图存储的形式相关。使用邻接表的时间复杂度为$\mathcal{O}(|V|+|E|)$, 使用邻接矩阵的时间复杂度为 $\mathcal{O}(|V|^2)$

DFS实现拓扑排序

关键路径

在带权有向图中，顶点代表事件，边权代表活动的时间开销。这类图称为AOE图. AOE图中通常只设置一个入度为0的点为源点，作为工程起点；一个出度为0的点为汇点，作为工程终点。

AOE图有六个个重要的概念，分别为:

• 事件 $v_k$ 的最早发生时间 $v_e(k)$: 从源点到当前顶点的最长路径。

• 活动 $a_i$ 的最早发生时间 $e(i)$ : 对应弧起点的时间最早发生时间，相当于这个弧的前序最长距离。

• 关键路径: 从源点到汇点的最长距离。意味着整个工程的完结，时间不能短于这个总权值。关键路径上的活动称为关键活动

以下这两个DDL概念的定义是从关键路径反过来定义的

• 事件 $v_k$ 的最晚发生时间$v_l(k)$: 保证所有后继事件有足够时间发生的最晚时间。可以通过关键路径(总工程的DDL减去后继最长的路径进行计算)
  对于活动也有相同的定义

• 活动 $a_l$ 的最晚发生时间$l(i)$: 定义为弧尾事件的最晚发生时间减去活动的耗时。也就是在最后DDL期限下，开始执行活动$a_l$的时间。

• 活动 $a_l$ 的时间余量定义为活动的最晚发生时间与最早发生时间的差值$d(i) = l(i)-e(i)$。如果时间余量为0，则说明只能在一个时间点执行，这种活动称为关键活动。