图（graph）

图的定义

>[!note ] 图（Graph）： > 由顶点的非空有限集合 V （由 n>0 个顶点组成）与边的集合 EE（顶点之间的关系）构成的结构。其形式化定义为 G=(V,E)。

• 顶点（Vertex）：图中的数据元素通常称为顶点，在下面的示意图中我们使用圆圈来表示顶点。

• 边（Edge）：图中两个数据元素之间的关联关系通常称为边，在下面的示意图中我们使用连接两个顶点之间的线段来表示边。边的形式化定义为：e=⟨u,v⟩，表示从 u 到 v 的一条边，其中 u 称为起始点，v 称为终止点。

• 子图（Sub Graph）：对于图 G=(V,E)与 G′=(V′,E′)，如果存在 V′⊆V，E′⊆E，则称图 G′ 是图 G 的一个子图。在下面的示意图中我们给出了一个图 G及其一个子图 G′。特别的，根据定义，G 也是其自身的子图。

如果将顶点看作节点，将边看作连接各个节点的引用（指针），我们就可以将图看作一种从链表拓展而来的数据结构。如图 9-1 所示，相较于线性关系（链表）和分治关系（树），网络关系（图）的自由度更高，因而更为复杂。

图的常见类型与术语

有向图与无向图

按照边是否有方向，我们可以将图分为两种类型：「无向图」和「有向图」。

• 无向图（Undirected Graph）：如果图中的每条边都没有指向性，则称为无向图。例如朋友关系图、路线图都是无向图。
• 有向图（Directed Graph）：如果图中的每条边都具有指向性，则称为有向图。例如流程图是有向图。

如果无向图中有 n 个顶点，则无向图中最多有 n×(n−1)/2 条边。而具有 n×(n−1)/2 条边的无向图称为 「完全无向图（Completed Undirected Graph）」。

如果有向图中有 n 个顶点，则有向图中最多有 n×(n−1)条弧。而具有 n×(n−1) 条弧的有向图称为 「完全有向图（Completed Directed Graph）」。

如下图所示，左侧为包含 44 个顶点的完全无向图，右侧为包含 44 个顶点的完全有向图。

下面介绍一下无向图和有向图中一个重要概念 「顶点的度」。

• 顶点的度（Degree）：与该顶点 vi​ 相关联的==边的条数==，记为 TD(vi)。

例如上图左侧的完全无向图中，顶点 v3 的度为 3。

而对于有向图，我们可以将顶点的度分为 「顶点的出度」 和 「顶点的入度」。

• 顶点的出度：以该顶点 vi​ 为出发点的边的条数，记为 OD(vi)。
• 顶点的入度：以该顶点 vi​ 为终止点的边的条数，记为 ID(vi)。
• 有向图中某顶点的度 = 该顶点的出度 + 该顶点的入度，即 TD(vi)=OD(vi)+ID(vi)。

例如上图右侧的完全有向图中，顶点 v3​ 的出度为 3，入度为 3，顶点 v3​ 的度为 3+3=6。

环形图和无环图

「路径」 是图中的一个重要概念，对于图 G=(V,E)，如果存在顶点序列 vi0,vi1,vi2,…,vim，使得 (vi0,vi1),(vi1,vi2),…,(vim−1,vim)∈E（即他们都是图 G 的边，对于有向图则是 ⟨vi0,vi1⟩,⟨vi1,vi2⟩,…,⟨vim−1,vim⟩∈E），则称该顶点序列为顶点 vi0 和顶点 vim之间的一条路径，其中 vi0是这条路径的起始点，vim​​ 是这条路径的终止点。

简单来说，如果顶点 vi0 可以通过一系列的顶点和边，到达顶点 vim，则称顶点 vi0vi0​​ 和顶点 vimvim​​ 之间有一条路径，其中经过的顶点序列则称为两个顶点之间的路径。

• 环（Circle）：如果一条路径的起始点和终止点相同（即 vi0==vim ），则称这条路径为「回路」或者「环」。
• 简单路径：顶点序列中顶点不重复出现的路径称为「简单路径」。

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

• 环形图（Circular Graph）：如果图中存在至少一条环路，则该图称为「环形图」。
• 无环图（Acyclic Graph）：如果图中不存在环路，则该图称为「无环图」。

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

如下图所示，分别为：无向无环图、无向环形图、有向无环图和有向环形图。其中有向环形图中的顶点 v1、v2​、v3​ 与相连的边构成了一个环。

环形图和无环图

连通图和非连通图

连通无向图和连通分量

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

• 连通无向图：在无向图中，如果图中任意两个顶点之间都是连通的，则称该图为连通无向图。
• 非连通无向图：在无向图中，如果图中至少存在一对顶点之间不存在任何路径，则该图称为非连通无向图。

如下图所示，

• 左侧图中 v1 与 v2​、v3​、v4​、v5​、v6​ 都是连通的，所以该图为连通无向图。
• 右侧图中 v1​ 与 v2​、v3​、v4​ 都是连通的，但是 v1​ 和 v5、v6 之间不存在任何路径，则该图为非连通无向图。

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

• 连通子图：如果无向图的子图是连通无向图，则该子图称为原图的连通子图。
• 极⼤连通⼦图：无向图中的一个连通子图，并且不存在包含它的更大的连通子图。
• 连通分量：无向图中的一个极大连通子图（不存在包含它的更大的连通子图）称为该图的连通分量。

例如上图中右侧的非连通无向图，其本身是非连通的。但顶点 v1​、v2​、v3​、v4​ 与其相连的边构成的子图是连通的，并且不存在包含它的更大的连通子图了，所以该子图是原图的一个连通分量。同理，顶点 v5​、v6​ 与其相连的边构成的子图也是原图的一个连通分量。

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

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

