第7章 图

7.1 图的定义和术语

顶点（Vertex）
记 $V$ 是顶点的有穷非空集合
以 $<v,w>$ 表示从 $v$ 到 $w$ 的弧（Arc），其中 $v$ 称为弧尾（Tail）或初始点（Initial Node）， $w$ 称为弧头（Head）或终端点（Terminal Node）。记图中弧的集合为 $VR$ 。
与图中的边或弧相关的数称为权，带权的图称为网（Network）。
图的种类
- 若对于 $\forall<v,w>\in VR$ 均有 $<w,v>\in VR$ （即 $VR$ 是对称的），则称此图为无向图（Undigraph），否则称为有向图（Digraph）。
  对于无向图，可以以无序对 $(v,w)$ 代替 $<v,w>$ 和 $<w,v>$ ，表示 $v$ 和 $w$ 之间的一条边（Edge）。
- 有 $\frac{1}{2}n(n-1)$ 条边的无向图称为无向完全图（Completed graph），即任意两个结点之间均有边相连的无向无环图（顶点到其自身的弧或边称为环）。具有 $n(n-1)$ 条边的无向图称为有向完全图。
- 有很少条边或弧的图称为稀疏图（Sparse graph），反之称为稠密图（Dense graph）。
- 子图：通俗地说，从图中取出一部分顶点及有关的部分边。
顶点 $v$ 的度（Degree）是和 $v$ 相关联的边的数目，记为 $TD(v)$ ；以顶点 $v$ 为头的弧的数目称为 $v$ 的入度（InDegree），记为 $ID(v)$ ；以顶点 $v$ 为尾的弧的数目称为 $v$ 的出度（OutDegree），记为 $OD(v)$ 。对于顶点 $v$ 显然有 $TD(v) = ID(v) + OD(v)$ 。
路径和简单路径、回路和简单回路（环，Cycle）：（略）
和“连通”有关的概念
- 在图中如果从顶点 $v$ 到顶点 $w$ 有路径（若图为有向图，则路径也是有向的），则称顶点 $v$ 和顶点 $w$ 是连通的。
- 在无向图中如果对于任意两个顶点 $v,w\in V$ ， $v$ 和 $w$ 是连通的，则称此图为连通图（Connected Graph）。无向图中的极大连通子图称为连通分量（Connected Component）
- 在有向图中如果对于任意两个顶点 $v,w\in V$ ， $v \neq w$ ，从 $v$ 到 $w$ 和从 $w$ 到 $v$ 都存在路径，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。（所以“强连通图”和“强连通分量”是针对有向图而言的，无向图的定义比有向图严格）。
- 连通图的生成树：含有连通图中全部 $n$ 个结点，却只有足以构成一棵树的 $n-1$ 条边的一个极小连通子图。图中有且仅有 $n-1$ 条边是生成树的必要条件（但不是充分条件）。如果在生成树上添加一条边，则必定构成一个环，因为加入的这条边使得其依附的两个顶点之间有了第二条的路径。生成树一般不唯一。

7.2 图的存储结构

7.2.1 数组表示法

用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。以二位数组表示 $n$ 个顶点的图时，需要存储 $n$ 个顶点信息和 $n^2$ 个弧信息。

