图

基本概念

图的定义

图 $G$ 由顶点集 $V$ 和边集 $E$ 组成，记作 $G(V,E)$ ，顶点集一定非空，因此，图不能为空，但是边集可以为空。

图的存储及基本操作

基本要求

完整、准确地反应顶点集和边集的信息，根据不同图的结构和算法，采用不同的存储方式也有很大影响。

邻接矩阵法

邻接矩阵

使用一个一维数组存储图中的顶点信息，用一个二维数组存储图中边的信息，这个二维数组就是所谓的邻接矩阵。

对于普通图，邻接矩阵是一个二值矩阵，为 $1$ 则表示其对应的两个顶点存在一条边相连；如果是带权图，则不是二值矩阵，对应位置存放边的权值，不存在边的位置则存储无穷。

对于无向图来说，邻接矩阵是一个对称矩阵，因此规模较大时可以采用压缩矩阵的方式存储。

对于简单应用来说，可省略存储顶点信息的一维数组。

特点

无向图邻接矩阵的第 $i$ 行（第 $i$ 列) 中的非零元素（对于带权图是非无穷元素，下同）的个数是顶点 $V_i$ 的度；
对于有向图，邻接矩阵的行非零元素是对应顶点的出度，列非零元素则是入度；
邻接矩阵可以很方便确定两个顶点之间是否有边相连，但是要求所有边的个数则时间复杂度为 $O(|V|^2)$ ；
显然稠密图更适合用邻接矩阵表示；
设图的邻接矩阵为 $A$ ，则 $A^n$ 中对应位置表示两个顶点之间长度为 $n$ 的路径的数目（这是显然的，具体证明在离散数学中）。

邻接表法

对图中的每个顶点指向的顶点建立一个单链表，这些顶点由形成一个顺序结构，单链表中就存储这对应节点的下标。

特点

对于无向图，空间复杂度是 $O(|V|+2|E|)$ ，有向图则是 $O(|V|+|E|)$ ；
与邻接图相反，邻接表不能快速找到两个顶点是否相邻，但是可以很容易得到一个顶点与的边；
有向图的邻接表可以快速求出出度，但是求入度则需要遍历所有节点，因此也有 逆邻接表 用于快速求入度；
邻接表表示不唯一，顶点单链表中元素顺序任意。

十字链表

有向图的一种链式存储结构，可以认为是邻接表法的双向扩展，即在邻接表的基础上，额外构建了一个描述入度的链路；

英文是 Orthogonal List，实际上是正交链表。

通过十字链表，可以很方便的求出度和入度。

从名字上来说，十字链表实际上是正交链表，其所指的就是二维矩阵中的上下左右四个方向，由有向图的邻接矩阵可知，行表示出，列表示入，因此只需要将非零顶点连接起来即可，链表节点的前两个整数表示所在矩阵中的第几行几列，后两个指针表示在矩阵中该元素的下方和右方的第一个非零元素所形成的节点。

但是我们创建十字链表时不可能先创建一个邻接矩阵，因此考虑从另一个方面理解。

由邻接表法扩展至十字链表法是很合理的，要想在邻接表法的基础上实现双向索引的功能，我们考虑在保持原先邻接表中额外添加一条链路描述顶点的入度路径：

为顺序结构中的每个顶点额外添加一个指针域，以此为起点构建一个 逆邻接表（即以此找到所有的）；
有向图的入度和与出度和是相同的，这是我们保持邻接表结构、数目不变的依据；
由第一第二条，我们可以 重复利用邻接表中已经有的链表节点，并将相应的节点相连；假设一个顶点 $V_{0}$ 的出度为 $n$ ，描述入度时，就会有 $n$ 个顶点（可以重复，虽然本章讨论的是简单图）会找到 $V_{0}$ ，而邻接表中 $V_{0}$ 的单链表刚好有 $n$ 个元素，恰好一一对应这 $n$ 个顶点；
由于是额外建立一个逆邻接表，因此节点中需要额外添加一个指针域，指向下一个同级前驱；另外此时只是形成了一个通路，并不知道每个节点所表示顶点是什么，因此要额外添加一个整数，表示是哪一个节点。

🤔

上文中的 重复利用邻接表中已经有的链表节点，节点间共用数据部分，可以节省内存，实际上完全可以将邻接表和逆邻接表拼在一起，数据部分使用指针（对于稀疏矩阵来说，这点数据占用应该不是不可接受的），因此十字链表法的主要作用和应用是啥？（不懂）

邻接多重表

