图的基本概念与表示

图把现实问题抽象成“对象”和“关系”。对象构成顶点集 $V$，关系构成边集 $E$，记作

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

后续 BFS、DFS、最短路、生成树和网络流都建立在这些基础概念上。

1. 无向图与有向图

无向边 $\{u,v\}$ 不区分方向，$\{u,v\}=\{v,u\}$；有向边 $(u,v)$ 从 $u$ 指向 $v$，通常与 $(v,u)$ 不同。

无向图中，顶点 $v$ 的度 $\deg(v)$ 是关联边数，并满足握手定理：

$$\sum_{v\in V}\deg(v)=2|E|.$$

因此奇数度顶点的数量一定为偶数。

有向图分别定义入度 $\deg^-(v)$ 和出度 $\deg^+(v)$，且

$$\sum_v\deg^-(v)=\sum_v\deg^+(v)=|E|.$$

2. 路径、环与可达

路径是顶点序列

$$\langle v_0,v_1,\ldots,v_k\rangle,$$

其中相邻顶点之间都有对应边。若顶点不重复，称简单路径；若 $v_0=v_k$ 且至少含一条边，构成环。

从 $u$ 存在路径到 $v$，称 $v$ 从 $u$ 可达。有向图中的可达有方向，不具有对称性。

3. 连通分量与强连通分量

无向图中，任意两点互相可达时图连通；极大的连通顶点集合叫连通分量。

有向图中，“忽略方向后连通”叫弱连通；只有任意两点都能沿有向路径相互到达，才叫强连通。极大的强连通顶点集合是强连通分量。

4. 树与森林

无向树等价地满足多组性质：

• 连通且无环；
• 有 $|V|-1$ 条边且连通；
• 有 $|V|-1$ 条边且无环；
• 任意两点间恰有一条简单路径。

无环无向图称森林，每个连通分量都是一棵树。给一棵树增加任意一条非树边会产生唯一环；删除任意一条树边会使其不连通。

5. 一笔画与欧拉道路

欧拉道路要求每条边恰好经过一次，不要求每个顶点只出现一次。

对忽略孤立点后连通的无向图：

• 所有顶点度数为偶数时，存在欧拉回路；
• 恰有两个奇度顶点时，存在从一个奇度点到另一个奇度点的欧拉道路；
• 其他情况不存在。

不要把它与经过每个顶点一次的 Hamilton 路混淆，后者困难得多。

6. 邻接矩阵

用 $|V|\times|V|$ 矩阵 $A$ 表示边：无权图中 $A[u][v]$ 表示是否有边，带权图中存边权或无穷。

• 空间：$O(V^2)$；
• 判断某条边是否存在：$O(1)$；
• 枚举一个顶点的所有邻居：$O(V)$。

适合稠密图或频繁查询任意点对关系。

7. 邻接表

每个顶点保存一个邻居列表。

• 空间：$O(V+E)$；
• 枚举 $u$ 的邻居：$O(\deg(u))$；
• 朴素判断特定边：最坏 $O(\deg(u))$。

无向边通常在两个端点的列表中各存一次，但复杂度中的 $E$ 仍指原图边数。大多数稀疏图算法都以邻接表为默认表示。

8. 复杂度里的 $V$ 与 $E$

写 $O(V+E)$ 时，$V$ 和 $E$ 分别简写 $|V|$、$|E|$。这是读取整张邻接表所需的线性时间。若用邻接矩阵，同一个 BFS 可能变成 $O(V^2)$，所以分析算法时必须同时说明图的存储方式。