图论入门

图论概述

在本模块中，我们将学习图的两种表示方法以及基于这些表示的基本算法。

从数学角度讲，一个（有向）图是一个二元组 $G = (V, E)$，其中 $V$ 是顶点的集合，$E$ 是顶点有序对的集合，称为边。一条边 $(i,j)$ 从顶点 $i$ 指向顶点 $j$；$i$ 称为边的起点，$j$ 称为边的终点。图 $G$ 中的一条路径是一系列顶点 $v_0, \ldots, v_k$，使得对于每个 $i \in \{1, \ldots, k\}$，边 $(v_{i-1}, v_i)$ 属于 $E$。如果这条路径还满足边 $(v_k, v_0) \in E$，则称其为环路。若一条路径（或环路）的所有顶点互不相同，则称其为简单路径（或简单环路）。如果存在从某个顶点 $v_i$ 到另一个顶点 $v_j$ 的路径，则称 $v_j$ 可由 $v_i$ 到达。下图展示了一个包含十二个顶点的图：

一个包含十二个顶点的图。顶点用编号的圆圈表示，边用带箭头的曲线表示，箭头方向从起点指向终点。

图的应用

由于图能够建模众多现象，因此其应用极为广泛。许多应用是显而易见的。例如，计算机网络可以建模为图，其中顶点代表计算机，边代表计算机之间的（有向）通信链路。城市道路系统也可以建模为图，顶点表示路口，边表示连接相邻路口的道路。

更不明显的例子出现在我们意识到图可以表示集合中任意两个元素之间的成对关系时。例如，在大学环境中，我们可以构建一个课程时间冲突图：顶点代表学校开设的课程，当且仅当至少有一名学生同时选修课程 $i$ 和课程 $j$ 时，边 $(i,j)$ 存在。因此，一条边表示课程 $i$ 的考试不应与课程 $j$ 的考试安排在同一时间。

在本节中，我们用 $n$ 表示图 $G$ 的顶点数量，用 $m$ 表示边的数量。即 $n = |V|$，$m = |E|$。此外，我们假设 $V = \{0, \ldots, n-1\}$。任何需要与顶点关联的数据都可以存储在一个长度为 $n$ 的数组中。

图上的操作

常见的图操作包括：

• addEdge(i,j)：将边 $(i,j)$ 添加到 $E$ 中。
• removeEdge(i,j)：从 $E$ 中移除边 $(i,j)$。
• hasEdge(i,j)：检查边 $(i,j)$ 是否属于 $E$。
• outEdges(i)：返回所有满足 $(i,j) \in E$ 的整数 $j$ 的列表。
• inEdges(i)：返回所有满足 $(j,i) \in E$ 的整数 $j$ 的列表。

需要注意的是，这些操作并不难高效实现。例如，前三个操作可以通过使用 USet 直接实现，利用哈希表可在期望常数时间内完成。后两个操作也可以通过为每个顶点维护一个邻接顶点列表，在常数时间内完成。

然而，不同应用场景对这些操作有不同的性能要求，理想情况下，我们可以选择最简单但能满足所有需求的实现方式。因此，我们将讨论图表示的两大类方法。