数据结构--图论

发表于 2022/12/07 更新于 2024/02/04

作者 Jinkai

21 分钟阅读

图论（Graph Theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

基本概念

点和边

图由顶点和边构成，边用于连接两个点

顶点：通常用 V(vertex) 表示顶点集合
- 度(Degree)：所有与该点连接的边数之和
- 入度(Indegree)：存在于有向图中，所有接入该点的边数之和
- 出度(Outdegree)：存在于有向图中，所有接出该点的边数之和
边：通常用 E(edge) 表示边的集合

有向图和无向图

(v, w) 表示无向边，即 v 和 w 是互通的
<v, w> 表示有向边，该边始于 v，终于 w

有权图和无权图

有权图：每条边具有一定的权重(weight)，通常是一个数字
无权图：每条边均没有权重，也可以理解为权为 1

连通图和非连通图

连通图(connected graph)：对于无向图，任意两个点间都存在路径
- 强连通(strongly connected)：必须是有向图，任意两个点间都存在互相可达的路径
- 单连通(unilaterally conncected)：必须是有向图，任意两个点间都存在可达的路径（无需互相可达）
非连通图：至少存在某两个点之间没有路径
连通分量：图中的子图符合连通要求时，把这个子图称为连通分量。连通图的子图中只有自身(自身也属于子图)是连通分量

图的表示

邻接矩阵和邻接表

邻接表一般用链表的形式表示，也可以叫邻接链表

无向无权图:

无向有权图:

有向无权图:

邻接矩阵和邻接表对比：

邻接矩阵由于没有相连的边也占有空间，因此存在浪费空间的问题，而邻接链表则比较合理地利用空间
邻接链表比较耗时，牺牲很大的时间来查找，因此比较耗时，而邻接矩阵法相比邻接链表法来说，时间复杂度低。

图的遍历

深度优先遍历：(Depth First Search, DFS)
广度优先遍历：(Breadth First Search, BFS)

不同的图的表示有不同的遍历逻辑，很好理解，不再赘述

环检测算法

深度优先遍历算法

深度优先(DFS)遍历所有点，每访问一个点，将其标记为已访问，如果在遍历过程中有边指向已访问的点，则视为产生环。

拓扑排序

拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图（DAG）才有拓扑排序，非 DAG 图没有拓扑排序一说。

贪心算法创建拓扑排序：

从 DAG 图中选择一个没有前驱（即入度为 0）的顶点并输出。
从图中删除该顶点和所有以它为起点的有向边。
重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

最短路径算法 (Shortest Path Algorithm)

求某点到另一目标点的最短路径，一般将无权图的边视为权值为 1

Dijkstra 迪杰斯特拉算法

广度优先扩散式遍历所有点，直到遍历到终点开始沿路线返回。一定能找到最短路径。慢速但正确。

一般需要一个开启列表和关闭列表用于保存状态，在后面介绍 A* 算法时有详细介绍

Floyd 佛洛伊德算法

利用了动态规划思想

假设图中共有 $x$ 个点，分别标号为 1 到 $x$，出发点标号为 start，结束点标号为 end

