1. 图章引论¶
1.1. 图的术语与实现¶
图提供了数据结构灵活性的极致。图由一组节点和一组边组成，其中一条边连接两个节点。树和列表可以被视为图的特例。
图用于对现实世界系统和抽象问题建模， 是许多应用中的首选数据结构。 以下是图通常用于解决的问题类型的一小部分示例。
对计算机和通信网络中的连接进行建模。
将抽象地图表示为一组位置及位置之间的距离。 这可用于计算位置之间的最短路线， 例如 GPS 路由查找器中的路线。
对运输网络中的流量容量进行建模， 以找出哪些链路造成瓶颈。
从起始状态找到通往目标状态的路径。 这是人工智能应用和计算机游戏程序中 建模问题的常用方法。
对计算机算法进行建模， 以展示程序状态之间的转换。
在复杂活动（如建造大型建筑）中， 找到完成子任务的可接受顺序。
对关系进行建模， 如家族树、商业或军事组织以及科学分类。
本模块的其余部分涵盖一些基本的图术语。 以下模块将描述图的基本表示法、提供参考实现， 并涵盖核心图算法，包括遍历、拓扑排序、 最短路径算法和最小代价生成树算法。 除了这些算法本身有用和有趣之外， 它们还说明了整个课程中介绍的许多其他数据结构的使用。
一个 图 \(\mathbf{G} = (\mathbf{V}, \mathbf{E})\) 由 一组 顶点 \(\mathbf{V}\) 和 一组 边 \(\mathbf{E}\) 组成， 使得 \(\mathbf{E}\) 中的每条边 都是 \(\mathbf{V}\) 中一对顶点之间的连接。 [1] 顶点的数量写作 \(|\mathbf{V}|\)， 边的数量写作 \(|\mathbf{E}|\)。 \(|\mathbf{E}|\) 的范围可以从零到最大 \(|\mathbf{V}|^2 - |\mathbf{V}|\)。
边不具有方向的图称为 无向图， 如下图的 (a) 部分所示。 边从一个顶点指向另一个顶点的图 （如 (b)）称为 有向图 或 有向图。 顶点关联标签的图（如 (c)）称为 标记图。 每条边可能关联一个代价或 权值。 边具有权值的图（如 (c)）称为 加权图。
连接顶点 \(a\) 和 \(b\) 的边写作 \((a, b)\)。 这样的边称为与顶点 \(a\) 和 \(b\) 关联。 这两个顶点称为 相邻。 如果边从 \(a\) 指向 \(b\)， 则我们说 \(a\) 邻接到 \(b\) ， \(b\) 由 \(a\) 邻接而来。 顶点的 度 是与其关联的边数。 例如，下面的顶点 \(e\) 的度为三。
在有向图中，顶点的 出度 是由它邻接出去的 邻居数（或从它发出的边数）， 而 入度 是邻接到它的邻居数 （或进入它的边数）。 在上面的 (c) 中，顶点 1 的入度为二，出度为一。
顶点序列 \(v_1, v_2, ..., v_n\) 构成长度为 \(n-1\) 的 路径， 条件是存在从 \(v_i\) 到 \(v_{i+1}\) 的边 （\(1 \leq i < n\)）。 如果路径上的所有顶点都不同， 则路径是 简单路径。 路径的 长度 是它包含的边数。 环 是长度为三或更大的路径， 连接某个顶点 \(v_1\) 到自身。 如果路径是简单的（除了第一个和最后一个顶点相同）， 则环是 简单环。
如果任何顶点之间至少存在一条路径， 则无向图是 连通图。 无向图的极大连通子图称为 连通分量。 例如，此图显示了一个有三个连通分量的无向图。
边相对较少的图称为 稀疏图 ，而边较多的图称为 稠密图 。包含所有可能边的图被称为 完全图 。 子图 \(\mathbf{S}\) 是通过从图 \(\mathbf{G}\) 中选择 \(\mathbf{G}\) 的顶点子集 \(\mathbf{V}_s\) 和 \(\mathbf{G}\) 的边子集 \(\mathbf{E}_s\) 形成的，使得对于每条边 \(e \in \mathbf{E}_s\) ， \(e\) 的两个顶点都在 \(\mathbf{V}_s\) 中。 \(V\) 的任何子图，若其中所有顶点都与该子图中的其他所有顶点相连，则称为 团 。
没有环的图称为 无环图。 因此，没有环的有向图称为 有向无环图 或 DAG。
自由树 是一个连通的、无向的、 没有简单环的图。 等价定义是自由树是连通的且有 \(|\mathbf{V}| - 1\) 条边。
1.1.1. 图的表示法¶
有两种常用的图表示方法。 图的 邻接矩阵 是一个 \(|\mathbf{V}| \times |\mathbf{V}|\) 的数组。 我们通常将顶点标记为从 \(v_0\) 到 \(v_{|\mathbf{V}|-1}\)。 邻接矩阵的第 \(i\) 行包含顶点 \(v_i\) 的条目。 第 \(i\) 行的第 \(j\) 列在从 \(v_i\) 到 \(v_j\) 存在边时被标记，否则不被标记。 邻接矩阵的空间需求为 \(\Theta(|\mathbf{V}|^2)\)。
第二种常用的图表示是 邻接表。 邻接表是链表的数组。 数组长度为 \(|\mathbf{V}|\)， 位置 \(i\) 存储指向顶点 \(v_i\) 的边链表的指针。 此链表通过与顶点 \(v_i\) 相邻的顶点来表示边。
以下是在有向图上两种表示法的示例。 顶点 0 的条目存储 1 和 4， 因为图中有两条从顶点 0 出去的边， 一条到顶点 1，一条到顶点 4。 顶点 2 的列表存储顶点 4 的条目， 因为有一条从顶点 2 到顶点 4 的边， 但没有顶点 3 的条目， 因为这条边是进入顶点 2 而不是从它出去的。
邻接矩阵和邻接表都可以用于存储有向图或无向图。 连接顶点 \(u\) 和 \(v\) 的无向图的每条边 由两条有向边表示：一条从 \(u\) 到 \(v\)， 一条从 \(v\) 到 \(u\)。 以下是在无向图上两种表示法的示例。 我们看到邻接矩阵和邻接表中的边条目 都有两倍多。 例如，对于无向图，顶点 2 的列表存储 顶点 3 和顶点 4 的条目。
邻接表的空间需求取决于图中的边数和顶点数。 每个顶点必须有一个数组条目 （即使该顶点不与任何其他顶点相邻， 因此其链表上没有元素）， 每条边必须出现在其中一条列表上。 因此，成本为 \(\Theta(|\mathbf{V}| + |\mathbf{E}|)\)。
有时我们想在每条边上存储权值或距离， 如图 18.1.1 (c) 所示。 这在邻接矩阵中很容易实现， 我们只需在矩阵中存储权值。 在图 18.1.7 和 18.1.8 中， 我们仅在每个位置存储值 "1" 以表明边存在。 这本可以使用单个位来完成， 但由于位操作在大多数编程语言中通常很复杂， 实现可能在每个矩阵位置存储一个字节或整数。 对于加权图，我们需要在矩阵的每个位置 存储足够的空间来表示权值， 通常是一个整数。
邻接表需要在每条边上显式存储一个权值。 在下面显示的邻接表中， 每个链表节点存储两个值。 第一个是关联边末端邻居的索引。 第二个是权值。 与邻接矩阵一样，这个值需要空间来表示， 通常是一个整数。
哪种图表示更节省空间取决于图中的边数。 邻接表仅存储实际出现在图中的边的信息， 而邻接矩阵为每条潜在边（无论是否存在）都需要空间。 然而，邻接表不需要指针的额外开销， 这可能是一个相当大的成本， 特别是如果边存储的唯一信息是 指示其存在的一位。 随着图变得更稠密，邻接矩阵变得相对更节省空间。 稀疏图可能使用邻接表表示更节省空间。
邻接矩阵通常比使用邻接表 导致算法具有更高的渐近成本。 原因是图算法通常需要访问每个顶点的每个邻居。 使用邻接表，只检查连接顶点与其邻居的实际边。 但是，邻接矩阵必须查看其 \(|\mathbf{V}|\) 条潜在边中的每一条， 在算法原本只需要 \(\Theta(|\mathbf{V}| + |\mathbf{E}|)\) 时间时， 产生 \(\Theta(|\mathbf{V}^2|)\) 的总时间成本。 当图是稀疏的时，这是一个相当大的劣势， 但当图接近完全时则不是。
