17.1. 章引论：图¶
17.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\) 条边。
17.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}|)\)。
有时我们想在每条边上存储权值或距离，如图 17.1.1 (c) 所示。这在邻接矩阵中很容易实现，我们只需在矩阵中存储权值。在图 17.1.7 和 17.1.8 中，我们仅在每个位置存储值 "1" 以表明边存在。这本可以使用单个位来完成，但由于位操作在大多数编程语言中通常很复杂，实现可能在每个矩阵位置存储一个字节或整数。对于加权图，我们需要在矩阵的每个位置存储足够的空间来表示权值，通常是一个整数。
邻接表需要在每条边上显式存储一个权值。在下面显示的邻接表中，每个链表节点存储两个值。第一个是关联边末端邻居的索引。第二个是权值。与邻接矩阵一样，这个值需要空间来表示，通常是一个整数。
哪种图表示更节省空间取决于图中的边数。邻接表仅存储实际出现在图中的边的信息，而邻接矩阵为每条潜在边（无论是否存在）都需要空间。然而，邻接矩阵不需要指针的额外开销，这可能是一个相当大的成本，特别是如果边存储的唯一信息是指示其存在的一位。随着图变得更稠密，邻接矩阵变得相对更节省空间。稀疏图可能使用邻接表表示更节省空间。
邻接矩阵通常比使用邻接表导致算法具有更高的渐近成本。原因是图算法通常需要访问每个顶点的每个邻居。使用邻接表，只检查连接顶点与其邻居的实际边。但是，邻接矩阵必须查看其 \(|\mathbf{V}|\) 条潜在边中的每一条，在算法原本只需要 \(\Theta(|\mathbf{V}| + |\mathbf{E}|)\) 时间时，产生 \(\Theta(|\mathbf{V}^2|)\) 的总时间成本。当图是稀疏的时，这是一个相当大的劣势，但当图接近完全时则不是。