思路 1
设$D_{i,j,k}$为从$i$到$j$的只以${1..k}$(不包括 start 和 end)集合（可以称为中间点集合，不允许经过不在该集合内的点）中的节点为中间节点的最短路径的长度，目标是求$D_{start,end,x})$的最小值。
假设 start 和 end 之间直接距离为 10（不可直接达就是 ∞，反正就是有个值），如果只引入一个点 A 中转，能让距离缩短，更新 start 和 end 间的最短路径；如果再加入一个点 B 中转，点 B 可能是 start 和 A 间的，也可能是 A 和 end 间的，也有可能直接在 start 和 end 间，但是能让这两个点间的距离缩短，更新这两个点间的最短路径，同时更新 start 和 end 间的最短路径。遍历每个点，使用一个中间点集合不断加入点并更新每个点间的最短路径，则能得到一个最短路径解。
示例图：
不经过中间点（中间点集合为空）：
仅经过 1 （中间点集合为 {1} ）：
此时 3 到 2 有了可达路径，距离从 ∞ 到了 9（3->2->1），其他点类似
仅经过 1,2 （中间点集合为 {1,2} ）：
问题就在于按照什么顺序去遍历，主要是规避后效性。假设我们将点 4 添加到中间点集合，那么理论上 3->1 的距离会被更新为 6（3->4->1 或者 3->x->4->x->1），这就需要先更新 3->4 的距离和 4->1 的距离，3->4 的距离并不会因为点 4 被加入中间点集合而被缩短，同理 4->1 也不会，可以证明无后效性，也就是更新 3->4 的距离和 4->1 的距离这个操作的先后顺序不会影响计算 3->1 距离的决策
列出状态转移方程：
$E_{i,j}=min(E_{i,j},E_{i,k}+E_{k,j})(k \in {1,…,x})$
思路 2
该问题可分解为经过某个点k的情况和不经过某个点k的情况:
- 假设 $i$ 到 $j$ 的最短路径经过k，则该路径一定能拆解为 $i$ 到 $k$ 的最短路径加上 $k$ 到 $j$ 的最短路径（符合最优子结构，最优解所包含的子问题的解也是最优的）。因为 $i$ 到 $k$ 的最短路径一定不再包含中间点 $k$，于是将 $k$ 从中间点集合中删除，变为 ${1..k-1}$。得到如下方程：
  $D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}$
- 假设$i$到$j$的最短路径不经过k，则可将$k$从中间点集合中删除，变为${1..k-1}$。得到如下方程：
  $D_{i,j,k}=D_{i,j,k-1}$
- 设 k 为 0 时表示直接距离（$i$ 和 $j$ 相连边的权值，如果不相邻则该值为无穷大，一般赋值为 0 就表示无穷大）
  $D_{i,j,0}=L_{i,j}$
最短路径为两种情况取最优的情况，也就是最小值（符合无后效性，某阶段状态一旦确定，就不受这个状态以后决策的影响，$D_k$的状态总是由$D_{k-1}$转化而来($i$,$j$相同时)，不会出现$D_k$影响$D_{k-1}$的情况）。列出状态转移方程：
$D_{i,j,k}=min(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})$
原表达式是通过 k 的收缩不断分解问题的，自底向上来看就是 k 递增的过程，所以这里的遍历方式也是 k 递增。利用滚动数组优化，可以在滚动过程中抛弃(无需保存)无用解，直接用$E_{i,j}$变量保存滚动保存每次计算后的最优解。优化后的状态转移方程：
$E_{i,j}=min(E_{i,j},E_{i,k}+E_{k,j})(k \in {1,…,x})$
$E_{i,j}$ 初始值是 $L_{i,j}$

实现：

  
// 这里的点集合是{0,..,n-1}
for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]);
        }
    }
}
min_dst = a[start][end]

最小生成树 (Minimum Spanning Trees MST)

生成树: 无向图 G 的生成树（英语：Spanning Tree）是具有 G 的全部顶点，但边数最少的连通子图（连通子图并非连通分量）。一个图的生成树可能有多个。
最小生成树: 带权图的生成树中，总权重最小的称为最小生成树。

实例：要在 n 个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

Prim 普里姆算法

一种贪心算法，不过可以获取最优解，复杂度是$O(Elog{E})$