• 强连通有向图：如果图中任意两个顶点 vi​ 和 vj​，从 vi​ 到 vj​ 和从 vj​ 到 vi​ 都有路径，则称该图为强连通有向图。
• 非强连通有向图：如果图中至少存在一对顶点之间不存在任何路径，则该图称为非强连通有向图。

如下图所示，左侧图中任意两个顶点之间都有路径，则左侧图为强连通有向图。右侧图中顶点 v7​ 无法通过路径到达其他顶点，则右侧图为非强连通有向图。

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

• 强连通子图：如果有向图的子图是连通有向图，则该子图称为原图的强连通子图。
• 极⼤强连通⼦图：有向图中的一个强连通子图，并且不存在包含它的更大的强连通子图。
• 强连通分量：有向图中的一个极⼤强连通⼦图，称为该图的强连通分量。

例如上图中，右侧的非强连通有向图，其本身不是强连通的（顶点 v7​ 无法通过路径到达其他顶点）。但顶点 v1​、v2​、v3​、v4​、v5​、v6​ 与其相连的边构成的子图（即上图的左侧图）是强连通的，并且不存在包含它的更大的强连通子图了，所以该子图是原图的一个强连通分量（即上图中的左侧图是右侧图的强连通分量）。同理，顶点 v7​ 构成的子图也是原图的一个强连通分量

带权图

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

• 带权图：如果图的每条边都被赋以⼀个权值，这种图称为带权图。
• 网络：带权的连通无向图称为网络。

在下面的示意图中，我们给出了一个带权图的例子。

稠密图和稀疏图

根据图中边的稀疏程度，我们可以将图分为「稠密图」和「稀疏图」。这是一个模糊的概念，目前为止还没有给出一个量化的定义。

• 稠密图（Dense Graph）：一张图的边数远小于其点数的平方。
• 稀疏图（Sparse Graph）：一张图的边数接近其点数的平方。

其他常用术语

相邻

在无向图 G=(V,E) 中，若点 v 是边 e 的一个端点，则称 v 和 e 是 关联的 (incident) 或 相邻的 (adjacent)。对于两顶点 u 和 v，若存在边 (u,v)，则称 u 和 v 是 相邻的 (adjacent)。

简单图

自环 (loop)：对 E 中的边 e=(u,v)，若 u=v，则 e 被称作一个自环。

重边 (multiple edge)：若 E 中存在两个完全相同的元素（边）$e_1,e_2$，则它们被称作（一组）重边。

简单图 (simple graph)：若一个图中没有自环和重边，它被称为简单图。具有至少两个顶点的简单无向图中一定存在度相同的结点。（鸽巢原理）

如果一张图中有自环或重边，则称它为 多重图 (multigraph)。

>[!warning] 在无向图中 (u,v) 和 (v,u) 算一组重边，而在有向图中，$u\to v$ 和 v→u 不为重边。

>[!warning] 在题目中，如果没有特殊说明，是可以存在自环和重边的，在做题时需特殊考虑。

度数

与一个顶点 v 关联的==边的条数==称作该顶点的 度 (degree)，记作 d(v)。特别地，对于边 (v,v)，则每条这样的边要对 d(v) 产生 2 的贡献。

路径

途径 (walk)：途径是连接一连串顶点的边的序列，可以为有限或无限长度。

迹 (trail)：对于一条途径 w，若 e1,e2,…,ek 两两互不相同，则称 w 是一条迹。

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

回路 (circuit)：对于一条迹 w，若 v0=vk，则称 w 是一条回路。

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

图的表示

图的常用表示方式包括“邻接矩阵”和“邻接表”。以下使用无向图进行举例。

1.   邻接矩阵

设图的顶点数量为 n ，邻接矩阵（adjacency matrix）使用一个 n×n 大小的矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 1 或 0 表示两个顶点之间是否存在边。

如图 9-5 所示，设邻接矩阵为 M、顶点列表为 V ，那么矩阵元素 M[i,j]=1 表示顶点 V[i] 到顶点 V[j] 之间存在边，反之 M[i,j]=0 表示两顶点之间无边。

邻接矩阵具有以下特性。

• 在简单图中，顶点不能与自身相连，此时邻接矩阵主对角线元素没有意义。
• 对于无向图，两个方向的边等价，此时邻接矩阵关于主对角线对称。
• 将邻接矩阵的元素从 1 和 0 替换为权重，则可表示有权图。

使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 O(1) 。然而，矩阵的空间复杂度为 O(n^2) ，内存占用较多。

2.   邻接表

邻接表（adjacency list）使用 n 个链表来表示图，链表节点表示顶点。第 i 个链表对应顶点 i ，其中存储了该顶点的所有邻接顶点（与该顶点相连的顶点）。图 9-6 展示了一个使用邻接表存储的图的示例。

邻接表仅存储实际存在的边，而边的总数通常远小于 n^2 ，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。

观察图 9-6 ，邻接表结构与哈希表中的“链式地址”非常相似，因此我们也可以采用类似的方法来优化效率。比如当链表较长时，可以将链表转化为 AVL 树或红黑树，从而将时间效率从 O(n) 优化至 O(log⁡n) ；还可以把链表转换为哈希表，从而将时间复杂度降至 O(1)。

图的常见应用

如表 9-1 所示，许多现实系统可以用图来建模，相应的问题也可以约化为图计算问题。

表 9-1   现实生活中常见的图

应用	顶点	边	图计算问题
社交网络	用户	好友关系	潜在好友推荐
地铁线路	站点	站点间的连通性	最短路线推荐
太阳系	星体	星体间的万有引力作用	行星轨道计算