图论之算法篇

发表于 2018-06-19 更新于 2025-02-02 分类于 0-数学基础， F-图论阅读次数：本文字数： 5.7k 阅读时长 ≈ 5 分钟

图论中的算法基本都是提出后，经过检验的。我就不讨论算法很基础的原理，只是从看懂一个算法的角度去学习。本着不花时间去重复别人优秀工作的原则，本文中很多部分引用了别人的工作，甚至是照搬过来，因为我觉得算法这东西已经类似真理 , 证明不需要你，你可以看得懂，别人也可以，只是表达方式不同，别人有优秀的表达方式，我为什么不用呢！

算法类

戴克斯特拉算法 (D.A)

描述: 又译迪杰斯特拉算法 , 使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。

原理: 迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.

迪杰斯特拉算法算法图示

结合上图，详细解释迪杰斯特拉算法:
通过维护一个两个集合来实现:

1. 一个集合内存储已经找到的最短距离及其路径 (假设为 D)
2. 另一个是未找到的最短距离的点到起始顶点的路径 (假设为 U)
下面更新 U 的过程也是如此

图示目标：寻找顶点 1 到所有顶点的最短路径.

第一步：初始化 D,U
初始节点到自身距离为 0, 直接初初始化到 D 集合，U 集合维护顶点到初始节点 1 的距离和长度，根据上图，可初始化为以下两个集合.

enter description here

注：图中表示节点名称，每个集合记录距离和路径，路径中的数字也表示节点名称，空间不够，不标单引号了.

以下步骤是不断更新两个集合的过程:

1.D 根据 U 更新当前最短路径到自己 (扩张过程)
2.U 根据新加入的节点更新自己 (松弛过程)
3. 迭代以上过程，直到所有路径遍历完

下面是各个迭代过程图示:

第二步
由前面的初始情况可知，与节点 1 直接相连接一共 3 个点，最近的点是 2. 把 1 与 2 的当前最短距离和路径加到集合 D 中，然后根据新的集合 D, 更新集合 U 的信息，更新的过程是:

1. 首先看看 2 节点的出边有那些，图中可以看到是：3,4
2. 节点 1 经过 2 节点到达上面两个节点与直接到达上面两个节点的距离比较，那个距离小就把信息更新到 U 集合中

第三步

上一次迭代完成后，集合 D 有 1,2 两个点，这两个点能到达的点是 6,3,4; 广度遍历路径得到 1 到 3 个节点的 3 最近，将节点 3 填到 D 中，然后更新 U.
此时的广度遍历就是从 1 开始，可以经过 2, 最终到达 3,4,6 其中一个节点的路径。具体包括:

a. 1->3
b. 1->6
c. 1->2->4

第四步
上一次迭代完成后，集合 D 有 1,2,3 三个点，这三个点能到达的点是 6,4; 广度遍历路径得到 1->3->6 这路径最短，将 6 更新到 D 后，更新 U.

第五步
上一次迭代完成后，集合 D 有 1,2,3,6 四个点，这四个点能到达的点是 5,4; 广度遍历路径得到 1->3->4 这路径最短，将 4 更新到 D 后，更新 U.

第六步
上一次迭代完成后，集合 D 有 1,2,3,6,4 五个点，这五个点能到达的点是 5; 广度遍历路径得到 1->3->6->5 这路径最短，将 4 更新到 D 后，更新 U.

最终，节点 1 到各个节点的最短路径及其长度都保存在集合 D 中.

注：迪杰斯特拉算法也可用于有向图最短路径查找，还有一个迪杰斯特拉的优化算法双向的迪杰斯特拉 , 改进的地方是从源点和终点同时广度优先搜索最短路径，总的来说双向的迪杰斯特拉比一般迪杰斯特拉更快.

最短路径快速算法 (SPFA)

描述:
SPFA 算法是西南交通大学段凡丁于 1994 年发表的，是一个用于求解有向带权图单源最短路径的改良的贝尔曼 - 福特算法。这一算法被认为在随机的稀疏图上表现出色，并且极其适合带有负边权的图。然而 SPFA 在最坏情况的时间复杂度与贝尔曼 - 福特算法相同，因此在非负边权的图中仍然最好使用戴克斯特拉算法。

原理:

最短路径快速算法图示

声明:
图片来源于: 最快最好用的 ——spfa 算法

弗洛伊德算法 (Floyd-Warshall)

描述:
是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包.

原理:
假设我有以下 graph:

演示graph

可以得到以下的邻接矩阵:

