图 graph | 彩潭有鲤的札记

type

status

date

slug

summary

图的定义

图 (graph)是一个二元组：

是非空集，称为点集 (vertex set)，对于中的每个元素，称其为顶点 (vertex)或节点(node)，简称点

为各结点之间边的集合，称为边集 (edge set)

常用表示图。当都是有限集合时，称为有限图。当或是无限集合时，称为无限图。

子图（Sub Graph）：对于图与，如果存在，，则称图是图的一个子图。特别的，也是其自身的子图。

图的分类

无向图&有向图

有向图

若从顶点到的边有方向，则称这条边为有向边，也称为弧。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。

有向图和树的区别是，有向图不需要指定一个根节点，并且一个节点到另一个节点之间可能存在有好几条(或者没有)路径。有向图是由一个有限的称为顶点(vertices)的集合以及一个有限的连接没对顶点的有向弧或者有向边的集合构成的。

顶点的度：与该顶点相关联的边的条数，记为。对于有向图，可以将顶点的度分为 「顶点的出度」和 「顶点的入度」：箭头的起始端为出向边，箭头的末端为入向边。一个顶点出向边的个数称为出度，入向边的个数称为入度。

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有个顶点的有向完全图有条边：

无向图

若从顶点到的边没有方向，则称这条边为无向边。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。

无向图与有向图的区别如下：

无向图的边没有出向边和入向边的区分

无向图的顶点没有到达自己顶点位置的边

在无向图中，一个顶点的边的个数称之为度。

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图，含有个顶点的无向完全图有条边：

混合图

若中既有有向边，又有无向边，则为混合图。

赋权图

有时，图不仅需要表示顶点之间是否存在某种关系，还需要表示这一关系的具体细节。这时候需要在边上带一些数据信息，这些数据信息被称为权。权值可以具有某种具体意义，比如权值可以代表距离、时间以及价格等不同属性。

若的每条边都被赋予一个数作为该边的权，则称为赋权图。如果这些权都是正实数，就称为正权图。

环形图和无环图

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。形式化地说，一条有限途径是一个边的序列，使得存在一个顶点序列满足，其中。这样的途径可以简写为。通常来说，边的数量被称作这条途径的长度（如果边是带权的，长度通常指途径上的边权之和)。

迹 (trail)：对于一条途径，若两两互不相同，则称是一条迹

路径 (path)（又称 简单路径 (simple path))：对于一条迹，若其连接的点的序列中点两两不同，则称是一条路径

回路 (circuit)：对于一条迹，若，则称是一条回路

环/圈 (cycle)（又称简单回路/简单环 (simple circuit))：对于一条回路，若是点序列中唯一重复出现的点对，则称是一个环

根据图中是否有环，可以将图分为「环形图」和「无环图」

环形图（Circular Graph）：图中存在至少一条环路

无环图（Acyclic Graph）：图中不存在环路

特别的，在有向图中，如果不存在环路，则将该图称为「有向无环图（Directed Acyclic Graph）」，缩写为 DAG。因为有向无环图拥有为独特的拓扑结构，经常被用于处理动态规划、导航中寻求最短路径、数据压缩等多种算法场景。

有向环形图中的顶点、与相连的边构成了一个环

连通图和非连通图

连通无向图和连通分量

在无向图中，如果从顶点到顶点有路径，则称顶点和是连通的

连通无向图：在无向图中，图中任意两个顶点之间都是连通的

非连通无向图：在无向图中，图中至少存在一对顶点之间不存在任何路径

有些无向图可能不是连通无向图，但是其子图可能是连通的。这些子图称为原图的连通子图。而无向图的一个极大连通子图（不存在包含它的更大的连通子图）则称为该图的连通分量。

连通子图：如果无向图的子图是连通无向图，则该子图称为原图的连通子图。

连通分量：无向图中的一个极大连通子图（不存在包含它的更大的连通子图）称为该图的连通分量。

极大连通子图：无向图中的一个连通子图，并且不存在包含它的更大的连通子图。

强连通有向图和强连通分量

在有向图中，如果从顶点到顶点有路径，并且从顶点到顶点也有路径，则称顶点与是连通的。

强连通有向图：如果图中任意两个顶点和，从到和从到都有路径，则称该图为强连通有向图。

非强连通有向图：如果图中至少存在一对顶点之间不存在任何路径，则该图称为非强连通有向图。