对于无权图
邻接矩阵中的每个元素 $w_{ij}$ 定义为 $w_{ij}=\left\{ \begin{aligned} 1,<v_i,v_j>\in VR\\ 0,<v_i,v_j>\notin VR \end{aligned} \right.$
则对于无向图，顶点 $v_i$ 的度是邻接矩阵中第 $i$ 行或第 $i$ 列的元素之和；对于有向图，顶点 $v_i$ 的出度是邻接矩阵中第 $i$ 行的元素之和，入度是邻接矩阵中第 $i$ 列的元素之和。
对于带权图（网）
邻接矩阵中的每个元素定义为 $\left\{ \begin{aligned} w_{ij},<v_i,v_j>\in VR\\ \infty,<v_i,v_j>\notin VR \end{aligned} \right.$

7.2.2 邻接表

邻接表（Adjacency List）是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第 $i$ 个单链表中的结点表示依附于顶点 $v_i$ 的边（对于有向图是以顶点 $v_i$ 为尾（初始点）的弧）。

每一个结点由三部分组成
1. adjacentVertex：该弧所邻接的另一点的位置
2. nextArc：指向表示下一条边或弧的结点
3. data/info：与当前边或弧相关的信息，如权值等。

为优化随机访问，表头结点通常以顺序结构的形式存储。在无向图的邻接表中，第 $i$ 个链表中的结点数即为顶点 $v_i$ 的度。而在有向图中，第 $i$ 个链表中的结点数只是顶点 $v_i$ 的出度。为求入度必须遍历整个邻接表，在所有链表中adjacentVertex的值为 $i$ 的个数即为 $v_i$ 的入度。

namespace graph
{
    //邻接表实现（存储结构）
    namespace adjacency_list_impl
    {
        //进行声明以在实现中使用
        struct ArcNode_s;
        struct VertexNode_s;

        typedef struct ArcNode_s
        {
            //指向邻接顶点，若为有向弧，adjacentVertex为该弧的终端点
            struct VertexNode_s *adjacentVertex;

            struct ArcNode_s *lastArc;//指向上一条弧
            struct ArcNode_s *nextArc;//指向下一条弧
            void *data;//与该弧有关的数据
        } ArcNode_t;
        typedef struct VertexNode_s
        {
            //依附于当前顶点（Vertex）的边（对于有向图是以当前顶点作为弧尾的弧）
            //作为结点构成了一个链表，firstArc指向该链表的第一个结点
            struct ArcNode_s *firstArc;
            void *data;
        } VertexNode_t;
        typedef struct
        {
            VertexNode_t vertices[256];
            size_t numberOfVertex;
        } Graph_t;
    }

    //邻接多重表实现（存储结构）
    namespace adjacency_multilist_impl
    {
        //进行声明以在实现中使用
        struct ArcNode_s;
        struct VertexNode_s;

        typedef struct ArcNode_s
        {
            //指向邻接顶点
            //若为有向弧，i为弧尾，j为弧头
            struct { struct VertexNode_s *i, *j; } vertices;

            //link.i指向下一条依附于顶点vertices.i的弧
            //link.j指向下一条依附于顶点vertices.j的弧
            //特别地，若为有向弧
            //link.i指向弧尾vertices.i相同的下一条弧
            //link.j指向弧头vertices.j相同的下一条弧
            struct { struct ArcNode_s *i, *j; } link;

            struct ArcNode_s *lastArc;//指向上一条弧
            struct ArcNode_s *nextArc;//指向下一条弧
            void *data;//与该弧有关的数据
        } ArcNode_t;
        typedef struct VertexNode_s
        {
            //依附于当前顶点（Vertex）的边（对于有向图是以当前顶点作为弧尾的弧）
            //作为结点构成了一个链表，firstArc指向该链表的第一个结点
            struct ArcNode_s *firstArc;
            void *data;
        } VertexNode_t;
        typedef struct
        {
            VertexNode_t vertices[256];
            size_t numberOfVertex;
        } Graph_t;
    }

    //十字链表实现（存储结构）
    namespace orthogonal_list_impl
    {
        //进行声明
        struct ArcNode_s;
        struct VertexNode_s;

        typedef struct ArcNode_s
        {
            //指向邻接顶点
            //若为有向弧，i为弧尾，j为弧头
            struct { struct VertexNode_s *i, *j; } vertices;

            //link.i指向下一条依附于顶点vertices.i的弧
            //link.j指向下一条依附于顶点vertices.j的弧
            //特别地，若为有向弧
            //link.i指向弧尾vertices.i相同的下一条弧
            //link.j指向弧头vertices.j相同的下一条弧
            struct { struct ArcNode_s *i, *j; } link;

            struct ArcNode_s *lastArc;//指向上一条弧
            struct ArcNode_s *nextArc;//指向下一条弧
            void *data;//与该弧有关的数据
        } ArcNode_t;
        typedef struct VertexNode_s
        {
            //firstIn指向该顶点的第一条入弧
            struct ArcNode_t *firstIn;
            //firstOut指向该顶点的第一条出弧
            struct ArcNode_t *firstOut;
            void *data;//与该弧有关的数据
            //这样弧头相同的弧都在一条链表上
            //弧尾相同的弧也在同一链表上
        } VertexNode_t;
        typedef struct
        {
            VertexNode_t vertices[256];
            size_t numberOfVertex;
        } Graph_t;
    }
    //由有向图和无向图的定义可知，无向图是有向图的特例。
    //实际应用中的弧通常是有向的，无向图的应用较少。
    //所以在算法实现中我们认为所有的弧都是有向的
    //如需使用边（无向弧），则加入两条数据域相同而头尾互换的有向弧
    

    //邻接表和邻接多重表的顶点的存储结构是一致的
    //每一个顶点都含有一个链表的入口（和与该顶点有关的数据域），区别在于
    //在邻接表中，从每一个顶点所对应的链表的入口中获得的每一个结点为以其对应顶点作为弧尾的弧
    //在邻接多重表中，从每一个顶点所对应的链表的入口中获得的每一个结点为与其邻接的弧（而不仅限于以其对应顶点作为弧尾的弧）

    //邻接多重表和十字链表的弧的存储结构是一致的，区别在于
    //邻接多重表中每一个顶点都含有一个链表的入口（其中每一个结点为与该顶点邻接的弧）
    //十字链表中每一个顶点都含有两个链表的入口
    //从其中一个链表入口（firstIn）中获得的每一个结点为以该顶点为弧尾的弧
    //从另外一个链表入口（firstOut）中获得的每一个结点为以该顶点为弧头的弧

    //由上述存储结构的异同，我们可以使用宏(Macro)将图的上述存储结构编写在一起
    //在C++中不提倡使用宏，可以以模板类和模板函数。
}

由有向图和无向图的定义可知，无向图是有向图的特例。实际应用中的弧通常是有向的，无向图的应用较少。因此在算法实现中我们认为所有的弧都是有向的，如需使用边（无向弧），则采用两条数据域相同而头尾互换的有向弧。
上述存储结构的异同
- 邻接表和邻接多重表的顶点的存储结构是一致的，每一个顶点都含有一个链表的入口（和与该顶点有关的数据域），区别在于：
  - 在邻接表中，从每一个顶点所对应的链表的入口中获得的每一个结点为以其对应顶点作为弧尾的弧。
  - 在邻接多重表中，从每一个顶点所对应的链表的入口中获得的每一个结点为与其邻接的弧（而不仅限于以其对应顶点作为弧尾的弧）。
- 邻接多重表和十字链表的弧的存储结构是一致的，区别在于：
  - 邻接多重表中每一个顶点都含有一个链表的入口（其中每一个结点为与该顶点邻接的弧）。
  - 十字链表中每一个顶点都含有两个链表的入口：从其中一个链表入口（firstIn）中获得的每一个结点为以该顶点为弧尾的弧；从另外一个链表入口（firstOut）中获得的每一个结点为以该顶点为弧头的弧。
由上述存储结构的异同，我们可以使用宏(Macro)将图的上述存储结构编写在一起；在C++中不提倡使用宏，可以以模板类和模板函数。

7.3 图的遍历（深度优先搜索和广度优先搜索）

教材第170页算法7.6（广度优先搜素）中的队列中的每一个结点可以理解为——该结点已访问过但是其子结点尚未访问过。深度优先搜索用递归方法非常易于实现。

7.4 图的连通性问题

7.4.1 无向图的连通分量和生成树

- 对于连通图：从图中任一顶点出发进行搜索，即可访问图中所有顶点，且图中所有顶点和遍历过程中经过的边的集合一起构成了极小连通子图，同时也是该连通图的一棵生成树。（其极大连通子图便是连通图本身）
- 对于非连通图：需要从多个顶点出发进行搜索，每一次从一个新的起始点出发进行搜索过程中所得到的顶点集，和所有依附于这些顶点的边便构成了非连通图的各个连通分量（极大连通子图）;而该顶点集和遍历该顶点集时所走过的边一起构成了各个连通分量的生成树（极小连通子图）。这些连通分量的生成树组成非连通图的生成森林。
称由深度优先搜索得到的生成树为深度优先生成树；由广度优先搜索得到的生成树为广度优先生成树。

7.4.2 有向图的强连通分量

7.4.3 最小生成树

最小生成树（Minimum Cost Spanning Tree）：连通网的最小代价生成树（以各边权值表示对应的代价）。

Prim算法
设是顶点集的一个非空子集，是上最小生成树中边的集合。
- 初始状态： $U = \{ u_0 \},u_0 \in V$ ， $TE= \{ \}$
  在所有满足 $u \in U,v \in V-U$ 的边中找一条代价最小的边 $(u,v)$ 并入集合 $TE$ ，并将 $v$ 并入 $U$ ，直到 $U = V$ 。此时 $TE$ 中必有 $n-1$ 条边， $(V,\{ TE \} )$ 即为最小生成树。
  Prim算法的时间复杂度显然为平方阶。
Kruskal算法

7.4.4 关节点和重连通分量

若在删去顶点 $v$ 以及和 $v$ 相关联的各边之后，顶点 $v$ 所在的连通分量被分割成两个或两个以上的连通分量，则称顶点 $v$ 是该图的一个关节点（articulation point）。
一个没有关节点的连通图称为重连通图（biconnected graph）。在重连通图中，任意一对顶点之间至少存在两条路径，则在删去某个顶点以及依附于该顶点的各边时不会破坏图的连通性。
关节点的特性
- 若生成树的根有两颗或者两颗以上的子树，则此根节点必为关节点。
- 若生成树的某个非叶子节点 $v$ 的子树的根和结点均没有指向 $v$ 的祖先的边，则 $v$ 为关节点。
根据关节点的特性，由一次深度优先搜索即可求得连通图中存在的所有关节点。易于编程实现。

7.5 有向无环图及其应用（在当代最著名的应用便是Git）

检查无向图和有向图是否存在环
- 对于无向图：若深度优先搜索过程中出现指向已访问过的顶点的边，则必定存在环。
- 对于有向图：（见7.5.1 拓扑排序）

7.5.1 拓扑排序（Topological Sort）

拓扑排序（Topological Sort）：由某个集合上的偏序得到该集合上的一个全序，即由偏序定义得到拓扑有序序列）。
- 偏序（partial order）：集合中仅有部分成员之间可以比较。
- 全序（total order）：集合中任意两个成员之间均可比较。

如何进行拓扑排序

do {
    在有向图中选一个无前驱的顶点并将其输出;
    从图中删去该顶点和以它为尾的弧;
} until(全部顶点均已输出 || 图中不存在无前驱的顶点)
if(图中不存在无前驱的顶点) println("有向图中存在环");

当有向图中无环时，也可利用的深度优先搜索进行拓扑排序。

7.5.2 关键路径（Critical Path）

AOV与AOE
- 以顶点表示活动的网——Activity On Vertex Network,AOV
- 以边表示活动的网——Activity On Edge,AOE
  对于AOE网，可以在以边表示活动的同时，以弧的权表示活动的持续时间等信息，并且同时可以在顶点中表示活动之间的信息，例如事件（Event）。所以，AOE的适用范围比AOV更广；但是对于一些应用而言，AOV更简洁，例如Git就是AOV的应用的一个十分成功的例子。
在AOE网中，如果以边的权表示持续时间，则AOE网可以用来估算工程的完成时间，此时，定义路径长度为路径上各活动的持续时间之和（而不是路径上弧的数目）。
- 由于有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的的最长路径的长度。路径长度最长的路径称为关键路径（Critical Path）。
- 若将 $v_0$ 作为起始点，则从 $v_0$ 到 $v_i$ 的最长路径长度即为事件 $v_i$ 的最早开始时间，这个时间决定了所有以 $v_i$ 为尾的弧所表示的活动 $a_i$ 的最早开始时间 $e(i)$ （这些活动的开始时间不仅取决于事件 $v_i$ 的最早开始时间，同时也取决于事件 $v_i$ 所消耗的时间）。在编程中表示事件 $v_i$ 的下标 $i$ 和表示活动及活动最早开始时间 $e(i)$ 的编号 $i$ 可能是不同的，应当具体情况具体分析。
- 定义活动的最迟开始时间 $l(i)$ 为不推迟整个工程完成时间的前提下，活动 $a_i$ 最迟必须开始的时间。两者之差 $l(i) - e(i)$ 即为完成活动 $a_i$ 的时间余量。将 $l(i)=e(i)$ 的活动称为关键活动。显然关键路径上的活动都是关键活动；因此提前完成非关键活动不能加快整个工程的进度，分析关键路径的目的是辨明哪些是关键活动，以便争取提高关键活动的效率以缩短整个工期。
- 若以弧表示活动，其持续时间为，事件的最早发生时间为，事件的最迟发生时间为。则有如下关系：
  
  显然我们需要求得和。
  1. 向前递推求 $ve(j)$
    $\begin{align*} ve(j)&=\max_i \{ ve(i) + dut(<i,j>) \},<i,j> \in T \\ ve(0) &= 0 \end{align*}$
    
    其中 $T$ 是所有以第 $j$ 个顶点为头的弧的集合。
  2. 向后递推求 $vl(i)$
    $\begin{align*} vl(i) &= \min_j \{ vl(j)-dut(<i,j>) \}&,&<i,j> \in S \\ vl(i) &= ve(i)&,& \ S=\phi \end{align*}$
    
    其中 $S$ 是所有以第 $i$ 个顶点为尾的弧的集合。由此可见，为确定出度为0的顶点（一般为工程的完成点）的最迟发生时间，我们需要求得该顶点的最早发生时间。所以上述两个递推公式的计算必须在拓扑有序的前提下进行。从起始点 $v_0$ 出发，令 $ve(0)=0$ ，按拓扑有序求其余各顶点（包括完成点）的最早发生时间。
  - 算法
    1. 从起始点 $v_0$ 出发，令 $ve(0)=0$ ，按拓扑有序求其余各顶点（包括完成点）的最早发生时间。若得到的拓扑有序序列中顶点的个数小于网络中的顶点数，则说明网络中存在环，不能求其关键路径。
    2. 从完成点（出度为0的点）出发，令其最迟发生时间等于最早发生时间，按上述第二项递推公式求得其余各顶点的最迟发生时间。
    3. 根据各事件（顶点）的最早发生时间和最迟发生时间求得各活动（弧）的最早开始时间和最迟开始时间。满足最早开始时间与最迟开始时间相等的弧即为关键活动。
  如果有时间，可以自己实现一遍。

7.6 最短路径

Dijkstra算法和Floyd算法

Dijkstra算法（迪杰斯特拉算法）

选定起始点 $v$ 。设置线性表 $D$ ，其中每个元素 $D(i)$ 表示当前所找到的从起始点 $v$ 到每个终点 $v_i$ 最短路径的长度，以弧 $<v,v_i>$ 的长度或 $\infty$ （若弧不存在）初始化之。设置 $S$ 为已找到的从 $v$ 出发的最短路径的终点的集合，初始状态为空集。 $arcs$ 为邻接矩阵。
选择 $j=\mathop{\arg\min}_{i} \big \{ D(i)|v_i \in V-S \big \}$ ，那么 $v_j$ 就是当前求得的一条从 $v$ 出发的最短路径的终点，并将 $v_j$ 并入集合 $S$ 中（ $S = S \cup v_j$ ）。
遍历集合 $V-S$ 中的所有顶点：对于 $v_k \in V-S$ ，如果 $D(j) + arcs[j][k]<D(k)$ ，则以其更新 $D[k]$ 。
重复2，3步直到 $n-1$ 次，即直到 $V-S$ 为空集。

Floyd算法

算法步骤
令网络的权矩阵为 $D = (d_{ij})_{n \times n}$ ，设 $l_{ij}$ 为从顶点 $v_i$ 到 $v_j$ 的直接距离，其中 $d_{ij}= \left\{ \begin{aligned} l_{ij},<v_i,v_j>\in VR\\ \infty,<v_i,v_j>\notin VR \end{aligned} \right.$
初始权矩阵 $D^{(0)}=D$ 。计算 $D^{(k)} = (d_{ij}^{(k)})_{n \times n},k=1,2,...,n$ ，其中 $d_{ij}^{(k)}=\min \{ d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)} \}$ 。
进行n次迭代之后 $D^{(n)} = (d_{ij}^{(n)})_{n \times n},k=1,2,...,n$ 中的各个元素即为点 $v_i$ 到点 $v_j$ 的最短路长。
本文作者的一些经历和想法
最初接触Dijkstra算法和Floyd算法是在低年级时准备全国大学生数学建模竞赛时，当时有一本书给出了Dijkstra算法和Floyd算法的MATLAB程序，但是当时我的编程能力比较弱，对于算法方面的内容抱有畏惧心理。故只知其然，而不知其所以然。
Floyd算法的迭代过程实在是令我错愕， $d_{ij}^{(k)}=\min \{ d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)} \}$ 的原理是什么呢？为什么迭代 $n$ 次，即顶点的数量即可得到最短路径呢？
算法简析