无向图的链式存储结构，由于无向图的性质，其邻接矩阵是一个对称矩阵，因此存储的时候只需要存储一半即可。与十字链表类似，不再赘述。

图的遍历

tip

从某一顶点出发，按照某种方式访问所有顶点且 仅访问一次。

由于图结构的复杂性，一个顶点可以与任意的顶点相连接，遍历时很容易会再回到该顶点，因此通常使用一个 visited 数组来标识顶点是否被访问过。

广度优先搜索

类似于二叉树的层序遍历，指的是先访问某一个顶点的所有邻接顶点，在分别以同样的方式操作其所有邻接顶点。

实现上一般采用队列，当首先访问第一个顶点，入队，此后执行出队、访问出队元素的所有邻接顶点并入队，如此反复，直到队列为空，再寻找图中未被访问的顶点，执行相同的操作。

广度优先算法适合求解单源最短路径问题，因为其总是按照距离远近来遍历的，当最短的遍历结束后可直接结束循环。

同时广度优先搜索的过程中，可以得到一颗遍历树，成为广度优先生成树，若图是邻接矩阵存储的，则树也是唯一的，若为邻接表则不唯一，下面的深搜也是同理。

深度优先搜索

类似于树的先序遍历，先访问一个顶点及其后继，直到没有后继。，则返回上一个的顶点访问其其余的后继。

实现上可以使用栈，由于递归本身就是一个栈，直接使用递归实现即可。

深度优先生成树：略。

图的遍历与连通性

通过图的遍历算法可以判断图的连通性，从任意一个节点出发，只需要一次遍历就能访问图中的所有顶点。

图的应用

最小生成树

连通图所能生成的包含最少的边的连通生成树，若再添加一条边，就会形成回路，去除一条边，则会使生成树变为非连通图。

对于带权图，还需要保证边的权值之和最小。

容易看出最小生成树的一些性质：

不唯一，但当边权值各不相同时， $G$ 的最小生成树是唯一的；若无向图连通图的边数比顶点树少 1，则其本来就是最小生成树。
最小生成树不唯一，但是权值之和唯一其最小；
最小生成树的边数为顶点数减去 1.

最小生成的构造算法大多基于以下性质：对于带权无向连通图的一条权值最小的边，一定存在一棵包含这条边的最小生成树。

Prim 算法

十分类似与寻找图的最短路径的 $Dijkstra$ 算法，其构造算法如下：

初始时从图中任意选取一个顶点加入树中；
从剩余的顶点和边当中选择一个与当前树中距离最近的顶点和对应边，加入树中；
重复第二步，直到所有节点都添加到树中。

时间复杂度为 $O(|V|^2)$ ，不依赖于 $|E|$ 适合求解稠密图的最小生成树。

Kruskal 算法

按照边权值的递增序列选择合适的边来构造最小生成树：

初始时树中只有节点而没有边，并对所有边按照权值递增排序；
选择一个最小的边加入树中，若构成回路则舍弃选择下一条权值最小的边；
执行第二步知道所有顶点都能连通。

note

通常使用堆来存放边的集合，因此每次选择最小权值边的时间复杂度为 $O(\log_{2}|E|)$ ，另外，生成树的所有边可以视为一个等价类，每次添加新的边的过程类似于求解等价类的过程，可以采用并查集来描述，因此构造生成树的时间复杂度是 $|E|\log_{2}|E|$ ，因此 $Kruskal$ 算法适用于边稀疏而顶点较多的图。

最短路径

前文所提到的使用广度搜索只能针对无权图，而对于带权图则需要以边权进行加权。求解最短路径的算法通常基于一个性质——两点之间的最短路径也包含路径上其他点之间的最短路径。最短路径通常可以分为两种，单源最短路径——求某一点的到其他各顶点的的最短路径，可以通过 $Dijkstra$ 算法求解；求每一对顶点之间的最短路径，可以使用 $Floyd$ 算法。

Dijkstra 算法

初始时将起点 $v_{0}$ 放入集合，集合中每添加一个顶点，都要修改起点到剩余顶点的最短路径长度。构造过程中需要使用两个辅助数组 dist 和 path 分别用于存放起点到其他各个顶点之间的长度，和对应顶点到原点路径的 前驱顶点。

算法主要流程如下：

初始化：dist 数组初始化为邻接矩阵中起点对应的权值，若不存在起点到该点值，则初始化为 $\infty$ ；
从剩余的顶点集合中选出一个距离集合最近的一个 $v_{1}$ ，加入集合中；
更新 dist：更新起点到所有剩余节点的最短路径，若从 $v_{0}$ 到 $v_{1}$ 所的路径长度加上 $v_{1}$ 到另一顶点 $v_{2}$ 的路径长度小于 dist 中原来的路径长度，则更新上去；
重复第二到三步 $n-1$ 步。