与无向图类似，有向图的一个极大强连通子图称为该图的 强连通分量

强连通子图：如果有向图的子图是连通有向图，则该子图称为原图的强连通子图

强连通分量：有向图中的一个极大强连通子图，称为该图的强连通分量

极大强连通子图：有向图中的一个强连通子图，并且不存在包含它的更大的强连通子图

右侧的非强连通有向图，其本身不是强连通的（顶点无法通过路径到达其他顶点）。但顶点、、、、、与其相连的边构成的子图（左侧图）是强连通的，并且不存在包含它的更大的强连通子图了，所以该子图是原图的一个强连通分量。

图的存储

邻接矩阵

将有向图中所有的顶点编号为，邻接矩阵就是一个的矩阵，如果节点邻接于节点（即存在一条有向边从节点指向节点），则矩阵中第行第列的元素为，否则为：

对于带权有向图，在邻接矩阵表示的时候，顶点到顶点的就被权值所替换：

对于有向图的邻接矩阵而言，如果邻接矩阵是一个稀疏矩阵的话，存储的效率太低，即其空间利用率低。

边集数组

边集数组（Edgeset Array）：使用一个数组来存储存储顶点之间的邻接关系。数组中每个元素都包含一条边的起点、终点和边的权值val（如果是带权图）。

邻接表

邻接表（Adjacency List）：使用顺序存储和链式存储相结合的存储结构来存储图的顶点和边。其数据结构包括两个部分，其中一个部分是数组，主要用来存放顶点的数据信息，另一个部分是链表，用来存放边信息。

将有向图表示为一个数组或向量，其中每个元素对应有向图的一个节点，每个存储相应顶点中的数据，以及一个包含所有邻接于该顶点的顶点编号的链表：

邻接表只描述了顶点的出度，如果需要描述顶点的入度，则需要使用逆邻接表

链式前向星

链式前向星（Linked Forward Star）：也叫做静态邻接表，实质上就是使用静态链表实现的邻接表。链式前向星将边集数组和邻接表相结合，可以快速访问一个节点所有的邻接点，并且使用很少的额外空间

链式前向星采用了一种静态链表的存储方式，可以说是目前建图和遍历效率最高的存储方式。

链式前向星由两种数据结构组成：

特殊的边集数组：edges，其中 edges[i] 表示第 i 条边。edges[i].vj 表示第 i 条边的终止点，edges[i].val 表示第 i 条边的权值，edges[i].next 表示与第 i 条边同起始点的下一条边的存储位置。

头节点数组：head，其中 head[i] 存储以顶点 i 为起始点的第 1 条边在数组 edges 中的下标。

十字链表

首先，十字链表中含有两种结构，一个是顶点，一个是节点，顶点的结构如下图所示：

节点的结构则如下图所示：

那么，将一个有向图转化为十字链表的过程如下图所示：

邻接多重表

在邻接多重表中，其节点的结构如下图所示：

那么，将一个无向图转化为邻接多重表的过程如下图所示：

图的遍历

邻接表节点的定义：

构建邻接表：

信息文件内容如下：

深度优先遍历

广度优先遍历

拓扑排序

拓扑排序（Topological Sorting）：一种对有向无环图（DAG）的所有顶点进行线性排序的方法，使得图中任意一点u和v，如果存在有向边 <u,v>，则 u 必须在 v 之前出现。对有向图进行拓扑排序产生的线性序列称为满足拓扑次序的序列，简称拓扑排序。

图的拓扑排序是针对有向无环图（DAG）来说的，无向图和有向有环图没有拓扑排序，或者说不存在拓扑排序。

如上图中的有向无环图（DAG）所示，是该图的一个拓扑序列。与此同时，也是该图的一个拓扑序列。也就是说，对于一个有向无环图来说，拓扑序列可能不止一个。

拓扑排序有两种实现方法，分别是「Kahn 算法」和「DFS 深度优先搜索算法」。

Kahn 算法的基本思想：

不断找寻有向图中入度为 0 的顶点，将其输出。

然后删除入度为 0 的顶点和从该顶点出发的有向边。

重复上述操作直到图为空，或者找不到入度为 0 的节点为止。

实现步骤

使用数组 indegrees 用于记录图中各个顶点的入度。

