图的概念与存储

图是由顶点和边组成的结构，用来刻画对象以及对象之间的联系。形式化地，一个图可以表示为二元组

$$G=(V,E),$$

其中 $V$ 是有限的顶点集，$E$ 是顶点对的集合。在无向图中，边为无序对 $\{u,v\}$；在有向图中，边为有序对 $(u,v)$。

在入门学习中，我们主要讨论简单图，即不包含重边和自环的图。重边是指在同一对顶点之间出现多条边；自环是指边的两个端点相同。限制在简单图的范围内，可以避免不必要的冗余，使得许多基本性质更加清晰。

度数

顶点的度数描述了它与多少条边相连。在无向图中，顶点 $v$ 的度数 $\mathrm{deg}(v)$ 定义为与 $v$ 相连的边的条数。在有向图中，需要区分入度 ${\mathrm{deg}}^{-}(v)$（进入 $v$ 的边数）和出度 ${\mathrm{deg}}^{+}(v)$（从 $v$ 出发的边数）。度数直接反映了顶点在图中的连接情况。

途径、路径与环

图的结构不仅体现在单条边上，还体现在由边串联而成的顶点序列中。

途径（walk）是顶点序列 $v_0,v_1,\dots ,v_k$，其中每一对相邻顶点 $(v_{i-1},v_i)$ 都在边集 $E$ 中。途径允许顶点和边重复。而 路径（path）是不重复顶点的途径（除非首尾相同）。环（cycle）是首尾相同且中间顶点不重复的路径。

连通性

一个图整体的紧密程度由连通性刻画。在无向图中，如果任意两个顶点之间都存在一条路径，则称该图为连通图。否则，图会自然地分解为若干连通分量，它们内部各自连通，但彼此之间互不相达。

在有向图中，对应的概念是强连通性。若任意两点之间都存在方向一致的往返路径，则称该图为强连通图。

图的存储方式

为了在计算机中操作图，需要将其表示为适合的数据结构。常见的方式有邻接矩阵与邻接表。

邻接矩阵

设图有 $n$ 个顶点，则用一个 $n\times n$ 矩阵 $A$ 表示。元素 $A_{i,j}$ 表示顶点 $i$ 与顶点 $j$ 之间的边及其权值。如果边不存在，则记为 $0$ 或 $\mathrm{\infty }$。邻接矩阵支持 $O(1)$ 时间判断两点是否相连，但在稀疏图中空间利用率较低。

邻接表

为每个顶点维护一个邻居集合，只存储实际存在的边。邻接表在稀疏图上更为高效，遍历邻居时也避免了多余开销。但它无法像矩阵那样在常数时间内判断两点是否相连。

邻接矩阵与邻接表各有优缺点，实际使用时往往根据图的稠密程度来选择。