graph的邻接矩阵

该邻接矩阵 D 记录了有向图中，直接可达节点之间的距离.
下面就 1->3 的最短路径进行分析:

直接可达的路径权重为：9
比这短的路径可能是 1->X->3 (X 是除 1,3 外的所有点中的一个或多个)

假设 X 长度为 1,X 就是 2,4,5 其中一个值，1->X->3 的路径长度小于 9, 在矩阵中就是 D [1][x]+D [x][3]<9 (为了理解，假设矩阵从 1 开始编号).
D [1][2]+D [2][3]=5+3=8<9 更新最短路径长度
D[1][4]+D[4][3]=∞+∞=∞
D[1][5]+D[5][3]=∞+∞=∞

假设 X 长度是 2,X 就是考虑顺序在 2,4,5 中任取两个。有以下情况
D[1][2]+D[2][4]+D[4][3]=5+2+∞=∞
D[1][4]+D[4][2]+D[2][3]=∞+∞+3=∞
… 剩下组合省略

同理 X 长度为 3 时 , 有以下情况
D [1][2]+D [2][4]+D [4][5]+D [5][3]=2+2+1+2=7<8 更新
… 剩下组合省略

最后找到，1 到 3 的最短路径是，1->2->4->5->3, 最短距离为 8, 更新 D 矩阵得到:

更新后D矩阵

在这个新的 D 上继续算其他节点之间的最短路径。当然，这在程序中就是简单遍历，其实这里 X 的长度就是 1 到 3 中间需要经过多少节点。所有节点遍历完成，得到 graph 内两两节点之间的最短距离.

克鲁斯卡尔算法 (K.A)

描述:
一种用来查找最小生成树的算法，由 Joseph Kruskal 在 1956 年发表。用来解决同样问题的还有 Prim 算法和 Boruvka 算法等。三种算法都是贪心算法的应用。和 Boruvka 算法不同的地方是，Kruskal 算法在图中存在相同权值的边时也有效。

原理:

克鲁斯卡尔算法算法图示

把所有边选出来，并按照权重进行排序，从权重最小边开始选择，每次选择一条边，每次选择的边不能与原来的边构成环，知道选择的边包含所有的节点.

普里姆算法 (P.A)

描述:
图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。

原理:
从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

输入：一个加权连通图，其中顶点集合为V，边集合为E；
初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
重复下列操作，直到Vnew = V：
    在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则是V中没有加入Vnew的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
    将v加入集合Vnew中，将（u, v）加入集合Enew中；
输出：使用集合Vnew和Enew来描述所得到的最小生成树。

(1) 顶点 D 被任意选为起始点。顶点 A、B、E 和 F 通过单条边与 D 相连。A 是距离 D 最近的顶点，因此将 A 及对应边 AD 以高亮表示。

(2) 下一个顶点为距离 D 或 A 最近的顶点。B 距 D 为 9，距 A 为 7，E 为 15，F 为 6。因此，F 距 D 或 A 最近，因此将顶点 F 与相应边 DF 以高亮表示。

(3) 算法继续重复上面的步骤。距离 A 为 7 的顶点 B 被高亮表示。

(4) 在当前情况下，可以在 C、E 与 G 间进行选择。C 距 B 为 8，E 距 B 为 7，G 距 F 为 11。E 最近，因此将顶点 E 与相应边 BE 高亮表示。

(5) 这里，可供选择的顶点只有 C 和 G。C 距 E 为 5，G 距 E 为 9，故选取 C，并与边 EC 一同高亮表示。

(6) 顶点 G 是唯一剩下的顶点，它距 F 为 11，距 E 为 9，E 最近，故高亮表示 G 及相应边 EG。

(7) 现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为 39。

拓扑排序算法 (TSA)

描述:
对一个有向无环图 (Directed Acyclic Graph 简称 DAG) G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边 (u,v)∈E (G)，则 u 在线性序列中出现在 v 之前。

图形的顶点可以表示要执行的任务，并且边缘可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网 (Activity On Vertex network)，简称 AOV 网。

一个 AOV 网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。在 AOV 网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列 (Topological order)，由 AOV 网构造拓扑序列的过程叫做拓扑排序 (Topological sort)。AOV 网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

原理:
重复以下两个步骤，即可以得到拓扑序列.

1. 在有向图中任意选择一个无前驱的节点，并且作为当前的拓扑序列输出
2. 删除与前面选择的无前驱节点的所有关联的边

例子:

e拓扑排序算法例子

下面是得到其中一个拓扑序列的过程:

第一步:a 是无前驱的节点，选择
第二步:a 去掉后，b,c 为无前驱节点，任选一个，假设选择 c
第三步:a,c 去掉，只有 b 为无前驱节点，选择
第四步:a,c,b 去掉后，d,e 为无前驱节点，任选一个，假设选择 d
第五步:a,c,b,d 去掉后，e,f 为无前驱节点，任选一个，假设选择 f
第六步:a,c,b,d,f 去掉后，只有 e 为无前驱节点，选择
第六步:a,c,b,d,f,e 去掉后，只有 g 为无前驱节点，选择
第七步：所有节点遍历完成，得到拓扑序列

最终得到的拓扑序列为 a->c->b->d->f->e->g

关键路径算法 (CPA)

描述:
关键路径：在 AOE 网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径，一个 AOE 网中不一定只有一条关键路径，可能会有多条。
关键活动：关键路径上的活动（边）。
由于 AOE 网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。

原理:
现有无向有权图

无向有权图

根据这个 graph 定义四个值：前两个针对顶点，后两个针对边

(1) 事件最早开始时间：顶点最早发生的时间。
节点 B 只有 A 指向，所以其最早开始时间是 1, 对于节点 E, 需要等待 B,C,D 完成才能开始，缺一不可，所以其最早时间是 A->D->E:8

(2) 事件最晚开始时间：顶点最晚发生的时间，超出则会延误整个工期。
从右往左推，假设求得关键路径是 A->D->E->H->J:18, 以 H 为例，J->H:18-7=11 表示 J 最晚开始时间，超过这个时间 J 无法在 18 内完成.J->I->H 为例，18-5-1=12, 也是 H 的最迟开始时间，但是 11 比 12 靠前，所以 11 为 H 的最迟开始时间.

(3) 活动的最早开始时间：边最早发生时间。
求某一点的最早开始时间就是计算该节点前所有几点完成的时刻。比如 E 开始时，必须等待 A->C->E (4);A->B->E (4);A->D->E (8) 上的边必须先完成，取最长时间 8 为 E 的最早开始时间，比如上图各节点的最早开始时间如下:

最早发生时间

图中所标数字是每个节点的最早开始时间，假设源点 (A) 从 0 开始算起，汇点不需要时间处理。那么整个网络，最长的路径就是 18 (A->D->E->H->J). 各个点的最迟发生时间从后往前推，取较小的，比如 H 这个点 J->H (18-7=11),J->I->H (18-5-1=12), 就取 11.

(4) 活动的最晚开始时间：边最晚发生时间。不推迟工期的最晚开工时间。

以上数字均是时间点，从源点算起.
假设起点是 vo，则我们称从 v0 到 vi 的最长路径的长度为 vi 的最早发生时间，同时，vi 的最早发生时间也是所有以 vi 为尾的弧所表示的活动的最早开始时间，使用 e（i）表示活动 ai 最早发生时间，除此之外，我们还定义了一个活动最迟发生时间，使用 l（i）表示，不推迟工期的最晚开工时间。我们把 e（i）=l（i）的活动 ai 称为关键活动.

下面是算法的推理过程:
1. 构建 graph 网络
2. 从源点开始求 graph 的拓扑排序序列，如果序列个数小于 graph 节点个数，则 graph 存储环，程序退出，否则根据拓扑序列求各个节点的最早开始时间ve(j), 计算公式为:

1
2
3

$$
ve(j)=Max(ve(i)+Dur(i,j))
$$

3. 从汇点求 graph 的逆拓扑序列，然后根据该序列求各个节点的最晚开始时间vl(j), 计算公式为:

1
2
3

$$
vl(j)=Min(vl(i)-Dur(i,j))
$$

4. 如果 ve (j)=vl (j), 则 i-.j 是关键路径，否则不是.

广度优先搜索算法 (BFS)

描述:
又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS 是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用 open-closed 表。

原理:
优先搜索同以层次的节点，和优先往纵深搜索不同，过程如下图，代码过程不描述.

广度优先搜索算法

深度优先搜索算法 (DFS)

描述:
是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

原理:
过程如下图，代码过程不描述.

深度优先搜索算法

参考:
维基百科 - 图论
 百度百科 - 迪杰斯特拉算法
 最短路径问题 —Dijkstra 算法详解
 数据结构 — 拓扑排序详解
 傻子也能看懂的弗洛伊德算法
 算法学习记录 - 图 —— 应用之关键路径
 数据结构 ---- 关键路径详解