图 | DS
基本概念
图 G 由顶点的有限非空集 V 和边集 E 组成 → G = (V, E)
线性表可以是空表，树可以是空树，但图不可以是空图（边集可空，顶点集一定非空）
|V| 表示 G 中顶点 vertex 的个数，|E| 表示 G 中边 edge 的条数
有向图：每条边都有方向
无向图：每条边都没有方向
弧/有向边
有向图中的边，是顶点的有序对，记为 <$v_i$, $v_j$>，$v_j$ 为弧头，$v_i$ 为弧尾
<$v_i$, $v_j$> 称从 $v_i$ 到 $v_j$ 的弧，也称 $v_i$ 邻接到 $v_j$
无向图中，边是顶点的无序对，记为 ($v_i$, $v_j$)，等价于有向图中 <$v_i$, $v_j$> 和 <$v_j$, $v_i$> 两条边
可以说 $v_i$ 和 $v_j$ 互为邻接点
边 ($v_i$, $v_j$) 依附于 $v_i$ 和 $v_j$，或称边 ($v_i$, $v_j$) 和 $v_i$、$v_j$ 相关联
度 TD($v$)：无向图中依附于顶点 $v$ 的边的条数
入度 ID($v$)：有向图中指向顶点 $v$ 的边的条数
出度 OD($v$)：有向图中由顶点 $v$ 发出的边的条数
无向图的全部顶点的度的和等于边数的 2 倍（因为每条边与两个顶点相关联）
有向图的全部顶点的入度之和 = 出度之和 = 边数
简单图：不存在重复边（平行边）+ 不存在顶点到自身的边（自循环）
多重图：存在平行边或自循环
数据结构中仅讨论简单图
无向完全图：具有 $\frac{n(n-1)}{2}$ 条边的无向图（任意两顶点间都存在边）
有向完全图：具有 $n(n-1)$ 条边的有向图（任意两顶点间都存在方向相反的两条弧）
子图
子图的点集和边集是父图点集和边集的子集（必要条件）
但并非父图点集和边集的任何子集都能构成子图，因为这样的子集可能不是图
生成子图
子图的点集和父图的点集相同，这样的子图称为父图的生成子图
连通：两顶点间有路径存在，则称这两顶点连通
强连通：两顶点间双向连通，则称这两顶点强连通
连通图：任意两顶点连通，则称为连通图，否则称为非连通图
强连通图：任意两顶点强连通，则称为强连通图，否则称为非强连通图
在无向图中讨论连通性，在有向图中讨论强连通性
连通分量 = 极大连通子图：连通 + 边尽可能多
强连通分量 = 极大强连通分量：强连通 + 边尽可能多
生成树：包含图中全部顶点的一个极小连通子图（全部顶点 + 连通 + 边尽可能少）
生成森林：非连通图的各连通分量的生成树构成了该非连通图的生成树林
有向树：一个顶点的入度为 0、其余顶点的入度均为 1 的有向图
非连通图边最多的情况：由 $n-1$ 个顶点构成无向完全图，另一个顶点孤立
强连通图边最少的情况：$n$ 条弧构成一个环路
权：每条边都可以标上具有某种意义的数值，该数值称为该边的权值
网：带权图
路径
顶点 $v_p$ 到顶点 $v_q$ 之间的一条路径是指顶点序列 $v_p$，$v_{i1}$，…，$v_{i2}$，$v_{im}$，$v_q$
关联的边也可理解为路径的构成要素，此时路径定义为由顶点和相邻顶点序偶构成的边所形成的序列
路径长度：路径上边的数目
回路/环：第一个顶点和最后一个顶点相同的路径
简单路径：顶点不重复出现（顶点只经过一次）
简单回路：除首尾顶点外其余顶点不重复出现
稠密图、稀疏图
边数的多少
一般 |E|＜|V|log|V| 时可视为稀疏图
距离
顶点 $u$ 到顶点 $v$ 的距离是 $u$ 到 $v$ 的最短路径（若存在）的长度
若 $u$ 到 $v$ 不存在路径，则记该距离为 ∞
存储结构
邻接矩阵
用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系）。存储顶点之间邻接关系的二维数组称为邻接矩阵。结点数为 $n$ 的图的邻接矩阵是 $n$ 阶方阵
在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点信息等均可省略）
无权图：$A[i][j]=1$ 表示 ($v_i$, $v_j$) 或 <$v_i$, $v_j$> 在图中存在；$A[i][j]=0$ 表示 ($v_i$, $v_j$) 或 <$v_i$, $v_j$> 在图中不存在
带权图：$A[i][j]=w_{ij}$ 表示 ($v_i$, $v_j$) 或 <$v_i$, $v_j$> 在图中存在且权值为 $w_{ij}$；$A[i][j]=0$ 或 $\infin$ 表示 ($v_i$, $v_j$) 或 <$v_i$, $v_j$> 在图中不存在
无向图的邻接矩阵
对称且唯一（对规模特大的邻接矩阵可采用压缩存储。试题若无特别说明，默认上下三角都存储）
第 $i$ 行或第 $i$ 列的非零或非 $\infin$ 元素的个数为顶点 $i$ 的度（非零或非 $\infin$ 元素的个数为总边数的两倍）
有向图的邻接矩阵
非零或非 $\infin$ 元素的个数为总边数
第 $i$ 行非零或非 $\infin$ 元素的个数为顶点 $i$ 的出度，第 $i$ 列非零或非 $\infin$ 元素的个数为顶点 $i$ 的入度
优点：容易确定图中任意两点之间是否有边相连
缺点：要确定图中有多少条边则必须按行、按列对每个元素进行检测，耗时久；稀疏图显然要浪费大量的存储空间
适用：稠密图
空间复杂度：$O(|V|^2)$
设图 $G$ 的邻接矩阵为 $A$，$A^n$ 的元素 $A^n[i][j]$ 等于由顶点 $i$ 到顶点 $j$ 的长度为 $n$ 的路径的数目（离散数学）
邻接表
顶点表(顺) + 边表(链)
对于有向图，边表即为出边表
特点
给定一顶点，很容易找到它的所有邻边
表示不唯一：每个顶点对应的单链表中各边结点链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序
有向图邻接表求给定顶点的出度和出边容易，但求入度和入边需要遍历全部的邻接表（也可采用逆邻接表，就反过来）
若要确定给定两个顶点间是否存在边，在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低
空间复杂度
无向图：$O(|V|+2|E|)$（边会存两次）
有向图：$O(|V|+|E|)$
适用：稀疏图（极大地节省存储空间）
十字链表 (有向图)
顶点表(顺) + 弧表(链)
弧结点：tailvex 指示弧尾顶点编号，headvex 指示弧头顶点编号，hlink 指向弧头相同的下一条弧，tlink 指向弧尾相同的下一条弧，info 存放该弧的相关信息
顶点结点：data 存放数据信息，firstin 指向以该顶点为弧头的第一个弧结点，firstout 指向以该顶点为弧尾的第一个弧结点。仍是顺序存储
出边、入边容易找，出度、入度容易求
表示不唯一，但一个十字链表表示确定一个图
邻接多重表 (无向图)
顶点表(顺) + 边表(链)
边结点：ivex 和 jvex 指示该边依附的两个顶点的编号，ilink 指向下一条依附于顶点 ivex 的边，jlink 指向下一条依附于顶点 jvex 的边，info 存放该边的相关信息
顶点结点：data 存储该顶点的相关信息，firstedge 指向第一条依附于该顶点的边
对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点
遍历
从某一顶点出发，按照某种搜索方法沿着图中的边，对所有顶点访问一次且仅访问一次
BFS
图的广度优先搜索遍历算法是二叉树的层次遍历算法的扩展
空间复杂度：$O(|V|)$
邻接表和邻接矩阵都需借助一个辅助队列
时间复杂度
邻接表：$O(|V|+|E|)$
邻接矩阵：$O(|V^2|)$
BFS 算法求解单源最短路径问题（非带权图）
DFS
类似树的先序遍历
空间复杂度：$O(|V|)$
递归工作栈
时间复杂度
邻接表：$O(|V|+|E|)$
邻接矩阵：$O(|V^2|)$
DFS 可实现拓扑排序，可判断图中是否存在回路
若将输出顶点信息的语句移到退出递归前，则输出的顶点序列是逆拓扑排序
BFS/DFS 序列、广度/深度优先生成树的唯一性
邻接矩阵：唯一（因为同一个图的邻接矩阵存储表示唯一）
邻接表：不唯一（因为同一个图的邻接表存储表示不唯一）
连通图产生树，非连通图产生森林
对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路
遍历与连通性
无向图：调用
BFS(Graph g, int v)或DFS(Graph g, int v)的次数等于该图的连通分量数有向图：不好说。能确定的是，需要多次调用
BFS或DFS才能遍历全部顶点的图是非强连通的
应用
最小 (代价) 树 MST
MST (Minimum-Spanning-Tree)
带权连通无向图的生成树中，边的权值之和最小的那棵生成树
性质：
- MST（树形）不唯一
- MST 的边的权值之和唯一
- MST 的边数为顶点数减 1
Prim 算法和 Kruskal 算法都是基于贪心算法策略的构造 MST 的算法
Prim 算法
- 思路：从某一顶点开始扩展，每次选择离当前生成树距离最近的顶点并入
- 时间复杂度：$O(|V^2|)$
- 适用：边稠密图
Kruskal 算法
思路：按权值递增次序选择“合适”的边来构造，直至所有顶点都在一个连通分量上
“合适”指该边依附的两个顶点分别落在不同的连通分量上
时间复杂度
使用堆存放边：$O(\log_{2}|E|)$
使用并查集描述生成树：$O(|E|log_{2}|E|)$
适用：边稀疏而顶点较多的图
TODO 看不懂：由于生成树 T 中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的结构来描述 T，从而构造 T 的时间复杂度为 $O(|E|log_{2}|E|)$
最短路径
使用 BFS 求解单源最短路径只是对无权图而言
求解带权图最短路径的算法通常依赖一种性质：两点间的最短路径也包含了路径上其他顶点间的最短路径
求最短路径允许图有环（Floyd 算法不允许有带负边的环），并且有向图和无向图都适用
Dijkstra 算法
求单源最短路径（某一顶点到其他各顶点的最短路径）
思路
设两个顶点集合 S、T，S 存放已找到最短路径的顶点，T 存放剩余顶点（初始 S 中只包括源点）
不断从 T 选取与源点路径最近的顶点并入 S，每并入一个都要更新源点到剩余顶点最短路径长度值（以并入的新顶点与源点最短路径为基础计算）
时间复杂度
邻接矩阵、邻接表：$O(|V^2|)$
不适用：带有负权值边的图（因为已并入 S 的点的最短路径无法更新）
也可以求任意两个顶点间的最短路径
寻找从源点到某个特定顶点的最短路径，和求解源点到其他所有顶点的最短路径一样复杂，时间复杂度也为 $O(|V^2|)$
考题只要求求最短路径长度时就不用记录中间顶点
Floyd 算法
求所有顶点间的最短路径
思路
设有 $n$ 个顶点 $v_0$、$v_1$、…、$v_{n-1}$，以 $n$ 阶方阵 $A$ 记录两顶点间的最短路径长度
共有 $n+1$ 个方阵序列 $A^{-1}$、$A^{0}$、…、$A^{n-1}$，其中 $A^{-1}$ 记录初始状态各顶点间的最短路径长度，此后依次尝试在原路径加入 $v_0$、$v_1$ … 作为中间顶点，若能减少路径长度，则以此作为当前最短路径，并在方阵中更新最短路径长度。加入 $v_i$ 更新最短路径后得到方阵 $A^{i}$，经过 $n$ 次迭代后所得到的 $A^{(n-1)}$ 便保存了任意一对顶点间的最短路径长度
$A^{k}[i][j]=min(A^{k-1}[i][j], A^{k-1}[i][k]+A^{k-1}[k][j])$
显然，主对角线始终为 0。另外计算 $A^{i}$ 即加入 $v_i$ 时，第 $i$ 行和第 $i$ 列也不用动
时间复杂度：$O(|V^3|)$
不适用：允许图中带有负权值的边，但不允许有包含负权值边的环
也可用单源最短路径算法来解决每对顶点之间的最短路径问题：
轮流将每个顶点最为源点，并且在所有边权值均非负时，运行一次 Dijkstra 算法
其算法复杂度为 $O(|V|)·O(|V^2|)=O(|V^3|)$
有向无环图描述表达式
DAG (Directed Acyclic Graph)
利用有向无环图 DAG 描述表达式，可实现对相同子式的共享，从而节省存储空间
例如表达式 $((a+b)(b(c+d))+(c+d)e)((c+d)e)$，公共子式为 $(c+d)$ 和 $(c+d)e$
拓扑排序
AOV 网 (Activity On Vertex NetWork)
以顶点表示活动、以弧表示活动的先后次序的无权 DAG
拓扑排序
由一个 DAG 的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
- 每个顶点出现且只出现一次
- 若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径
或定义为：拓扑排序是对 DAG 的顶点的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后面
每个 AOV 网都有一个或多个拓扑排序序列
对 AOV 网进行拓扑排序的常用算法思路：
从 AOV 中选择一个没有前驱的顶点并输出
从网中删除该顶点和所有以它为起点的有向边
重复前两步，直到当前 AOV 网为空或当前网中不存在无前驱的顶点为止
后一种情况说明有向图中必然存在环
入度为 0 的顶点，说明没有前驱活动或前驱活动都已完成，则工程可以从这个顶点所代表的活动开始或继续
拓扑排序算法时间复杂度
邻接表：$O(|V|+|E|)$
邻接矩阵：$O(|V^2|)$
DAG 中存在有多个直接后继的顶点，则拓扑排序的结果通常不唯一
但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果唯一
利用 DFS 也可实现拓扑排序
逆拓扑排序步骤：
- 从 AOV 中选择一个无后继（出度为 0）的顶点并输出
- 从网中删除该顶点和所有所有以它为终点的有向边
- 重复前两步，直到当前 AOV 网为空
关键路径
AOE 网 (Activity On Edge Network)
以顶点表示事件，以有向边表示活动，以边的权值代表完成该活动开销的带权 DAG
AOE 网性质
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生
在 AOE 网中仅有一个入度为 0 的顶点，称为开始顶点（源点），代表整个工程的开始
网中也仅存一个出度为 0 的顶点，称为结束顶点（汇点），表示整个工程的结束
在 AOE 网中，有些活动是可以并行进行的
从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同
完成不同路径上的活动所需时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才算结束
关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径
关键活动：关键路径上的所有活动
完成整个工程的最短时间 = 关键路径的长度
通过加快关键活动来缩短整个工程的工期
但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能变成非关键活动
关键路径不一定唯一，且对于有几条关键路径的网，只加快部分关键路径并不能缩短整个工期，只有加快所有关键路径才能达到缩短工期的目的
事件 $v_k$ 的最早发生时间 $ve(k)$
从源点到 $v_k$ 的最长路径长度
决定了所有从 $v_k$ 开始的活动能够开工的最早时间
可按 $ve(源点)=0$、$ve(k)=max(ve(j)+weight(v_j, v_k))$ 从前往后进行递推计算。其中 $v_j$ 为 $v_k$ 的任意前驱，$weight(v_j, v_k)$ 为 <$v_j$, $v_k$> 的权值
可在求拓扑排序的过程基础上求解
事件 $v_k$ 的最迟发生时间 $vl(k)$
在不推迟整个工程完成的前提下，即保证它的后继事件 $v_j$ 在其最迟发生时间 $vl(j)$ 能够发生时，该事件最迟必须发生的时间
可按 $vl(汇点)=ve(汇点)$、$vl(k)=min(vl(j)-weight(v_k, v_j)$ 从后往前进行递推计算。其中 $v_k$ 为 $v_j$ 的任意前驱
可在求逆拓扑排序的过程基础上求解
活动 $a_i$ 的最早发生时间 $e(i)$
该活动弧的起点事件的最早发生时间
活动 $a_i$ 的最迟发生时间 $l(i)$
该活动弧的终点事件的最迟发生时间与该活动所需时间之差
活动 $a_i$ 完成的时间余量 $d(i)$
在不增加完成整个工程所需总时间的情况下，活动 $a_i$ 可以拖延的时间
$d(i)=l(i)-e(i)$
若一个活动的时间余量为 0，说明该活动必须如期完成，否则就会拖延整个工程的进度
$l(i)-e(i)=0$ 即 $l(i)=e(i)$ 的活动就是关键活动
求关键路径的一般步骤
从源点出发，令 $ve(源点)=0$，按拓扑排序求其余顶点的 $ve()$
从汇点出发，令 $vl(汇点)=ve(汇点)$，按逆拓扑排序求其余顶点的 $vl()$
根据各顶点的 $ve()$ 求所有弧的 $e()$
根据各顶点的 $vl()$ 求所有弧的 $l()$
求 AOE 网中所有活动的 $d()$，找出所有 $d()=0$ 的活动构成关键路径
这里求关键路径要满足：路径上的所有活动都是关键活动，即 $d()=0$ 的活动，并且路径长度等于最大路径长，即 $vl(汇点)$ 或 $ve(汇点)$（特别注意：路径上所有活动都是关键活动 ≠ 此路径是关键路径）
实际上求出各顶点 $ve()$ 后就能得到关键路径（可能有多条）
求关键路径还是得多练习，有些地方说不清楚，需要熟练度
练手：
刷题笔记
若具有 $n$ 个顶点的图是一个环，则它有 $n$ 棵生成树
若一个具有 $n$ 个顶点、$e$ 条边的无向图是一个森林，则该森林中必有 $n - e$ 棵树
无向图的全部顶点的度的和等于边数的 2 倍，因为每条边和两个顶点相关联
$n$ 个顶点的非连通图边最多的情况：由 $n-1$ 个顶点构成一个完全图，另一个孤立
$n$ 个顶点的强连通图边最少的情况：$n$ 条边构成一个环路
只有邻接矩阵的表示唯一
无向图邻接表中边会存两次
练一下只根据邻接表（即不画图）写出的 BFS 和 DFS 序列（P210 选择08）
不画图即按算法思路走，可以节省画图时间；画图比较直观，不容易错，但也要结合邻接表的边表结点顺序
根据邻接表画出深度优先生成树和广度优先生成树（P211 综合01）
画不画图跟上一条一样。建议第一遍做不画图，第二遍检查时画图
连通分量、极大连通子图、极小连通子图、生成树
MST 一定唯一的两种情况：① 图中各边的权值互不相等；② 图本身是一棵树
图中存在权值相同的边，其 MST 可能不唯一
讨论拓扑排序和关键路径的前提是：DAG（有向 + 无环）、连通
只讨论拓扑排序时使用的是 AOV 网，无权
讨论关键路径使用的是 AOE 网，有权
可以判断是否有环/回路
DFS
有向图：若从某个顶点 u 出发，在 DFS(u) 结束之前出现一条从顶点 v 到 u 的边，由于 v 在生成树上是 u 的子孙，则图中必定存在包含 u 和 v 的环
无向图：没想好
拓扑排序
存在无法找到下一个可以加入拓扑序列的顶点，则说明此图存在回路
求关键路径
求关键路径的算法本身无法判断是否有环
判断是否有环是求关键路径的第一步——拓扑排序
求两个顶点的最短路径上经过的顶点序列
选择题可以直接把选项的路径长度都求出来，选最短的就行
不然就跟着迪杰斯特拉或者弗洛伊德算法走一遍
不存在拓扑排序 $\iff$ 图中存在顶点数大于 1 的回路/环，该回路构成一个强连通分量
即，无环一定有拓扑
邻接矩阵为三角矩阵（且对角元全为零）$\rightarrow$ 无环
图的邻接矩阵为三角矩阵且对角元全为零 $\rightarrow$ 拓扑排序存在
图的邻接矩阵为三角矩阵且对角元全为零，并且对角线以上/以下全为 1（不为 0）$\rightarrow$ 拓扑序列存在且唯一
具有有序的拓扑排序序列 $\rightarrow$ 图的邻接矩阵为三角矩阵且对角元全为零
对有向图中的顶点进行适当的编号，使其邻接矩阵为三角矩阵且主对角元全为零的充分必要条件是，该有向图可以进行拓扑排序
拓扑序列唯一，不能唯一确定该图
拓扑序列唯一，也不能说明图中每个顶点的入度和出度最多为 1
比如下面三个 DAG，它们的拓扑排序唯一且都是 ABCD
事件的最早发生时间与以该事件为始的弧的活动（若有）的最早开始时间相同
事件的最迟发生时间是以该事件为尾的活动（若有）的最迟开始时间与该活动的持续时间之和
破圈法求解最小生成树
任取一圈，去掉圈上权值最大的边。反复执行这一步骤，直到没有圈为止
求有向图的强连通分量的数目
每个顶点自身都是一个强连通分量
所以含有 $n$ 个顶点的有向图至少有 $n$ 个强连通分量
当某个顶点只有出弧而没有入弧时，其他顶点无法到达这个顶点，不可能与其他顶点和边构成强连通分量
所以直接删除该顶点及所有与之为尾的弧（即该顶点的所有出弧）
关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少
缩短所有关键路径上共有的任意一个关键活动的持续时间可缩短关键路径长度
所有顶点事件都是关键事件并不能说明关键路径唯一
如下图，所有事件都是关键事件，且除了 a 之外都是关键活动
