Appearance
图的基本概念
为什么需要图的基本概念
前面学过的线性表和树都是特殊的数据结构——线性表是一对一关系，树是一对多关系，而图是多对多关系的通用表示。现实中大量问题都建模为图：社交网络、交通路线、课程先修关系、网页链接等。
408 考研中，图是数据结构的重点章节，涉及概念多、公式多、算法多。掌握基本概念是理解图的存储结构（邻接矩阵、邻接表）和图算法（遍历、最短路径、最小生成树、拓扑排序）的前提。
核心思想
图 G 由顶点集 V 和边集 E 组成，记为 G = (V, E)。
- 简单图：不存在重复边，不存在顶点到自身的边。408 考研中若无特别说明，讨论的都是简单图。
- 多重图：允许两个顶点之间存在多条边，或存在自环。
图的核心特点：
- 顶点之间的关系是任意的：任意两个顶点之间都可能存在边
- 边可以有方向：有向图中边用弧表示，有弧尾和弧头之分
- 边可以带权：带权图（网）中每条边附带一个权值，表示距离、代价等
交互可视化
通过下方的交互动画，你可以逐步观察图的基本概念的执行过程：
操作详解
有向图与无向图
无向图：边没有方向，用 (v, w) 表示，(v, w) 与 (w, v) 等价。
有向图：边有方向（称为弧），用 <v, w> 表示从 v 到 w 的弧，v 是弧尾，w 是弧头。<v, w> ≠ <w, v>。
| 概念 | 无向图 | 有向图 |
|---|---|---|
| 边的表示 | (v, w) | <v, w> |
| 边数上限（简单图） | n(n-1)/2 | n(n-1) |
| 完全图 | 每对顶点都有边 | 每对顶点都有方向相反的两条弧 |
| 完全图边数 | n(n-1)/2 | n(n-1) |
完全图：边数达到上限的简单图。无向完全图有 n(n-1)/2 条边，有向完全图有 n(n-1) 条弧。
子图：设 G = (V, E)，G' = (V', E')，若 V' ⊆ V 且 E' ⊆ E，则 G' 是 G 的子图。注意：V 的任意子集和 E 的任意子集不一定能构成子图，因为 E' 中的边所关联的顶点必须在 V' 中。
生成子图：V' = V 的子图，即包含全部顶点的子图。
度
无向图中：顶点 v 的度 TD(v) = 与 v 关联的边数。
有向图中：
- 入度 ID(v)：以 v 为弧头的弧的数量
- 出度 OD(v)：以 v 为弧尾的弧的数量
- 度 TD(v) = ID(v) + OD(v)
⭐ 握手定理（度与边数的关系）：
| 图类型 | 公式 | 说明 |
|---|---|---|
| 无向图 | ∑TD(v) = 2e | 每条边贡献 2 度 |
| 有向图 | ∑ID(v) = ∑OD(v) = e | 每条弧贡献 1 入度 + 1 出度 |
其中 e 为边（弧）的数量。该公式是选择题中求边数或度数的核心工具。
路径与回路
路径：从顶点 v 到顶点 w 的顶点序列，路径上边的数目称为路径长度。
简单路径：路径中顶点不重复出现的路径。
回路（环）：起点和终点相同的路径。简单回路：除起点和终点外，其余顶点不重复。
距离：从 v 到 w 的最短路径长度；若不存在路径，则距离为 ∞。
连通性
无向图的连通性：
- 连通：顶点 v 到 w 之间存在路径，则称 v 和 w 连通
- 连通图：图中任意两个顶点都连通
- 连通分量：无向图中的极大连通子图
⭐ 无向图连通的边数条件：
| 条件 | 说明 |
|---|---|
| 连通图至少 n-1 条边 | 边数 < n-1 一定不连通 |
| n-1 条边不一定连通 | 可能有孤立顶点 |
| 边数 > (n-1)(n-2)/2 则一定连通 | 利用完全图反证 |
有向图的连通性：
- 强连通：顶点 v 到 w 和 w 到 v 之间都存在路径
- 强连通图：任意两个顶点都强连通
- 强连通图至少需要 n 条弧（构成一个环）
二部图（二分图）
顶点集 V 可分为两个互不相交的子集 V₁ 和 V₂，图中每条边的两个端点分别属于 V₁ 和 V₂。
⭐ 判定定理：图 G 是二部图 ⟺ G 中不含奇数长度的回路。
完全二部图 K(m,n)：V₁ 中每个顶点与 V₂ 中每个顶点都有边，共 m×n 条边。
连通分量与强连通分量
连通分量（无向图）：无向图中的极大连通子图。连通图只有一个连通分量，即其自身。非连通图有多个连通分量。
⭐ "极大"的含义：不能再加入更多的顶点和边使其仍然连通。
强连通分量（有向图）：有向图中的极大强连通子图。
- 强连通图只有一个强连通分量，即其自身
- 任何一个顶点本身构成一个强连通分量
- 求强连通分量的方法：对图进行两次 DFS（Kosaraju 算法 / Tarjan 算法）
边数公式速查
| 图类型 | 边数公式/范围 | 说明 |
|---|---|---|
| 无向完全图 K_n | n(n-1)/2 | 每对顶点一条边 |
| 有向完全图 | n(n-1) | 每对顶点两条弧 |
| 无向连通图 | n-1 ≤ e ≤ n(n-1)/2 | 最少为树，最多为完全图 |
| 强连通图 | n ≤ e ≤ n(n-1) | 最少构成一个环 |
| 完全二部图 K(m,n) | m × n | V₁ 有 m 个，V₂ 有 n 个 |
| 无向图度数之和 | 2e | 握手定理 |
| 有向图入度之和 | e | 等于出度之和 |
考研高频考点
- ⭐ 握手定理：由度数求边数，或由边数求度数（选择题高频）
- ⭐ 连通图的最少/最多边数判断（选择题必考）
- ⭐ 连通分量与强连通分量的区分（概念题/选择题）
- ⭐ 完全图的边数公式（选择题/填空题）
- ⭐ 二部图的判定条件（不含奇数回路）
- 简单图 vs 多重图的区别
- 子图与生成子图的概念辨析
- 强连通图至少需要 n 条弧