数据结构复习-第四部分

本系列文章为作者复习数据结构过程中的知识点总结、速通，欢迎补充

Written by SJTU-XHW

Reference: 张同珍老师 PPT | UNIkeEN

Chapter 8 外部查找和排序

8.1 零碎概念集合

内存与外存的特性：外存读取访问速率 << 内存访问速率；

尽可能避免访问，宁可增加计算量……
记录：外存上的一个数据元素通常被称为一条记录；
磁道：磁盘表面储存信息的同心圆轨道；
扇区：磁盘的磁道被分为若干段，每段被称为一个扇区；

一个扇区相当于磁带上的一个数据块，也称磁盘块，是一次磁盘读写的单位；

8.2 B 树

定义：存储在外存上的动态查找表：

一棵 m 阶 B 树或者为空，或者满足：
1. 根结点的度 $d_r\in\{0\}\space\bigcup\space[2,\space m]$；
2. 除了根结点和叶结点外，每个结点的度 $d\in[\space\lceil\dfrac{m}{2}\rceil,\space m\space]$；
3. 度为s（s＞0）的结点具有 n = s-1 个关键字，信息存放方式：
  - 已排序：$K_1\le K_2\le …\le K_n$
  - $n$：关键字数；
  - $A_i$：指向满足关键字 $K_i\lt K\lt K_{i+1}$ 的后继结点的地址（是磁盘地址编号，可以类比为为内存中的指针）；
  - $(K_i, R_i)$：键值对，{关键字K、目标文件块的地址R}；
4. 所有叶结点在同一层，且深度相同、不存在信息（也称“失败结点”）；
加速原理：已知访问次数 $\varpropto$ 查找树高度；
运算实现
- 查找：类似二叉查找树，只不过多了“在结点中查找区间的步骤”
- 插入
  
  step 1. 先查找，再插入：注意结点内关键字的有序性
  
  可能违反B树定义1+2：结点的度可能会超过阶数m，因此进入第二步；
  
  step 2. 判断当前插入位的关键字数n（在插入前的）
  - $n\le m-1$，则不影响，插入结束；
  - $n=m$，必须分裂结点，进入第三步；
  step 3. 分裂结点
  
  不能违反定义1：根结点的度 ≥ 2，和定义2：非根非叶结点度 $\ge\lceil\dfrac{m}{2}\rceil$；
  
  假设原结点插入后：
  
  则对半分割结点：
  
  再将中间的结点：$(K_{\lceil\cfrac{m}{2}\rceil},\space R_{\lceil\cfrac{m}{2}\rceil})$ 提到父结点上用以分开两个分裂结点；
  
  step 4. 提升到父结点后，对父结点递归第二步，检查是否违反定义，并及时修正
- 删除
  
  step 1. 先查找关键字 $K_i$ 的位置，判断是否在底层（下一层为失败结点）
  
  如果是，跳过第二步；
  
  step 2. 找“替身”，使用右子树最左关键字（或左子树最右关键字，都位于底层）取代，然后转化为删除底层关键字
  
  step 3. 删除底层结点（注意不是失败结点）
  
  不能违反定义1、2：根节点度……非根非叶结点度……；
  - 删除后，关键字个数 $n\in[\space\lceil\dfrac{m}{2}\rceil-1\space,m-1\space]$，符号定义，删除结束；
  - 删除后，关键字个数 $n=\lceil\dfrac{m}{2}\rceil-2$，则需要向左 / 右兄弟节点借关键字；
    
    借的步骤（以左兄弟为例，如果左兄弟恰好$\lceil\dfrac{m}{2}\rceil-1$没法借，借右兄弟）：
    
    将左兄弟的最大关键字上移至父结点，再将父结点中大于该关键字的最小关键字（连同左兄弟最右边的指针）下移给被删关键字所在结点的最左边。完成。
  - 删除后，左、右兄弟结点都是 $n^\prime=\lceil\dfrac{m}{2}\rceil-1$，没法借，那么需要合并结点；
    
    合并步骤（以合并左兄弟为例，右兄弟同理）：
    
    将该结点与左兄弟合并，同时下移父结点位于这两个结点间的关键字；
    
    同时，这种情况必须递归检查父结点，如果父结点也因为减少一个关键字而不符定义，则也“先借，不行再合并”
- 运算实现的形象记忆：膨胀直到分裂；太瘦吸收两侧结点；都瘦合并结点

常见疑问：B树的阶数怎么确定？B树的结点怎么组织？算法设计中怎么快速找父结点？

Answer：
- 针对第一个问题，应该在实际应用中根据磁盘块大小、关键字长度、磁盘块地址长度共同确定B树的阶数；B树阶数的计算思路和B+树类似，可以参考后面B+树的阶数计算🔗；
- 针对第二个问题，和之前的数据结构不一样，B树存在外存上而非内存上，所以我们要定义先确定B树的阶数【没错，每棵B树的阶数在生命周期中是定值，不能变化】，然后事先在磁盘块的对应位置分配好各个结点、各个字段的空间位置，这样一棵B树就固定下来了！以后每访问B树的一个结点（在一个磁盘块大小中），就由 $A_i$ 的指引，在规定的空间完成就行；
- 针对第三个问题，在理解第二个问题后会发现，B树（包括B+树）的父结点的位置可以结合结点在磁盘上的分布（具体设计具体分析）计算出来（或者记录下来，因为存在外存的数据一定很大，一个地址的大小可以忽略不计），不用特意寻找浪费时间；

8.3 B+ 树

出现原因：B树支持快速查找某个记录，但如果要按关键字大小顺序访问文件的所有记录，那么时间效率低下；需要一个新型索引结构，来完成对于索引顺序文件（支持随机访问、按关键字顺序访问的文件）的访问；

保证索引有序（像 B 树结点中关键字有序）

保证文件的记录有序

定义：M 阶 B+ 树是满足如下条件的 M 叉树：
- 根的度满足 $d_r\in\{0\}\space\bigcup\space[2,\space M]$；
- 除根以外的所有结点的度满足 $d\in[\space\lceil\dfrac{M}{2}\rceil,\space M\space]$；
- 度为 k 的结点保存 k - 1 个键来引导查找，第 i 个键代表第 i + 1 子树中的键的最小值
  
  这意味着 B+ 树和 B 树不同，B+树中非底层（叶结点的上一层）结点存储的键都是出现在底层结点的！
- 叶结点包含数据块（为了访问结点的效率，一个数据块的大小应该设计为一个磁盘块的大小，使得机器在一次 I/O 读写就能完全将内容读进内存），其中存放若干记录（键-值对），同时叶结点按序连成单链表；
  
  这意味着 B+ 树的叶结点和非叶结点的类型不一样，即内含数据成员不一样；
- 叶结点中的每个数据块至少 $\lceil\dfrac{L}{2}\rceil$ 个记录，至多 L 个记录；