维护一个入度为 0 的顶点集合 S（可使用栈、队列、优先队列）。

每次从集合中选择任何一个没有前驱（即入度为 0）的顶点 u，将其输出到拓扑序列 order 中。

从图中删除该顶点 u，并且删除从该顶点出发的有向边 <u,v>（也就是把该顶点可达的顶点入度都减 1）。如果删除该边后顶点 v 的入度变为 0，则将顶点 v 放入集合 S 中。

重复上述过程，直到集合 S 为空，或者图中还有顶点未被访问（说明一定存在环路，无法形成拓扑序列）。

如果不存在环路，则 order 中顶点的顺序就是拓扑排序的结果。

基于 DFS 实现拓扑排序算法的基本思想：

对于一个顶点 u，深度优先遍历从该顶点出发的有向边 <u,v>。如果从该顶点 u 出发的所有相邻顶点 v 都已经搜索完毕，则回溯到顶点 u 时，该顶点 u 应该位于其所有相邻顶点 v 的前面（拓扑序列中）。

这样一来，当我们对每个顶点进行深度优先搜索，在回溯到该顶点时将其放入栈中，则最终从栈顶到栈底的序列就是一种拓扑排序。

实现步骤

使用集合 visited 用于记录当前顶点是否被访问过，避免重复访问。

使用集合 onStack 用于记录同一次深度优先搜索时，当前顶点是否被访问过。如果当前顶点被访问过，则说明图中存在环路，无法构成拓扑序列。

使用布尔变量 hasCycle 用于判断图中是否存在环。

从任意一个未被访问的顶点 u 出发。

如果顶点 u 在同一次深度优先搜索时被访问过，则说明存在环。
如果当前顶点被访问或者有环时，则无需再继续遍历，直接返回。

将顶点 u 标记为被访问过，并在本次深度优先搜索中标记为访问过。然后深度优先遍历从顶点 u 出发的有向边 <u,v>。

当顶点 u 的所有相邻顶点 v 都被访问后，回溯前记录当前节点 u（将当前节点 u 输出到拓扑序列 order 中）。

取消本次深度优先搜索时，顶点 u 的访问标记。

对其他未被访问的顶点重复 4∼7 步过程，直到所有节点都遍历完，或者出现环。

如果不存在环路，则将 order 逆序排序后，顶点的顺序就是拓扑排序的结果。

图的最短路径算法

不带权值的最短路径

对于不带权值的最短路径而言，我们可以采用广度优先遍历的方法，同时在遍历的过程中记录其上一个节点即可。如下图所示，我们找寻从 A 顶点到 H 顶点的最短路径：

从上图中可以看到，在广度优先遍历到第 2 层时，已经找到了 H 节点，此时直接返回即可。

Dijkstra算法

迪杰斯特拉(Dijkstra)算法是典型的单源最短路径算法，用于计算一个节点到其它所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

算法思想：设 G=(V,E) 是一个带权有向图，把图中顶点集合 V 分成两组，第一组为已求出最短路径的顶点集合(用 S 表示，初始时 S 中只有一个源点，以后每求得一条最短路径，就将加入到集合 S 中，直到全部顶点都加入到 S 中，算法就结束了)，第二组为其余未确定最短路径的顶点集合(用 U 表示)，按最短路径长度的递增次序依次把第二组的顶点加入 S 中。在加入的过程中，总保持从源点 v 到 S 中各顶点的最短路径长度不大于从源点 v 到 U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S 中的顶点的距离就是从 v 到此顶点的最短路径长度，U 中的顶点的距离，就是从 v 到此顶点只包括 S 中的顶点为中间顶点的当前最短路径长度。

Dijkstra 算法其实是贪心算法在单源最短路径问题上的典型应用场景。

其算法步骤如下：

初始时，S 只包含源点，即 S={v}，v 的距离为 0。U 包含除 v 外的其它顶点，即 U={其余顶点}，若 v 与 U 中顶点 u 有边，则 <u,v> 正常有权值，若 u 不是 v 的出边邻接点，则 <u,v> 权值为 ∞；

从 U 中选取一个距离 v 最小的顶点 k，把顶点 k 加入到 S 中(该选定的距离就是 v 到 k 的最短路径长度)；