第7章图

第7章图

7.1 图的定义和术语

7.2 图的存储结构

7.2.1 数组表示法

7.2.2 邻接表

7.3 图的遍历（深度优先搜索和广度优先搜索）

7.4 图的连通性问题

7.4.1 无向图的连通分量和生成树

7.4.2 有向图的强连通分量

7.4.3 最小生成树

7.4.4 关节点和重连通分量

7.5 有向无环图及其应用（在当代最著名的应用便是Git）

7.5.1 拓扑排序（Topological Sort）

7.5.2 关键路径（Critical Path）

7.6 最短路径

Dijkstra算法（迪杰斯特拉算法）

Floyd算法

推荐阅读更多精彩内容

第7章 图

7.1 图的定义和术语

7.2 图的存储结构

7.2.1 数组表示法

7.2.2 邻接表

7.3 图的遍历（深度优先搜索和广度优先搜索）

7.4 图的连通性问题

7.4.1 无向图的连通分量和生成树

7.4.2 有向图的强连通分量

7.4.3 最小生成树

7.4.4 关节点和重连通分量

7.5 有向无环图及其应用（在当代最著名的应用便是Git）

7.5.1 拓扑排序（Topological Sort）

7.5.2 关键路径（Critical Path）

7.6 最短路径

Dijkstra算法（迪杰斯特拉算法）

Floyd算法

推荐阅读更多精彩内容

第7章图