B树、B+树重难点题
- B+树阶数计算
  
  已知：一棵 B+ 树的一个非叶结点预分配：M-1个键、M个指针（记录磁盘地址）；叶结点预分配：L个记录、1个指针（构成单链表，但相对于L个记录可忽略不计）；
  
  假设：一个磁盘块 W Bytes、一个记录 R Bytes、一个关键字 K Bytes、一个磁盘地址大小 A Bytes，则：
  $\begin{equation}\left\{ \begin{aligned}&K\cdot(M-1)+A\cdot M\le W\\ &L\cdot R\le W\quad(A\ll L\cdot R)\\ \end{aligned} \right.\end{equation} \qquad (一般都取等、取整作最优情况)$
- 插入/删除某个元素后，B/B+树的结构变成什么样子；
- 含有 n（n＞0）个非叶结点的 m 阶 B 树至少包含多少个关键字、至多包含多少个关键字？；
  
  分析：
  
  最少关键字时，每个结点都取最少的度；根结点最小度为2（n＞0 保证根结点不是叶结点）、其他非叶结点最小度为 $\lceil \dfrac{m}{2}\rceil$，所以最小关键字为：$(n-1)(\lceil \dfrac{m}{2}\rceil-1)+1$ ；
  
  最多关键字时，每个结点取最多的度，所有非叶结点的最大度都是 m，所以最多关键字是 $n(m - 1)$；
- 一棵 m 阶 B 树有 N 个关键字，则这棵 B 树的最大高度、最小高度（高度含叶结点）分别是？
  
  分析：
  
  最大高度在所有非叶结点都取最小度时取得（根度为2，非根非叶度为 m/2 向上取整），不妨假设此时高度为 h，非叶结点所占高度为 h - 1；由于 B 树的叶结点在同一层，各个结点非常整齐，那么反推总非叶结点数（包括根结点）：
  $\begin{aligned} n_{NL}&=1+2+2\cdot\lceil \dfrac{m}{2}\rceil+\cdots+2\cdot(\lceil\dfrac{m}{2}\rceil)^{h-3}\\ &=1+2\cdot\dfrac{(\lceil\cfrac{m}{2}\rceil)^{h-2}-1}{\lceil\cfrac{m}{2}\rceil-1} \end{aligned}$
  结合”非根非叶度为 m/2 向上取整”的结论，所有非叶结点的关键字数（包括根结点）：
  $\begin{aligned} N&=(n_{NL}-1)\cdot(\lceil \dfrac{m}{2}\rceil-1)+1\\ &=2(\lceil \dfrac{m}{2}\rceil)^{h-2}-1 \end{aligned}$
  所以：$h\le2+log_{\lceil\cfrac{m}{2}\rceil}(\dfrac{N+1}{2})$；
  
  最小高度同理:
  $\begin{aligned} n_{NL}&=1+\sum\limits_{k=1}^{h-2}{m^k}=1+\dfrac{m(m^{h-2}-1)}{m-1}\\ N&=(n_{NL}-1)\cdot(m-1)+m-1=m^{h-1}-1 \end{aligned}$
  所以：$h\ge 1+log_m(N+1)$；
  
  综上，得到 B 树的高度结论（其中高度 h 包含叶结点）：
  
  含 N 个关键字的 m 阶 B 树的高度 $h\in[1+log_m(N+1),\space 2+log_{\lceil\cfrac{m}{2}\rceil}(\dfrac{N+1}{2})],\space h\in \mathbf{N^*}$
- 什么？你问 B+ 树的关键字、高度的计算呢？B+ 树的关键字都在叶结点里，非叶结点中的只是对叶结点的重复、索引，讨论的意义不大；算 B+ 树的阶数才是重点；

运算实现
- 查找：略
- 插入
  
  和 B 树类似，但需要注意的是，B+ 树和 B 树不同，在非叶结点中的键一定存在记录中，并且表示第 i + 1棵子树的最小值，所以在分裂结点时，没有上移的说法；
- 删除：和 B 树对应的解决方案，先领养，不行再合并

8.4 外排序

一般都使用归并排序，这在外排序中极其优秀；

⚠易错警示：如果题目说：”多阶段归并是为了最大限定地提高归并的路数“是正确的。不是说多阶段归并本身能提高归并路数，是因为多阶段归并能够提高”路“的利用率（对k路，总路数2k降为k+1），这样在同样大小的内存中，可以选取更大的k值。所以多阶段归并的目的也可以说成（在一定的资源条件下）为了最大限度地提高归并的路数；

█◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤图部分将结合离散数学-图论知识共同复习◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢◤◢█

Chapter 9 图

9.1 图论中的重要定义Ⅰ

图的起源：人们关心一类问题，给定的两点间是否有一条或多条连线的关系，而连接方式无关紧要。这类问题在数学上的抽象是图；

图的数学定义：一个图指有序三元组$(V(G),E(G),\psi_G)$，$V(G)$为非空（空图特殊，不参与讨论）顶点集，$E(G)$是不与$V(G)$相交的边集，$\psi_G$为关联函数；

约定：对于图 G，一般用符号 $V(G)$ 表示顶点集、$E(G)$ 表示边集、$\nu(G)$ 表示顶点数，$\varepsilon(G)$ 表示边数；若上下文仅有一个图，则省略 “(G)”；

注：无向图可以表示为二元组，即 V 和 E；
顶点对的定义：$\psi_G$ 使 G 的每条边对应于 G 的无序的顶点对；
连接、端点的定义：若 e 为 G 的一条边，u、v 是使 $\psi_G(e)=(u,v)$ 的顶点，则称：e 连接 u、v，顶点 u、v 称为 e 的端点；
关联、相邻、自环：一条边的端点与这条边关联；与同一条边关联的两个顶点称为相邻；端点重合为一点的边称为自环；
平面图、非平面图：边仅在端点相交的图称为平面图，反之为非平面图；
平凡图、非平凡图：仅有一个顶点的图称为平凡图；
有向边、无向边：可由端点 $v_i\space和\space v_j$ 表示 $e_k=(v_i,v_j)$ 的边称为无向边（vi、vj互为直接前驱、直接后继）；可由有序二元组 $e_k=\lt v_i,v_j\gt$ 表示的边是有向边（vi是vj的直接前驱、vj是vi的直接后继）；
有向图、无向图：所有边都是有向边的图是有向图，反之是无向图，否则是混合图；

可以将无向边视作双向有向边，因此此后不讨论混合图；
简单图、有向简单图：既没有自环，又没有重边的图，如果是无向图，称为简单图；如果是有向图，称为有向简单图；
1. 重边的定义：有两条及以上条边连接同一对顶点，称这个边为重边；
  
  ⚠易错警示：对有向边，A—->B 和 B—->A 组合不算重边！A—->B 和 A—->B 组合才是；
2. 如果不强调“有向”，一般情况下“图”指“无向图”；不过在定义中，如果发现只描述无向图的，大概率对有向图也适用，不然就单独拎出来了；
完全图、有向完全图：每对不同顶点都有一条边相连的简单图称为完全图；有向完全图同理；

特别地，将 n 个结点的完全图记作 $K_n$，但有向完全图没有这种记法；

定理1：$\varepsilon(K_n)=C^2_{n}$ 且对n 个结点的有向完全图G：$\varepsilon(G)=A^2_{n}$；

（因为A—->B 和 B—->A 组合不算重边）
偶图（或者称二部图）：一个图 G 的顶点集 $V(G)$ 可以分解为两个子集 X、Y，使得：每条边都有一个顶点在 X 中，另一个顶点在 Y 中；这样的一种分类 (X, Y) 称为 G 的一个二分类；

理解：按分解的两个点集“切一刀”，所有边都被砍断的图；
子图：若 $V(H)\subseteq V(G),\space E(H)\subseteq E(G)$，$\psi_H$ 为 $\psi_G$ 在 $E(H)$ 上的限制，则 $H$ 为 $G$ 的子图，记作：$H\subseteq G$；（真子图略）
母图：若 $H\subseteq G$，称 $G$ 为 $H$ 的母图；
生成子图（或称支撑子图，spanning sub-graph）：$H\subseteq G\space且\space V(H)=V(G)$，称 $H$ 为 $G$ 的生成子图；
导出子图：有点抽象，一般用不到定义，想要形象地了解见：图的运算🔗；
基础简单图：一个图 G 删去所有“多余”的边，使图中恰没有重边、自环，得到的这样的简单生成子图称为基础简单图；
赋权图（或称加权图）：若给图 G 的每条边都赋以实数 $w_k$ 作为该边的权，称 G 为赋权图；
顶点的度：图 G 的顶点 v 的度记为 $d_G(v)$，指 G 中与 v 相关联的数目；
- 约定：$\delta(G)、\Delta(G)$ 表示 G 的所有顶点的最小度、最大度；
- 度为0的点称为孤立点；
- 对于有向图，$d(v)=d_+(v)+d_-(v)$，$d_+$ 为正度/入度，$d_-$ 为负度/出度；
- 自环贡献一个入度、一个出度；
定理2：（握手定理）$\sum\limits_{v\in V}d(v)=2\varepsilon$（所有结点的度之和为边数的2倍，有向图也是）；

推论：对任何图，度为奇数的点（称奇点）的个数为偶数；

定理3：有向图中，$\sum{d_-}=\sum{d_+}=\varepsilon$（入度和=出度和=边数，是入度出度平分的意思）

定理4：非空简单图（$\varepsilon\gt1$）一定存在度相同的结点；

9.2 图的同构

注：图同构问题分为4类：精确图完全同构、精确子图同构、不精确图完全同构、不精确子图同构；现在学界已证明后三者是 NP 完全问题；计算机离散数学-图论、数据结构（包括下面的内容）讨论的是第一种问题；

恒等图的定义
同构图的定义：如果存在两个一一映射（双射）$\theta:\space V(G)\rightarrow V(H),\space\phi:\space E(G)\rightarrow E(H)$，使 $\psi_G(e)=(u,v)$ 当且仅当 $\psi_H(\phi(e))=\theta(u)\theta(v)$，则将这样的映射对 $(\theta,\phi)$ 称为 G 和 H 间的一个同构；将 G 与 H 同构关系记为 $G\cong H$；

理解：边边和点点必须一一相应；

就是在不添加边和点、不删除边和点的基础上任意移动顶点的相对位置、为顶点和边改名，所产生的不同形态的图；
关于同构的定理

定理5：（同构的必要条件）两个同构图的结点度的非增序列相同

定理6：（同构的必要条件）若 G1 与 G2 同构，则 G1 的任意导出子图都有 G2 的导出子图与其同构；

其实还有一个必要条件过于明显，不作为定理：两同构图的顶点数、边数相等；
判断方法
- 判断两图同构：按定义，找到两个一一映射；
  
  注：根据定义，可以得出一个显然的方法：一个图的邻接矩阵经历有限次的行互换、列互换，能变成另一个图的邻接矩阵，那么这两个图同构；
- 判断两图不同构：使用定理5、6（必要条件），不满足必要条件的就不是；

9.3 图的存储实现

图的关联矩阵（行是顶点，列是边）：因为空间原因，不做存储图的方法；

虽然不做存储方法，但在讨论树、有向连通图、电路图的某些性质时比较有用，感兴趣戳这里🔗（不在初级数据结构要求范围内）；
- 无向图的关联矩阵：可以由 bool 矩阵表示，1是有关联，0是没有关联；
- 有向图的关联矩阵：+1表示该边离开该结点，即正度/出度；-1表示该边进入该结点，即负度/入度；0表示没有关联；

图的邻接矩阵表示法：对任意的图 G，对应一个 $\nu\times\nu$ 的邻接矩阵 $A(G)=[a_{ij}]$，其中 $a_{ij}$ 为 $v_i、v_j$ 的连接数目；（空间：$O(|V|^2)$）

进一步，在数据结构中更常用的是“加权图的邻接矩阵”存储方法，可以兼顾非加权图：

$A[i][j]=\begin{equation}\left\{\begin{aligned}&\omega,&<i,j,w>\in E\\ &0,&i=j\\ &\infty,&otherwise\\ \end{aligned}\right.\end{equation}$

template <class VType, class EType>
class adjMatrixGraph {
private:
    VType* vertices;    // store the data of each vertex.
    EType** edges;      // store the data of each edge (in adjacent matrix form).
    EType noEdgeFlag;    // represent the no-edge area.
    int vertixNum;
    int edgeNum;
    int vertexIdx(const VType& v) const {
        for (int i = 0; i < vertixNum; ++i)
            if (vertices[i] == v) return i;
        throw vertexNotExists();
    }
    void dfs(int start, bool visited[]) const;
public:
    adjMatrixGraph(int vSize, const VType vers[], const EType& noEdge);
    adjMatrixGraph(const adjMatrixGraph<VType, EType>& cp) = delete;
    ~adjMatrixGraph();
    bool exist(const VType& v1, const VType& v2) const;
    void insert(const VType& v1, const VType& v2, const EType& w);
    void remove(const VType& v1, const VType& v2);

    void printAdjMatrix() const;
    void dfs() const;
    void dfs_nonRecur() const;
    void bfs() const;
};

图的邻接表表示法：改进了邻接矩阵表示法在面对稀疏矩阵时浪费空间、不易维护的问题；

结点集(结点数组)：node1 {结点值，与该结点相邻的直接后继(有方向)结点索引链表头指针}
 |------------------------------------------------------------|
 v
边集(单链表)：node2 {结点索引（不能放结点值，因为无法完成后面的遍历运算, 下一node2}

+ 保存边数、保存结点数
空间：O(|V|+|E|)

template <class VType, class EType>
class adjListGraph: public graph<VType, EType> {
private:
    struct eNode {
        int end;
        EType weight;
        eNode* next;
        eNode(): end(0), next(0) {}
        eNode(const EType& w, int e=0, eNode* nxt=0)
            : weight(w), end(e), next(nxt) {}
    };
    struct vNode {
        VType data;
        eNode* edge;
    };

    struct EulerNode {
        int nodeIdx;
        EulerNode* next;
        EulerNode(int idx=0, EulerNode* n=0)
            : nodeIdx(idx), next(n) {}
    };

    vNode* vertices;
    bool directed;
    int vertixNum;
    int edgeNum;

    int vertexIdx(const VType& v) const {
        for (int i = 0; i < vertixNum; ++i)
            if (vertices[i].data == v) return i;
        throw vertexNotExists();
    }
    typename adjListGraph<VType, EType>::vNode* cloneBase() const;
    void dfs(int start, bool visited[]) const;

    void _insert(int v1, int v2, const EType& w);
    void _remove(int v1, int v2);
    int _getInDegree(int v) const;
    int _getOutDegree(int v) const;
    int _getDegree(int v) const;
    void _EulerCircuit(int start, EulerNode*& begin, EulerNode*& end);
    int* topoSortIdx() const;
    int criticalPath(int* early, int* late) const;
    void printPath(int start, int end, int prev[]) const;
public:
    adjListGraph(int vSize, const VType vers[], bool direct=1);
    adjListGraph(const adjListGraph<VType, EType>& cp);
    adjListGraph(adjListGraph<VType, EType>&& tmp);
    ~adjListGraph();
    bool exist(const VType& v1, const VType& v2) const;
    void insert(const VType& v1, const VType& v2, const EType& w);
    void remove(const VType& v1, const VType& v2);

    int getDegree(const VType& v) const;
    int getInDegree(const VType& v) const;
    int getOutDegree(const VType& v) const;
    
    void printAdjList() const;
    void dfs() const;
    void dfs_nonRecur() const;
    void bfs() const;
    void print_dfs_tree(const VType& emptyFlag) const;
    void print_bfs_tree(const VType& emptyFlag) const;

    bool EulerCircuit(const VType& start);
    void topoSort() const;
    void criticalPath() const;
    // The shortest path for the graph: O(n^3)
    VType* dijkstra(const VType& start, const EType& noEdge, bool prompt=false) const;
    VType* SPFA(const VType& start, const EType& noEdge) const;
};

9.4 图的运算实现（except for traverse）

图的基本运算
- 差运算：（要求 $G_2$ 为 $G_1$ 子图）$G_1-G_2=(V_1,E_1-E_2)$；
- 补运算：$n$ 个结点的简单图的补图 $\overline{G}=K_n-G$；
- 删去结点 $v$ 及其关联的边：$G-v$
  
  $G-v$ 为 $G$ 的导出子图：有助于理解导出子图的意义；
- 删去边 $e$：$G-e$
  
  $G-e$ 为 $G$ 的生成子图：有助于理解生成子图的意义；
- 增加边 $e_{ij}=(v_i,v_j)$：$G+e_{ij}$
数据结构中图的基本运算：创建、判边、增删边、查点边数、遍历（后面分开讨论）；

图的运算实现：对于不同的存储方式，图的运算时间复杂度有所不同

邻接矩阵表示的运算实现

template <class VType, class EType>
adjMatrixGraph<VType, EType>::adjMatrixGraph(
    int vSize, const VType vers[], const EType& noEdge) {
    this->vertixNum = vSize; this->edgeNum = 0; noEdgeFlag = noEdge;
    vertices = new VType[vSize];
    edges = new EType*[vSize];
    for (int i = 0; i < vSize; ++i) {
        vertices[i] = vers[i];
        edges[i] = new EType[vSize];
        for (int j = 0; j < vSize; ++j)
            edges[i][j] = noEdge;
        edges[i][i] = 0;
    }
}

template <class VType, class EType>
adjMatrixGraph<VType, EType>::~adjMatrixGraph() {
    delete[] vertices;
    for (int i = 0; i < this->vertixNum; ++i)
        delete[] edges[i];
    delete[] edges;
}

template <class VType, class EType>
bool adjMatrixGraph<VType, EType>::exist(const VType& v1, const VType& v2) const {
    int u = vertexIdx(v1), v = vertexIdx(v2);
    return edges[u][v] != noEdgeFlag;
}

template <class VType, class EType>
void adjMatrixGraph<VType, EType>::insert(const VType& v1, const VType& v2, const EType& w) {
    int u = vertexIdx(v1), v = vertexIdx(v2);
    if (edges[u][v] == noEdgeFlag) ++this->edgeNum;
    edges[u][v] = w;
}

template <class VType, class EType>
void adjMatrixGraph<VType, EType>::undirected_insert(const VType& v1, const VType& v2, const EType& w) {
    int u = vertexIdx(v1), v = vertexIdx(v2);
    if (edges[u][v] == noEdgeFlag) ++this->edgeNum;
    if (edges[v][u] == noEdgeFlag) ++this->edgeNum;
    edges[u][v] = edges[v][u] = w;
}

template <class VType, class EType>
void adjMatrixGraph<VType, EType>::remove(const VType& v1, const VType& v2) {
    int u = vertexIdx(v1), v = vertexIdx(v2);
    if (edges[u][v] != noEdgeFlag) --this->edgeNum;
    edges[u][v] = noEdgeFlag;
}

template <class VType, class EType>
void adjMatrixGraph<VType, EType>::printAdjMatrix() const {
    for (int i = 0; i < this->vertixNum; ++i) {
        for (int j = 0; j < this->vertixNum; ++j)
            std::cout << edges[i][j] << ' ';
        std::cout << '\n';
    }
}

邻接表表示的运算实现

template <class VType, class EType>
adjListGraph<VType, EType>::adjListGraph(int vSize, const VType vers[], bool direct) {
    this->vertixNum = vSize; directed = direct;
    this->edgeNum = 0; vertices = new vNode[vSize];
    for (int i = 0; i < vSize; ++i) {
        vertices[i].data = vers[i];
        vertices[i].edge = nullptr;
    }
}

template <class VType, class EType>
adjListGraph<VType, EType>::~adjListGraph() {
    eNode* curEdge;
    for (int i = 0; i < this->vertixNum; ++i) {
        while (curEdge = vertices[i].edge) {
            vertices[i].edge = curEdge->next;
            delete curEdge;
        }
    }
    if (vertices) delete[] vertices;
}

template <class VType, class EType>
typename adjListGraph<VType, EType>::vNode* adjListGraph<VType, EType>::cloneBase() const {
    vNode* newVers = new vNode[this->vertixNum];
    for (int i = 0; i < this->vertixNum; ++i) {
        newVers[i].data = vertices[i].data;
        newVers[i].edge = nullptr;
        eNode** curEdgeDst = &(newVers[i].edge);
        eNode* curEdgeSrc = vertices[i].edge;
        while (curEdgeSrc) {
            *curEdgeDst = new eNode(curEdgeSrc->weight, curEdgeSrc->end, 0);
            curEdgeDst = &((*curEdgeDst)->next);
            curEdgeSrc = curEdgeSrc->next;
        }
    }
    return newVers;
}

template <class VType, class EType>
adjListGraph<VType, EType>::adjListGraph(const adjListGraph<VType, EType>& cp) {
    vertices = cp.cloneBase(); this->edgeNum = cp.edgeNum;
    this->vertixNum = cp.vertixNum; directed = cp.directed;
}

template <class VType, class EType>
adjListGraph<VType, EType>::adjListGraph(adjListGraph<VType, EType>&& tmp) {
    this->edgeNum = tmp.edgeNum; this->vertixNum = tmp.vertixNum; directed = tmp.directed;
    tmp.edgeNum = tmp.vertixNum = 0; vertices = tmp.vertices; tmp.vertices = nullptr;
}

template <class VType, class EType>
bool adjListGraph<VType, EType>::exist(const VType& v1, const VType& v2) const {
    int u = vertexIdx(v1), v = vertexIdx(v2);
    const eNode* cur = vertices[u].edge;
    while (cur) {
        if (cur->end == v) return true;
        cur = cur->next;
    }
    return false;
}

template <class VType, class EType>
void adjListGraph<VType, EType>::_insert(int v1, int v2, const EType& w) {
    eNode** cur = &(vertices[v1].edge);
    while (*cur && (*cur)->end != v2) cur = &((*cur)->next);
    if (!(*cur)) { ++this->edgeNum; *cur = new eNode(w, v2); }
}

template <class VType, class EType>
void adjListGraph<VType, EType>::_remove(int v1, int v2) {
    eNode** cur = &(vertices[v1].edge);
    while (*cur && (*cur)->end != v2) cur = &((*cur)->next);
    if (*cur) {
        eNode* tmp = *cur; *cur = (*cur)->next;
        delete tmp; --this->edgeNum;
    }
}

template <class VType, class EType>
void adjListGraph<VType, EType>::insert(const VType& v1, const VType& v2, const EType& w) {
    int u = vertexIdx(v1), v = vertexIdx(v2);
    _insert(u, v, w);
    if (!directed) _insert(v, u, w);
}

template <class VType, class EType>
void adjListGraph<VType, EType>::remove(const VType& v1, const VType& v2) {
    int u = vertexIdx(v1), v = vertexIdx(v2);
    _remove(u, v);
    if (!directed) _remove(v, u);
}

template <class VType, class EType>
int adjListGraph<VType, EType>::_getInDegree(int v) const {
    int ans = 0;
    for (int i = 0; i < this->vertixNum; ++i) {
        if (i == v) continue;
        eNode* curEdge = vertices[i].edge;
        while (curEdge) {
            if (curEdge->end == v) ++ans;
            curEdge = curEdge->next;
        }
    }
    return ans;
}

template <class VType, class EType>
int adjListGraph<VType, EType>::_getOutDegree(int v) const {
    int ans = 0;
    eNode* target = vertices[v].edge;
    while (target) { ++ans; target = target->next; }
    return ans;
}

template <class VType, class EType>
int adjListGraph<VType, EType>::_getDegree(int v) const {
    if (directed) return _getInDegree(v) + _getOutDegree(v);
    else return _getOutDegree(v);
}

template <class VType, class EType>
int adjListGraph<VType, EType>::getDegree(const VType& v) const {
    return _getDegree(vertexIdx(v));
}

template <class VType, class EType>
int adjListGraph<VType, EType>::getInDegree(const VType& v) const {
    return _getInDegree(vertexIdx(v));
}

template <class VType, class EType>
int adjListGraph<VType, EType>::getOutDegree(const VType& v) const {
    return _getOutDegree(vertexIdx(v));
}

template <class VType, class EType>
void adjListGraph<VType, EType>::printAdjList() const {
    for (int i = 0; i < this->vertixNum; ++i) {
        std::cout << "(" << i << ") " << vertices[i].data << ' ';
        const eNode* cur = vertices[i].edge;
        while (cur) {
            std::cout << "|-w=" << cur->weight
                << "->(" << cur->end << ") ";
            cur = cur->next;
        }
        std::cout << '\n';
    }
}

9.5 图论中的重要定义Ⅱ

道路和回路：在无向图 $G=(V,E)$ 中，若边点交替序列 $P=(v_{i1},e_{i1},v_{i2},e_{i2},…,e_{iq-1},v_{iq})$ 满足：$v_{ik}、v_{ik+1}$ 为 $e_{ik}$ 的两个端点，则称 P 为 G 的一条道路；特别地，如果 $v_{i1}=v_{iq}$，那么称道路 P 为 G 的一条回路；
- 如果 P 序列中没有重复的边，则 P 称为简单道路（或称“迹”）、简单回路（或称“闭迹”）；
- 更特别地，如果 P 序列中结点也不重复（结点不重复是边不重复的充分不必要条件），则称 P 为 G 的初级道路、初级回路；
有向道路和有向回路：在有向图 $G=(V,E,\psi_G)$ 中，若边序列 $P=(e_{i1},e_{i2},…,e_{iq})$，其中 $e_{ik}=(v_l, v_j)$，则称 P 为 G 的有向道路；若 $e_{iq}$ 终点也是 $e_{i1}$ 的始点，则称 P 为 G 的有向回路；
- 同样有：简单有向道路、简单有向回路、初级有向道路、初级有向回路的概念；
⚠易错点：平凡图一定是道路，但一定不是回路！
连通性、强连通性、弱连通性、单向连通性
- 无向图考虑“连通”：两结点间至少存在一条道路，则这两个结点间连通；
- 有向图考虑：
  1. 两结点间存在一条从 $v_i$ 到 $v_j$ 的有向道路且存在另一条从 $v_j$ 到 $v_i$ 的有向道路，则称 $v_i$ 和 $v_j$ 强连通；
  2. 两结点间仅存在一条从 $v_i$ 到 $v_j$ 的有向道路或仅存在另一条从 $v_j$ 到 $v_i$ 的有向道路，则称称 $v_i$ 和 $v_j$ 单向连通；
  3. 两结点间 不考虑所有道路的方向（称为“有向图的底图”），若这两个结点连通，则称 $v_i$ 和 $v_j$ 弱连通；
连通图、连通分量（或称“连通支”）
- 无向图 G 中任意两结点间都是连通的，则 G 为连通图；
- G 的连通子图（子图且连通）H 不是 G 的任何其他连通子图的真子图，称 H 为 G 的一个极大连通子图，也称连通分量；
有些不严谨的题问有向图“是不是连通图”，就将它看成一个无向图（忽略方向）；
强连通图、强连通分量
- 有向图 G 中任意两结点间都是强连通的，则 G 为强连通图；
- G 的强连通子图 H 不是 G 的任何其他强连通子图的真子图，称 H 为 G 的一个极大的强连通子图，也称强连通分量；
⚠易错点1：平凡图也单独算一个连通分量 / 强连通分量！

⚠易错点2：因为无向边看作“双向边”，所以连通的无向图一定是强连通的；

推论：图 G 的每个连通分支都是其导出子图；

小结论：图 G 对应关联矩阵记为 $M(G)$，则 G 的连通分支数为 $r(M(G))-1$；
割边与非割边、割点与非割点：删去图中某个边 / 点，图的连通分支数（连通性）改变，则称该边 / 点为割边 / 割点；
欧拉道路、欧拉回路：无向连通图 G 中的一条经过所有边的简单道路/回路称 G 的欧拉道路/回路；
- 理解：不重复地遍历所有边，不管点的情况；
- 注意：有向图也能讨论欧拉回路的问题，不过要遵循有向的连通性；
定理1：（欧拉回路充要条件）无向连通图 G 存在欧拉回路 $\Longleftrightarrow$ G 的各结点度数均为偶数；

推论1-1：（欧拉道路充分条件）无向连通图 G 仅有2个奇点 $\Longrightarrow$ G 存在欧拉道路；

推论1-2：（有向欧拉回路充分条件）有向连通图 G 的各结点的正、负度数相等 $\Longrightarrow$ G 存在有向欧拉回路（侧面说明有向可能严格一些，不仅结点度全为偶数，而且要进出相等）；

定理2：连通图 G 有 k 个奇点（由部分Ⅰ的定理可知，k为偶数），则 E(G) 可以划分为 $\dfrac{k}{2}$ 条简单道路；
哈密顿道路、哈密顿回路：无向图 G 的一条经过全部结点的初级道路/回路称 G 的哈密顿道路/回路（简称H道路/H回路）；
- 理解：“不重复地遍历所有点”；
- 注意：H 道路 / 回路一般针对简单图，因为重边和自环对它没有什么影响，可以转换为简单图的问题；
很遗憾，目前 H 道路 / 回路的判定没有充要条件！一般遍历是 NP 问题……

定理3：（H 回路充分条件）完全图 $K_n$ 为 H 图；

定理4：（H 回路充分条件）若简单图 G 每个结点度都大于 n/2，则 G 为 H 图；

说明：平均每个点的度越大，越有可能有H道路、H回路；

推论4-1：（H 道路充分条件）若简单图 G 的任两结点 $v_i,v_j$ 恒有 $d(v_i)+d(v_j)\ge n-1$，则 G 存在 H 道路；

证明提示：有 H 道路一定连通，可以先证连通性；

推论4-2：（H 回路充分条件）若简单图 G 的任两结点 $v_i,v_j$ 恒有 $d(v_i)+d(v_j)\ge n$，则 G 为 H 图；

推论4-3：（H 回路的闭包等价关系）向图 G 中满足 “ $d(v_i)+d(v_j)\ge n$”的不相邻两结点 $v_i,v_j$ 加边，直至无法找到这样的结点对为止，形成的新图称为 G 的闭包（记为$C(G)$）；那么有：$G\space为H图\Longleftrightarrow C(G)为H图$；

推论4-4：（H回路闭包充分条件）若 $C(G)=K_n$，则 G 为 H 图；

定理5：（可怜为数不多的 H 回路的必要条件）若 G 为 H 图，则对任意非空顶点集 S，有：$\omega(G-S)\le|S|$；
- 补充：欧拉图、H 图的定义：有欧拉回路 / H 回路的图才叫~（只有欧拉道路 / H 道路的不是）；
- 判断一个图是 H 图：使用上面的充分条件/等价条件；
- 判断一个图不是 H 图：使用上面的必要条件；
  
  举例：证明 Peterson 图是极大非 H 图（有 H 道路，但没有 H 回路）
  
  【问题：它满足定理5，能否判断一下为什么在删去任意4个顶点时，连通分支数一定小于等于3？】
  
  定理6：（必要条件）若一个点在 H 回路中，那么必定有且仅有两个相连的相异道路；

9.6 图的简单应用

【普通图】有 3L、5L、8L的三个没有刻度的量杯，现在8L的量杯装满了水，其他两个是空的；问如何操作（不撒不漏）可以让8L水分为两个4L水？
【二部图】人、狼、羊、菜过河问题

解决思路：“状态转换图”：将每一个状态抽象为一个顶点，先列出所有可能状态作为顶点，再用“一次能直接转换的关系”作为边连接，最后只需判断在起点（初态）和终点（末态）是否单向连通即可；

9.7 图论中的重要定义Ⅲ

提示：本章节不在初级数据结构要求范围内；

割边与非割边、割点与非割点：删去图中某个边 / 点，图的连通分支数（连通性）改变，则称该边 / 点为割边 / 割点；

定理1：e 为割边，当且仅当 e 不属于 G 的任何回路；
普通树的数学定义：不含任何回路的连通图称为树；

定理2：“连通”、“无回路”、“有 n-1 条边”三个条件任取两个都可以作为树的定义；

推论：“连通+全为割边”、“任意两点间有唯一道路”、“无回路+加一边就一回路” 这三个与树的定义等价；

定理3：树中一定有树叶结点（离散数学中没有空树的说法！只有空图）
根树的定义：若树 T 是有向树，且 T 中存在某结点 $v_0$ 的入度为0、其他结点入度为1，则称 T 是以 $v_0$ 为根的根树（或外向树），用 $\overrightarrow{T}$ 表示；

根树才是数据结构中的“树”！
生成树（或称“支撑树”）：图 G 的一个符合树定义的生成子图称为图 G 的生成树；

余树：给定图 G 的一棵生成树 T，定义余树 $\overline{T}=G-T$；一般情况下，余树不是树；
基本关联矩阵：上接“关联矩阵存储🔗”，虽然关联矩阵一般不作为存储方法，但有些情况讨论它的性质，可以更方便地解决某些问题；

友情提醒1：这里和电路理论的电路图研究结合比较紧密；

友情提醒2：这里的讨论对象是有向连通图；
- 定义：在有向连通图 $G=(V, E)$ 的关联矩阵 $B$ 中，划去任意任意结点 $v_k$所对应的一行，得到 $(\nu-1)\times\varepsilon$ 的矩阵 $B_k$，称为 G 的一个基本关联矩阵；
- 相关定理
定理1：有向连通图 G 的关联矩阵 B 满足：$r(B)=\nu-1$；

定理2：有向连通图 G 的基本关联矩阵 $B_k$ 满足：$r(B_k)=\nu-1$；

推论：n个结点树 T 的基本关联矩阵的秩为 $\nu-1$；

定理3：有向连通图 G 如果存在回路 C，则 C 中各边所对应基本关联矩阵 $B_k$ 的各列线性相关；

定理4：有向连通图 G 的基本关联矩阵 $B_k$，有：$B_k任意n-1阶子式M_{n-1}\ne0\Longleftrightarrow M_{n-1}各列对应边构成G的一棵生成树$；

定理4说明了可以由 $B_k$ 的非零 n-1 阶子式的数目来代表 $G$ 生成树的数目🔗；
回路矩阵和割集矩阵；

不说了亲，这边建议您好好复习电路理论课呢:sweat_smile:
Huffman树（最优二叉树），详见“数据结构复习-第二部分”；

9.8 图的经典算法

9.8.1 图的遍历算法

DFS 算法：类似树的前序遍历

邻接表存储 $O(|V|+|E|)$

template <class VType, class EType>
void adjListGraph<VType, EType>::dfs(int start, bool visited[]) const {
    eNode* curEdge = vertices[start].edge;
    std::cout << vertices[start].data << ' ';
    visited[start] = 1;
    while (curEdge) {
        if (!visited[curEdge->end]) dfs(curEdge->end, visited);
        curEdge = curEdge->next;
    }
}

template <class VType, class EType>
void adjListGraph<VType, EType>::dfs() const {
    bool* visited = new bool[this->vertixNum] {0};
    for (int i = 0; i < this->vertixNum; ++i) {
        if (visited[i]) continue;
        dfs(i, visited);
        std::cout << '\n';
    }
}

template <class VType, class EType>
void adjListGraph<VType, EType>::dfs_nonRecur() const {
    seqStack<int> tasks;
    bool* visited = new bool[this->vertixNum] {0};
    for (int i = 0; i < this->vertixNum; ++i) {
        if (visited[i]) continue;
        tasks.push(i);
        while (!tasks.isempty()) {
            int tmp = tasks.pop();
            if (visited[tmp]) continue;     // Necessary when doing non-recursive op.
            std::cout << vertices[tmp].data << ' ';
            visited[tmp] = 1;
            eNode* curEdge = vertices[tmp].edge;
            while (curEdge) {
                if (!visited[curEdge->end])
                    tasks.push(curEdge->end);
                curEdge = curEdge->next;
            }
        }
        std::cout << '\n';
    }
    delete[] visited;
}

邻接矩阵存储 $O(|V|^2)$

template <class VType, class EType>
void adjMatrixGraph<VType, EType>::dfs(int start, bool visited[]) const {
    std::cout << vertices[start] << ' ';
    visited[start] = 1;
    for (int i = start + 1; i < this->vertixNum; ++i) {
        if (!visited[i] && edges[start][i] != noEdgeFlag)
            dfs(i, visited);
    }
}

template <class VType, class EType>
void adjMatrixGraph<VType, EType>::dfs() const {
    bool* visited = new bool[this->vertixNum] {0};
    for (int i = 0; i < this->vertixNum; ++i) {
        if (visited[i]) continue;
        dfs(i, visited);
        std::cout << '\n';
    }
    delete[] visited;
}

template <class VType, class EType>
void adjMatrixGraph<VType, EType>::dfs_nonRecur() const {
    seqStack<int> tasks;
    bool* visited = new bool[this->vertixNum] {0};
    for (int i = 0; i < this->vertixNum; ++i) {
        if (visited[i]) continue;
        tasks.push(i);
        while (!tasks.isempty()) {
            int tmp = tasks.pop();
            if (visited[tmp]) continue;
            std::cout << vertices[tmp] << ' ';
            visited[tmp] = 1;
            for (int j = tmp + 1; j < this->vertixNum; ++j) {
                if (!visited[j] && edges[tmp][j] != noEdgeFlag)
                    tasks.push(j);
            }
        }
        std::cout << '\n';
    }
    delete[] visited;
}

BFS 算法：类似树的层次遍历

邻接表存储 $O(|V|+|E|)$

template <class VType, class EType>
void adjListGraph<VType, EType>::bfs() const {
    seqQueue<int> taskQ;
    bool* visited = new bool[this->vertixNum] {0};
    for (int i = 0; i < this->vertixNum; ++i) {
        if (visited[i]) continue;
        taskQ.enQueue(i);
        while (!taskQ.isempty()) {
            int tmp = taskQ.deQueue();
            if (visited[tmp]) continue;     // necessary.
            std::cout << vertices[tmp].data << ' ';
            visited[tmp] = 1;
            eNode* curEdge = vertices[tmp].edge;
            while (curEdge) {
                if (!visited[curEdge->end])
                    taskQ.enQueue(curEdge->end);
                curEdge = curEdge->next;
            }
        }
    }
    delete[] visited;
}

邻接矩阵存储 $O(|V|^2)$

template <class VType, class EType>
void adjMatrixGraph<VType, EType>::bfs() const {
    seqQueue<int> taskQ;
    bool* visited = new bool[this->vertixNum] {0};
    for (int i = 0; i < this->vertixNum; ++i) {
        if (visited[i]) continue;
        taskQ.enQueue(i);
        while (!taskQ.isempty()) {
            int tmp = taskQ.deQueue();
            if (visited[tmp]) continue;     // necessary when doing no-recursive op.
            std::cout << vertices[tmp] << ' ';
            visited[tmp] = 1;
            for (int j = tmp + 1; j < this->vertixNum; ++j) {
                if (!visited[j] && edges[tmp][j] != noEdgeFlag)
                    taskQ.enQueue(j);
            }
        }
        std::cout << '\n';
    }

    delete[] visited;
}

9.8.2 两点间道路判定算法

这里介绍邻接矩阵表示的算法，比较常见；

引入：对于一个非加权图的邻接矩阵（0&1），有 $P=(p_{ij})_{n\times n}=\sum\limits_{k=1}^n{A^k}$，则 $p_{ij}$ 为从 $v_i$ 到 $v_j$ 的道路数；实际问题只关心是否有道路，所以可以改成逻辑运算提升速度：$P=(p_{ij})_{n\times n}=\bigvee\limits_{k=1}^n{A^k}$，时间复杂度 $O(\nu^4)$；

Warshell算法 $O(\nu^3)$

P <- A
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        for (int k = 1; k <= n; ++k)
            p_{jk} <- p_{jk} V (p_{ji} Λ p_{ik})

DFS 和 BFS $O(\varepsilon)$：和图的遍历不一样的是，它比图的遍历更简单，只需从一个点出发（减少最外层循环），用visited数组和BFS/DFS整体寻找，如果遇到终点即停止并返回true，否则返回false；

9.8.3 有向图强连通分支判断算法

思路：先从图 G 任一点开始 DFS，如果 G 不是强连通图，则可能得到一个深度优先生成森林；对森林中的每棵树按照生成次序依此进行后序遍历，并按遍历顺序给每个结点编号（从小到大）；

然后使 G 的每条边逆向，得到 Gr，再从 Gr 编号最大的结点开始 DFS，得到新的深度优先遍历森林中的每一棵树就是 G 的一个强连通分量；

9.8.4 欧拉回路的构造算法

欧拉回路有明确的、好判断的充要条件，所以算法设计相对容易；

无论啥算法，最好先利用充要条件排除没有欧拉回路的图，能大大提高时间性能；

下面讨论如果有欧拉回路，应该怎么找的算法：

拼接法：DFS寻找回路（经过即删除），如果回路结束却仍然有未遍历的结点，则从新的未访问的结点开始遍历回路，并拼接（“8”字原理），循环直到所有边已被访问；
Floyd算法（非割边优先遍历）

9.8.5 欧拉回路的应用：中国邮递员问题（CPP）

中国邮递员问题：走遍图中的所有边后返回返回起点，要求总路程最短；

对于无向图 G 的结论
- 如果 G 中所有结点个数都是偶数：该图的任一欧拉回路都是解；
- 如果 G 中有且仅有 2 个奇点 $v_i\space和\space v_j$：找到 G 从 $v_i$ 到 $v_j$ 欧拉道路 $E_{ij}$，再找从 $v_j$ 到 $v_i$ 的最短路径 $P_{ji}$，则回路 $E_{ij}+P_{ji}$ 就是问题的解；
- 如果 G 中有两个以上，共2k个奇点（由前面图的性质推论，奇点必有偶数个）：
  $图G有最佳邮路L\Longleftrightarrow\begin{equation}\left\{\begin{aligned}&1.\space L的任一边最多重复一次\\&2.\space对G中的任一回路C，L中在C上重复边的长度之和\\&\quad不超过C总长的一半\space(C必须包含所有重边)\\\end{aligned}\right.\end{equation}$
  实际做法是：找出所有奇点，两两配对并依此为奇点间添加重复边（长度和原边相等），为它们配对成偶点，得到新图，也即邮路 $L_x$；再检查 $L_x$ 是否满足以上两个条件；如果违反第一条则一次性删除两条多余重边，如果违反第二条则将 $L_x$ 的该段道路改成与 $C$ 互补的道路；

9.8.6 H 回路的应用：旅行商问题（TSP）

问题描述：给定一个正权完全图，求总权最小的 H 回路；

NP 完全问题，只能寻找近似解；这里不介绍算法，仅介绍问题；提示：不建议使用贪心法，误差很大；

9.8.7 有向无环图、AOV网与拓扑排序

有向无环图（DAG）：不存在回路的有向图称为有向无环图；
AOV网：有向无环图中的顶点表示活动，边表示活动间的先后关系，这样的图称为AOV网；
拓扑排序：将AOV网中的活动发生的先后次序排成一个序列（如果有一条从 u 到 v 的道路，那么 v 必须出现在 u 之后），称为拓扑排序，这个序列称为拓扑序列；

拓扑排序实现思路：类似于图的 BFS，但是只有一个结点的所有直接前驱结点都已访问后，才能访问这个结点；$O(|V|+|E|)$

计算每个结点的入度，保存在数组中；
检查入度数组中入度为零（无依赖）的对应结点索引，并将其入队；
当队伍非空时，循环出队并输出这个结点，在假设将这个结点删除，修正这个结点的所有直接结点的入度（减1），如此重复2、3步骤；

// 请自行实现私有函数 int _getInDegree(int) 获取入度；
// 使用到了之前的seqQueue类；
template <class VType, class EType>
int* adjListGraph<VType, EType>::topoSortIdx() const {
    int* ans = new int[this->vertixNum] {0}; int ansIdx = 0;
    int* inDegrees = new int[this->vertixNum] {0};
    seqQueue<int> preRequests;
    for (int i = 0; i < this->vertixNum; ++i) {
        inDegrees[i] = _getInDegree(i);
        if (!inDegrees[i]) preRequests.enQueue(i);
    }
    while (!preRequests.isempty()) {
        int cur = preRequests.deQueue();
        ans[ansIdx++] = cur;
        eNode* curEdge = vertices[cur].edge;
        while (curEdge) {
            if (--inDegrees[curEdge->end] == 0)
                preRequests.enQueue(curEdge->end);
            curEdge = curEdge->next;
        }
    }
    for (int i = 0; i < this->vertixNum; ++i)
        if (inDegrees[i]) {
            std::cout << "[ERROR] A non-DAG does not support topoSort().";
            delete[] ans; return 0;
        }
    return ans;
}

// Usage
template <class VType, class EType>
void adjListGraph<VType, EType>::topoSort() const {
    int* seq = topoSortIdx();
    if (!seq) return;
    for (int i = 0; i < this->vertixNum; ++i)
        std::cout << vertices[seq[i]].data << ' ';
    std::cout << '\n';
    delete[] seq;
}

9.8.8 AOE网与关键路径

AOE网络：活动定义在边上（持续时间），事件定义在顶点上；
AOE网络的重要两点：源点（入度为0，工程“起点”）、汇点（出度为0，工程“终点”）；
AOE网络解决的问题：完成整项任务的最少时间、哪些活动是影响工程进度的关键;
关键路径：从源点到汇点的最长路径称为关键路径；
关键活动：关键路径上的活动。推迟关键活动必定影响项目进度；
最早发生时间：用“从源点到该结点的最长路径”（因为和拓扑排序一样，只有该结点的所有直接前驱结点都访问过后，才能算访问了这个结点）表征；
最迟发生时间：用“关键路径长(定值) - 从汇点到该结点的最短路径”表征（因为是最迟，距离汇点最近才符合定义）；
时间余量：最迟发生时间 - 最早发生时间。时间余量为0的活动是关键活动（第二定义）；

找关键路径的思路：（用第二定义）就是找每个顶点的最早、最迟发生时间，进而得到关键活动、关键路径；

找出AOE网的任一拓扑序列；
从头至尾遍历一次拓扑序列，在遍历到 u 时，更新它的所有直接后继结点 v 的最早发生时间（如果当前ee值＜u 的值+路径长，那么更新v的ee值为更大的）；
再从尾至头遍历一次拓扑序列，在遍历到 u 时，更新它的所有直接后继结点 v 的最迟发生时间（如果后继结点le值＜v 的值+路径长，那么更新为u为更小的）；

别问为啥不和第二步相对应，找直接前驱结点，问就是找前驱结点复杂度太大了；

⚠记得更新最迟发生时间之前，要用第二步得到的关键路径长度（就是拓扑序列最后一个结点的ee值）填充最迟发生时间数组；
找出所有“最早发生时间=最迟发生时间”的结点，按照拓扑序列的顺序依此输出，即为关键路径；

template <class VType, class EType>
int adjListGraph<VType, EType>::criticalPath(int* early, int* late) const {
    int* topoSeq = topoSortIdx();
    for (int i = 0; i < this->vertixNum; ++i) early[i] = 0;
    for (int i = 0; i < this->vertixNum; ++i) {
        eNode* curEdge = vertices[topoSeq[i]].edge;
        while (curEdge) {
            if (early[topoSeq[i]] + curEdge->weight > early[curEdge->end])
                early[curEdge->end] = early[topoSeq[i]] + curEdge->weight;
            curEdge = curEdge->next;
        }
    }
    int pLen = early[topoSeq[this->vertixNum - 1]];
    for (int i = 0; i < this->vertixNum; ++i) late[i] = len;
    for (int i = this->vertixNum - 1; i >= 0; --i) {
        eNode* curEdge = vertices[topoSeq[i]].edge;
        while (curEdge) {
            if (late[topoSeq[i]] > late[curEdge->end] - curEdge->weight)
                late[topoSeq[i]] = late[curEdge->end] - curEdge->weight;
            curEdge = curEdge->next;
        }
    }
    return pLen;
}

// Usage
template <class VType, class EType>
void adjListGraph<VType, EType>::criticalPath() const {
    int* ee = new int[this->vertixNum];
    int* le = new int[this->vertixNum];
    int pathLen = criticalPath(ee, le);
    std::cout << "[INFO] The length of the critical path: " << pathLen << '\n';
    std::cout << "[INFO] The critical path: \n";
    for (int i = 0; i < this->vertixNum; ++i)
        if (ee[i] == le[i]) std::cout << vertices[i].data << " -> ";
    std::cout << "[Fin]\n";
}

9.8.9 生成树的计数算法

原理：Binet-Cauchy 定理：两个矩阵 $A_{m\times n},\space B_{n\times m}\space(m\le n)$，则 $det(AB)=\sum\limits_i{A_iB_i}$ 。其中$A_i$、$B_i$ 分别是从 $A$ 中任取 $m$ 列、$B$ 中任取 $m$ 行构成的行列式；

虽然这样计算行列式有些麻烦，但它揭示了乘积矩阵行列式和各矩阵的子式之间的关系；

定理1：（有向连通图的普通生成树计数）设 $B_k$ 为有向连通图 $G=(V,E)$ 的某一基本关联矩阵，则 $G$ 中不同树的数目为 $det(B_kB_k^T)$；

解题提示：如果要求不含某个边的生成树数目，只要求将该边删去后的生成子图对应生成树的数目；如果要求必含某个边的生成树数目，只要该边的起点终点合并为一点，求新图对应生成树的数目；

如果想求无向连通图的生成树个数，需要将其每条边指定一个任意方向转化为有向连通图；

推论证明：求证完全图 $K_n$ 的不同生成树的数目为 $n^{n-2}$；
$det(B_kB_k^T)=\begin{vmatrix}n-1&-1&\cdots&-1\\-1&n-1&\cdots&-1\\\vdots&\vdots&\ddots&\vdots\\-1&-1&\cdots&n-1\end{vmatrix}=n^{n-2}$

⚠易错警示：如果是求完全图 $K_n$ 不同构的生成树的数目，和“不同生成树”不一样！和化学上求同分异构体的做法类似；例如 $K_5$ 的不同构生成树数目为 3，对应有机化学戊烷的正戊烷、异戊烷、新戊烷的构型；

定理2：（有向连通图的根树生成树计数）设 $\overrightarrow{B_k}$ 表示将有向连通图 $G$ 的关于结点 k 的关联矩阵 $B_k$ 中所有的 1 元素换成 0 之后的矩阵，则 $G$ 中以 k 为根的不同根树数目为 $det(\overrightarrow{B_k}B_k^T)$；

解题提示：如果要求不含某个边的根树生成树数目，删去这个边再算；

⚠易错警示：和普通生成树不同，如果要求必含某个边的根树生成树数目，需要先计算以 v0 为根的总根树数目，再减去不含这个边的生成树数目；或者求 $G^\prime=G-\{(t,v)|t\ne u\}$ 的根树生成树数目；

9.8.10 生成树的生成算法

不作介绍，有兴趣请查阅相关资料，例如《图论与代数结构》清华大学出版社第3章 3.5节支撑树的生成；

9.8.11 最小生成树算法

Kruskal 算法

思路：不断向初始化为空的根结点中加入当前未加入过的最短边，如果构成回路，一定是回路中的最长边，删除它；如果不构成回路则继续，直至达到 n-1 条边为止，此时 T 一定不含任何回路、n-1条边、包含所有图的顶点、所有权最小，在贪心法上是最小生成树；

如何证明这个贪心算法的正确性？

可以证明定理：$T=(V,E’)$ 是赋权连通图 $G=(V,E)$ 的最短树，当且仅当对任意的余树边 $e\in E-E’$，回路 $C^e(C^e\subseteq E’+e)$ 满足：其边权 $w(e)\ge w(a),\space a\in C^e\space(a\ne e)$；

T <- Φ    // 树根结点初始化为空
while (|T| < n - 1 && E(G) != Φ) {
    e <- E中最短边
    E <- E - e
    if (T + e 无回路) T <- T + e
}
if (|T| < n - 1) 输出非连通的信息
else return T

时间复杂度：$O(\varepsilon+p\space log\space\varepsilon),\space其中p为迭代次数$；适用于稀疏图（当p不大时）；

Prim 算法

思路：在结点集中任选一个结点 v0 构成集合 V’，从 V 和 V-V’ 中各选一个顶点 u（来自V）、v（来自V-V’）使得 (u, v) 是满足条件的u、v中最短的边，将此边加入树 T，令 V’+=u，直至 V’=V；

感兴趣可以找一找定理的正确性证明；
1
2
3
4
5
6
7
t <- v0, T <- Φ, U <- {t}
while (U != V) {
w(t, u) = min{w(t, v)} where v in (V - U)
T <- T + e(t, u)
U <- U + u
for (v in V - U) w(t, v) <- min{w(t, v), w(u, v)}
}
时间复杂度：$O(\nu^2)$；适用于稠密图；