以 k 为新的中间点，修改 U 中各顶点的距离，若从源点 v 到顶点 u 的距离(经过顶点 k)比原来距离(不经过顶点 k)短，则修改顶点 u 的距离值，修改后的距离值的顶点 k 的距离加上边上的权；

重复步骤 2 和 3 直到所有顶点都包含在 S 中；

例如，现在对于如下图所示的有权无向图：

开始时，以 A 点为源点，此时集合 S 中只有 A，且最短路径为 A->A=0，然后以 A 为中间点，从 A 开始找最短路径。而集合 U 则包含 B、C、D、E、F，其中，A->B=6，A->C=3，而到其余顶点的距离则为 ∞，可以看到 A->C=3 的权值最小：

于是将顶点 C 加入到集合 S 中，并以顶点 C 作为新的源点，此时集合 U 中包含 B、D、E、F，由于 A->C->B=3+2=5，其值要小于 A->B=6，因此更新顶点 B 的路径，同样地 A->C->D=3+3=6，A->C->E=3+4=7，A->C->D=3+3=6，可以看到，A->C->B 的权值最小：

选取顶点 B 加入到集合 S 中，然后将顶点 B 作为新的源点，此时集合 U 中包含 D、E、F，由于 A->C->B->D=3+2+5=10，其值要大于上一步中的 A->C->D=3+3=6，因此 D 值不变，而顶点 B 到顶点 E、F 的距离为 ∞，因此也不更新。可以看到 A->C->D 的权值最小：

选取顶点 D 加入到集合 S 中，并以顶点 D 作为新的源点，此时集合 U 中包含 E 和 F，由于 A->C->D->E=3+3+2=8，大于第二步中的 A->C->E=3+4=7，而 A->C->D->F=3+3+3=9。可以看到，A->C->E 的权值最小：

选取顶点 E 加入到集合 S 中，并将顶点 E 作为新的源点，此时集合 U 中仅剩下顶点 F，由于 A->C->E->F=3+4+5=12，大于第四步中的 A->C->D->F=3+3+3=9，可以看到 A->C->D->F 的权值最小：

将顶点 F 加入到集合 S 中，此时集合 U 已空，查找完毕：

注意，该算法无法处理负权变，有可能无法得到最短的路径，比如对于如下图所示的有权无向图：

开始时，选取 A 顶点作为源点，由于 A->B=4，A->C=6，所以选择顶点 B 加入到集合 S 中，但是 A->C->B=6-3=3，其值要小于 A->B=4，所以开始选取的 A->B 并非为最短路径。

Dijkstra算法优化

因为在每一次都需要遍历 U 集合，找寻权值最小的点，因此，可以使用小根堆数据结构来进行优化，其代码实现如下：

Floyd算法

Floyd 算法又称为插点法，是一种利用动态规划算法的思想寻找给定的加权图中多源点之间最短路径的算法，其主要思想是：

从第 1 个点到第 n 个点依次加入图中，每个点加入后进行试探是否有路径长度被更改。具体方法为遍历图中每一个点(通过 i,j 双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，更新两点(i,j)的距离。

重复上述直到最后插点试探完成。

其中更新距离的状态转移方程为:

其中的意思可以理解为到的最短路径。为到的最短路径，为到的最短路径。

例如，对于如下图所示的带权无向图：

将其转化为邻接矩阵后如下所示，其中 INF 表示两点间没有直接相连的路径：

首先，我们选择加入 A 顶点，那么就需要遍历邻接矩阵，看其他点经过 A 顶点中转后的距离能否小于其直接到达另一个点的距离。注意，下图中的绿色部分是不需要进行变化的，一方面对角线元素是自己到自己的距离，而除去对角线元素的其它绿色部分是 A 顶点无需中转而直接到达其它顶点的最短路径，所以，需要观察的只有其中的橙色部分：

那么对于以顶点 B 为起点的路径而言，如果存在更短的路径，则进行更新：

B->A->C=6+3=9 > B->C=2

B->A->D=INF > B->D=5

B->A->E=INF = B->E=INF

B->A->F=INF = B->F=INF

因此上述邻接矩阵中 B 行是无需发生任何改变的。然后以同样的方式观察其余的 C、D、E、F 顶点，完成后，再加入 B 顶点，以 B 顶点为中转顶点，重复上述过程即可。

所以，Floyd算法的时间复杂度为，但是相比于 Dijkstra 算法而言，它可以用来计算负权值的最短路径。