时间复杂度为 $O(|V|^2)$ ，如果求解某个节点到特定节点之间的最短路径，时间复杂度不变。

caution

当边上有负权值时，本算法并不适用，因为后续更新时可能会获得小于已经确定的最短路径。

dijkstra 算法和 prim 算法的相似之处

都是基于贪心策略的算法，每次选择当前最优的节点；
都需要维护一个集合来记录已经被遍历的节点；
都需要更新节点的最短距离。

Floyd 算法

问题定义

在一个各边权值大于 $0$ 的带权有向图中，对于任意的两个顶点 $v_i\neq v_j$ ，求出 $v_{i},v_{j}$ 之间的最短路径长度。

本算法的基本思想是，递推产生一个 $n$ 阶方阵序列 $A^{(-1)},A^{0},\cdots,A^{(n-1)}$ ，其中 $A^k[i][j]$ 表示顶点 $i$ 到顶点 $j$ 之间的路径长度， $k$ 表示绕行第 $k$ 个顶点的运算步骤。

使用邻接矩阵作为初始矩阵， $\infty$ 表示不存在路径。随后不断尝试添加在原路径中添加顶点作为中间顶点，所路径变短了则用新路径替换原路径。

info

实际上是通过中转来计算各个顶点之间的距离，原理为：对于节点 $A[k][k]$ ，其值一定是 $0$ ，因为表示自身之间的距离，以该顶点为中转，计算两个其余两个顶点之间在有 $A[k][k]$ 这个顶点中转的情况下的最短路径。选取第 $i$ 和 $j$ 个顶点，那么这个路径长度就是 $i$ 到 $k$ 的长度加上 $k$ 到 $j$ 的长度，可以表示为

A[k][i] + A[j][k]

再让其和这两个顶点之间原本的长度 $A[i][j]$ 相比，取短者即可。

因此其代码也是简单粗暴取

def Floyd(d):
    n = d.shape[0]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

时间复杂度为 $O(|V|^3)$ ，和为每个节点运行一次 $dijkstra$ 的事件复杂度一样

为了得到最短路径的路线，还需要额外一个矩阵存储，初始矩阵为

\begin{bmatrix} - & 2 &3& \cdots & n \\ 1 & - & 3 &\cdots & n \\ \vdots & \vdots & \vdots & \ddots &\vdots \\ 1 & 2 & 3&\cdots & - \end{bmatrix}

即每列中的数字就是当前的列数，表示从当前顶点到第 $j$ 个节点所经过的顶点（就是第 $j$ 个顶点本身），对角线表示无效数字，因为表示自己到自己的路径。

而如果某个路径更新了，则表示要到这个顶点之前，一定要经过中转顶点，因此更新位置的值设置为此时中转顶点的标号即可，代码可以修改为：

def Floyd(d, s):
    n = d.shape[0]
    for k in range(n):
        for i in range(n):
            for j in range(n):
	            update = d[i][k]+d[k][j]
	            if update < d[i][j]:
		            d[i][j] = update
		            s[i][j] = k
    return d

有向无环图描述表达式

有向无环图

不存在环的有向图，简称为 $DGA$ ，有向无环图常应用于表示依赖关系、自动机、描述含有公共子式的表达式等。

含有公共子式的表达式

使用二叉树表示这样的表达式时会有很多的浪费，可以使用有向无环图进行表示，共用一个公共子式。

深度学习中的使用

深度学习框架中，有向无环图被广泛应用于神经网络模型的训练和推理过程中。以下是 DAG 在深度学习框架中的一些应用：

神经网络模型的构建：神经网络模型可以被表示为一个 $DAG$ ，其中每个节点代表一个模块，每条边代表模块之间的连接。

自动微分：深度学习框架中的自动微分引擎可以通过 $DAG$ 来实现。在训练过程中，自动微分引擎会根据 $DAG$ 计算模型参数的梯度，并将其用于反向传播算法中。

模型优化：深度学习框架中的模型优化算法通常使用 $DAG$ 来表示计算图，以便能够高效地计算梯度和更新模型参数。

分布式训练：在分布式训练中，多个计算节点可以并行地计算 $DAG$ 中的不同部分，从而加速训练过程。深度学习框架中的分布式训练引擎通常使用 $DAG$ 来划分任务，并将其分配给不同的计算节点执行。