输入：一个加权连通图，其中顶点集合为 V，边集合为 E
初始化：Vnew = {x}，其中 x 为集合 V 中的任一节点(起始点)，Enew = {} 为空（证明：生成树一定是连通图，所以每个点一定有边相连，且可到达任意其他点，所以任意一点都可以作为起始点）
在集合 E 中选取权值最小的边 <u, v>，其中 u 为集合 Vnew 中的元素， v∈V 且 v 不在 Vnew 集合当中(如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一)。（证明：Vnew 表示已经连通的点集合，若要添加新的点进来，需要从该子图中找到一条边可以连到新的点，这里按权值选取起点在 Vnew 内且权值最小的边，这样就能确定要新添加的是哪个点了。要证明这条边一定属于最小生成树，可以用反证法：如果这条边不在最小生成树中，它连接的两个连通分量最终还是要连起来的，通过其他的连法，那么另一种连法与这条边在原图中一定构成了环，而环一定是能剪开的（所以叫生成树，树是没有环的），环中一定有一条权值大于这条边的边(至少就是起点是 u 的其他边一定比这条边大)，用这条边将其替换掉，子图仍旧保持连通，但总权值减小了。也就是说，如果不选取这条边，最后构成的生成树的总权值一定不会是最小的。）
将 v 加入集合 Vnew 中，将 <u, v> 边加入集合 Enew 中
重复步骤 3、4 直到 Vnew = V

Kruskal 克鲁斯克尔演算法

新建图 G，G 中拥有原图中相同的节点，但没有边
将原图中所有的边按权值从小到大排序
从权值最小的边开始，如果这条边连接的两个节点于图 G 中不在同一个连通分量中（避免生成环），则添加这条边到图 G 中
重复 3，直至图 G 中所有的节点都在同一个连通分量中

看示意图很好理解，每个不同的颜色表示独立的连通分量，在避免生成环的同时，依次添加最短的边让全部独立的连通分量连通。

和 Prim 算法的区别是 Prim 算法会构造并扩充一个大连通分量，而 Kruskal 算法可能会构造多个独立的大的连通分量最后将这几个连通分量相连。核心思想是一样的，也就是用贪心算法选最短边。

启发函数

评估当前点与终点的距离代价。

比如最佳优先搜索 BFS 算法，直接无视障碍物（极大的边权值）计算和终点的直线距离，因为两点之间直线最短，希望下一步更接近目标。快速但不正确

A*算法

结合广度优先遍历的 Dijkstra 算法和启发函数，一般用于游戏地图的自动寻路。

$f(n) = g(n) + h(n)$

f(n)表示在当前情况下从起点到终点的最小总代价（预估），g(n)表示起点到 n 的代价（实际，通过回溯计算已经移动的距离），h(n)表示启发函数算得的n 到终点的最小代价（预估，启发函数）

使用贪心策略，总是往f(n)更小的方向移动

Dijkstra 算法准确但慢，特别是范围扩大时计算量呈指数级增长，主要原因是它浪费了时间去探索没有希望的方向，所以我们希望引导 Dijkstra 算法遍历的方向，也就是尽可能抛弃无用的遍历（或者叫优先遍历更有希望的节点）。A*算法就是利用了启发函数来过滤 Dijkstra 算法无效的遍历。

首先需要两个数组：

开启列表 open_set：保存待计算的节点
关闭列表 close_set：保存已计算的节点

然后是一个变量：

当前节点：正在计算的节点

概念：

优先级：f(n)越小，优先级越高，也就是越有希望，需要优先遍历
回溯：遍历到终点后，逆向寻找返回起始点的路径
邻近节点：下一步可走的节点，比如只能十字方向走的情况下，斜对角的节点就不是临近节点

算法步骤：

初始化 open_set 和 close_set；
将起点加入open_set中，并设置优先级为 0（优先级最高）；
如果open_set不为空，则从 open_set 中选取优先级最高（就是 f(n)最小）的节点 n：
- 如果节点 n 为终点，则：
  - 从终点开始逐步追踪parent节点，一直达到起点；
  - 返回找到的结果路径，算法结束；
- 如果节点 n不是终点，则：
  - 将节点 n 从 open_set 中删除，并加入close_set中；
  - 遍历节点 n 所有的邻近节点：
    - 如果邻近节点 m 在close_set中，则：
      - 跳过，选取下一个邻近节点
    - 如果邻近节点 m 也不在open_set中，则：
      - 设置节点 m 的parent为节点 n
      - 计算节点 m 的优先级（f(n)）
      - 将节点 m 加入open_set中

参考

学习笔记

数据结构

本文由作者按照 CC BY 4.0 进行授权