拓扑排序

tip

对有向无环图的排序，可以表示顶点之间的依赖顺序关系，和二叉树的层次遍历比较像，可以使用队列实现。

要实现拓扑排序，图中的每个顶点出现且只出现一次。

拓扑排序的算法如下所示：

从 $DGA$ 中选择一个没有前驱的顶点并输出；
删除该顶点以及与之相连接的边；
重复前两步直到图无顶点或者不存在无前驱的顶点，如果仍然存在有前驱的顶点，则说明图中一定存在环。

由于删除每个顶点的同时还要删除与之相连的边，因此若使用 邻接表 存储拓扑排序的时间复杂度为 $O(|V|+|E|)$ ，若采用 邻接矩阵 存储则拓扑排序的时间复杂如为 $O(|V|^2)$ .

info

拓扑排序也可以利用栈和 深度优先遍历 实现，具体方式如下：

入栈所有入度为 $0$ 的节点；
出栈并输出栈顶元素，去除所有与之相邻的边；
循环前两步直到栈为空，（记得检查一下是否遍历了所有的顶点）

需要注意的是，本方法的遍历结果可能不像使用队列的“层次遍历” 一样清晰。

关键路径

AOE 网络

下面所说的网络都是 AOE 网络，即顶点表示事件边表示活动。

求解顺序为：

事件的最早发生时间，由每个顶点的最迟发生时间确定，因为只有前驱活动全部发生完毕后时间才能发生；
活动的最早发生时间，由该活动的起点发生时间确定，即和开始事件同时发生；
事件的最迟发生时间，从最后发生的事件向前推，如果某个事件到前驱事件有多个路径，那么选择最小的，这样才能满足最迟发生的要求；
活动的最迟发生时间，由活动的结束时间最迟的发生时间减去活动的持续时间所确定。

其中活动的最早发生时间和最迟发生时间若相同，则为关键活动。

代码

邻接表的深度优先遍历和广度优先遍历

邻接表需要定义顶点和边

typedef char *VertexType;

typedef struct ArcNode { // 边
  int adjvex; // 所连接的顶点在边表中的索引
  struct ArcNode *next;
} ArcNode;

typedef struct VNode { // 顶点
  VertexType data; // 顶点所存储的信息
  ArcNode *first;
} VNode, *AdjList;

typedef struct Graph {
  int vexnum, arcnum;
  AdjList array;
} Graph;

若想要查找某点到其他点的路径，可以使用深搜

bool DFS(Graph *graph, int start, int end, int *path, int *depth) {
  visited[start] = true; // 可以使用全局变量也可以传入参数。
  path[*depth] = start;

  if (start == end) {
    return true;
  }

  ArcNode *arcNode = graph->array[start].first;
  while (arcNode) { // 挨个访问边节点
    int next = arcNode->adjvex; // 得到下一个顶点的索引
    if (!visited[next]) { // 若没有访问过
      (*depth)++;
      if (DFS(graph, next, end, path, depth))
        return true;
    }
    arcNode = arcNode->next;
  }
  visited[start] = false; // 没有找到需要将当前的visitied置为false，表示回溯
  return false; // 没有找到符合的路径
}

void findPath(Graph *graph, int start, int end) {
  initVisited();

  int path[MAX_SIZE], depth = 0;
  if (DFS(graph, start, end, path, &depth)) {
    for (int i = 0; i <= depth; i++) {
      printf("%s ", graph->array[path[i]].data);
      putchar('\n');
    }
  } else {
    printf("no path");
    putchar('\n');
  }
}

对于邻接矩阵，如下：

void DFS(int start, int end) {
  visited[start] = 1; // 全局变量
  path[pathIndex++] = start; // 全局变量

  if (start == end) {
    int i;
    printf("Path: ");
    for (i = 0; i < pathIndex; i++) {
      printf("%d ", path[i]);
    }
    printf("\n");
  } else {
    int i;
    for (i = 0; i < MAX_VERTICES; i++) {
      if (graph[start][i] == 1 && visited[i] == 0) {
        DFS(i, end);
      }
    }
  }

  pathIndex--; // 回溯
  visited[start] = 0;
}

基本概念​

图的存储及基本操作​

邻接矩阵法​

邻接表法​

十字链表​

邻接多重表​

图的遍历​

广度优先搜索​

深度优先搜索​

图的遍历与连通性​

图的应用​

最小生成树​

最短路径​

有向无环图描述表达式​

拓扑排序​

关键路径​

代码​

邻接表的深度优先遍历和广度优先遍历​