# 图的基本概念：有向/无向、度、连通性 > 本文出自 CodeBrick 408 数据结构讲义，原文：https://www.codebrick.tech/ds-blog/posts/graph/concepts > 这是供 AI 阅读的纯文本版：公式为 LaTeX，流程图为 mermaid 源码，原文中的折叠内容已全部展开。 > 讲解或引用本文内容时，请一并给出上面的原文链接。 > 2026 大纲 **五（一）图的基本概念**。后面所有算法都直接引用本篇的定义。 ## 图是什么 图 $G=(V,E)$ 由**顶点集 $V$** 和**边集 $E$** 组成。这里有一处容易被略过的不对称：$V$ 是**有穷非空**集合——不存在没有顶点的图；而 $E$ **可以是空集**——$n$ 个孤零零的顶点、一条边都没有，它仍然是一个合法的图。 图与前面学过的线性表、树的根本区别，在于**顶点之间的关系是任意的**。线性表里一个元素只跟前驱后继有关系，树里一个结点只跟父结点和孩子有关系，而图里**任意两个顶点之间都可能有关系**。 > 🔴 **图没有顺序存储。** 不是不能用数组，而是**不能用元素在数组中的位置来表示边**——位置只编码得了"谁挨着谁"这一种关系，图却要表达任意两点之间的关系。所以后面的邻接矩阵、邻接表，都得把边**显式**记下来。 在"顶点之间有关系"这个共同点之上，边还有两个可变的维度，后面所有算法的分类都是从这两条长出来的： - **边可以有方向。** 无向图的边记作 $(v,w)$，$(v,w)$ 与 $(w,v)$ 是同一条边；有向图的边叫**弧**，记作 $\langle v,w\rangle$，$v$ 是**弧尾**、$w$ 是**弧头**，$\langle v,w\rangle \ne \langle w,v\rangle$。 - **边可以带权。** 边上标的数值叫**权**，带权的图叫**网**。权可以是距离、代价、容量，取决于这张图在建模什么。 最后约定一个前提：**既没有重复边、也没有顶点到自身的边**的图叫**简单图**，反之叫**多重图**。408 若无特别说明**一律默认简单图**——本篇后面所有边数上界公式，都只在简单图下成立。 这一篇剩下的内容，就是沿着上面这两个维度往下展开的： ```mermaid flowchart TD G["图 G = (V, E)"] --> D1["按边有无方向"] G --> D2["按边有无权值"] D1 --> UG["无向图：边 (v,w)"] D1 --> DG["有向图：弧 ⟨v,w⟩"] D2 --> NW["无权图"] D2 --> WG["带权图（网）"] UG --> DEG["度 TD(v)"] DG --> DEG2["入度 ID(v) + 出度 OD(v)"] DEG --> HS["握手定理 Σ度 = 2e"] DEG2 --> HS2["Σ入度 = Σ出度 = e"] HS --> CNT["边数上下界 / 连通性判据"] HS2 --> CNT UG --> C1["连通 → 连通分量 → 生成树"] DG --> C2["强连通 → 强连通分量 → 生成森林"] ``` ## 先动手看一眼 > 【交互可视化】图的基本概念可视化：https://www.codebrick.tech/visual/graph/concepts > （这是一个可以逐步执行的动画演示，纯文本版无法呈现，需要时请提示用户去这个链接看。） 下面这些结论全都能在图上先"看"出来，建议按这个顺序拨：切到**「度/入度/出度」**点任意一个顶点，观察它的 $ID$、$OD$、$TD$ 三个数是怎么对上的；切到**「完全图」**，比对面板里的 $|E|$ 与 $C(n,2)$；切到**「连通性」**和**「强连通分量」**，把同一组顶点在无向、有向两种模式下来回切，看分量的划分怎么变。 **看完你应该确认两件事**：同一组顶点，有向图能放下的边是无向图的两倍；以及**方向一变，"能互相到达"这件事就可能整片塌掉**。本篇后半的计数结论，基本都是这两件事的量化。 ## 有向图与无向图 ```mermaid flowchart LR subgraph 无向图["无向图：边无方向"] A1((A)) --- B1((B)) A1 --- C1((C)) B1 --- C1 end subgraph 有向图["有向图：边有方向"] A2((A)) --> B2((B)) A2 --> C2((C)) C2 --> B2 end ``` 方向的有无，直接决定了同一组顶点最多能放多少条边。$n$ 个顶点两两之间只能放一条无向边，所以无向图最多 $\dfrac{n(n-1)}{2}$ 条；换成有向图，每一对顶点可以放两条方向相反的弧，于是翻倍成 $n(n-1)$ 条。边数达到这个上限的简单图叫**完全图**。 **子图**是从原图里挖出来的一块：$V'\subseteq V$、$E'\subseteq E$。但 ⚠️ 顶点子集和边子集**不能随便挑**——$E'$ 中每条边的两个端点都必须留在 $V'$ 里，否则挖出来的东西根本不是一张图。只删边、不删顶点（即 $V'=V$）的子图，叫**生成子图**，后面的生成树就是它的特例。 ## 度与握手定理 **度**就是一个顶点"连着几条边"。无向图里 $TD(v)$ = 与 $v$ 关联的边数；有向图要拆成两笔账：**入度** $ID(v)$ 是以 $v$ 为**弧头**的弧数，**出度** $OD(v)$ 是以 $v$ 为**弧尾**的弧数，而 $TD(v)=ID(v)+OD(v)$。 > 🔴 **握手定理**：$\sum TD(v)=2e$。有向图则是 $\sum ID(v)=\sum OD(v)=e$，两者相加，$\sum TD(v)$ 仍然是 $2e$。 本节后面几条计数结论都从它出发，而它的推导只有一句话：**把"数度"换个数法。** 不按顶点数，改按边数——每条无向边 $(u,v)$ 恰好给 $u$ 贡献 1 度、给 $v$ 贡献 1 度，一共 2 度，$e$ 条边共贡献 $2e$ 度；按顶点数得到的总度数则是 $\sum TD(v)$。同一个量的两种数法必然相等，等式就出来了。有向图同理，每条弧贡献"1 个入度 + 1 个出度"，只是这两度落在了不同的账上，于是 $\sum ID=\sum OD=e$。 顺着这个等式能直接读出三条推论： 1. **度为奇数的顶点必定有偶数个。** 因为 $\sum TD(v)=2e$ 是偶数，把偶度顶点的贡献去掉，剩下奇度顶点的度之和仍是偶数；而若干个奇数相加要得偶数，个数只能是偶数。 2. **已知各顶点的度，边数唯一确定**：$e=\frac12\sum TD(v)$。 3. 已知边数和一部分顶点的度，可以反过来卡出顶点数的下界。 完全图的边数其实也是握手定理的一个直接推论：每个顶点与其余 $n-1$ 个顶点都相邻，度之和为 $n(n-1)$，除以 2 就是 $\dfrac{n(n-1)}{2}$。**它和上一节"两两配对"的数法得到同一个结果不是巧合——本来就是同一件事的两种数法。** 度还带出一组常用的粗分类：边很少的图叫**稀疏图**、边很多的叫**稠密图**，两者没有绝对分界，经验判据是 $e ⚠️ 路径长度数的是**边**，不是顶点——一条路径上的顶点数总比边数多 1，这个差 1 要留神。带权图里另有一个**带权路径长度**，指路径上各边权值之和。 在此之上加限制，就得到几个成组出现的术语：顶点不重复出现的路径叫**简单路径**；首尾顶点相同的路径叫**回路（环）**；除首尾外顶点不重复的回路叫**简单回路**。 **距离**是 $v$ 到 $w$ 的最短路径长度，不存在路径时记为 $\infty$。注意有向图里 $d(v,w)$ 与 $d(w,v)$ 是两个独立的量，完全可能一个有限、一个无穷。 ## 连通性 ### 无向图：连通分量是"极大"的 $v$ 与 $w$ 之间存在路径，就说这两个顶点**连通**；图中任意两个顶点都连通，就是**连通图**。不连通的图会散成几块，每一块叫一个**连通分量**，定义是**极大连通子图**。 "极大"的意思是**再从原图里拉进任何一个顶点，它就不连通了**。所以各个连通分量之间没有公共顶点，并起来正好是整个 $V$——这也是"分量"这个词的由来。 与它成对出现的是**生成树**：含全部 $n$ 个顶点、只有 $n-1$ 条边的**极小连通子图**，"极小"指**再删掉任何一条边就不连通了**。一个有 $n$ 个顶点、$k$ 个连通分量的图，每个分量各出一棵生成树，合起来叫**生成森林**，总边数为 $n-k$ 条。 > **极大和极小是从两个方向卡的**：问"再加一个顶点还连通吗"是极大，问"再删一条边还连通吗"是极小。两个词都在描述"恰好卡在边界上"。 ### 有向图：连通被细分成三级 无向图只有"连通 / 不连通"两态。有向图因为边有方向，同样一句"能不能到达"要分成三级来问，而且**层层加强**：强连通 $\Rightarrow$ 单向连通 $\Rightarrow$ 弱连通，反过来都不成立。 | 名称 | 定义 | 判别方法 | |---|---|---| | **弱连通** | 抹掉所有弧的方向后得到的**基图**是连通图 | 忽略方向做一次 DFS/BFS，看能否走遍全部顶点 | | **单向连通** | 任意两顶点 $u,v$，**至少**有一个方向可达 | 存在一条经过所有顶点的有向路径时必成立 | | **强连通** | 任意两顶点**两个方向都**可达 | 每个顶点的入度、出度都不为 0 是必要条件 | 三个顶点就足够把这三级分开： - $0\to 1,\ 1\to 2,\ 2\to 0$：**强连通**，绕着环走谁都能到谁。 - $0\to 1,\ 1\to 2$：**单向连通但非强连通**。$0$ 能到 $2$、$2$ 回不去，但每一对顶点都至少有一个方向通。 - $0\to 2,\ 1\to 2$：**弱连通但非单向连通**。抹掉方向后 $0-2-1$ 是连通的，可 $0$ 与 $1$ 之间两个方向都不可达。 > ⚠️ 题面上说"**连通的有向图**"，若无特别说明通常指**弱连通**（基图连通）；而"强连通"一定会被明确写出来。看到这个说法先确认它指的是哪一级。 有向图的**强连通分量**是**极大强连通子图**，和无向图的连通分量对应。有一点要留意：**单独一个顶点本身就构成一个强连通子图**，所以强连通分量一定覆盖全部顶点，不会有顶点落在所有分量之外。求法是对图做两次 DFS（Kosaraju 算法 / Tarjan 算法）。 还有一个单独命名的特例：**有向树**——恰有一个顶点入度为 0、其余顶点入度均为 1 的有向图。 **强连通图至少需要 $n$ 条弧**，推理同样只有两步：每个顶点的入度和出度都不能为 0，故 $\sum OD(v)\ge n$，即 $e\ge n$；而 $n$ 条弧确实够用——把所有顶点串成一个有向环 $v_1\to v_2\to\cdots\to v_n\to v_1$，任意两点绕环都能互达。所以这个下界是**紧的**。 ## 用边数判连通性 还有一类问法不给图，只给 $n$ 和 $e$ 两个数，问能推出什么。核心是三条： | 边数 | 结论 | 理由 | |---|---|---| | $e < n-1$ | **一定不连通** | 连通至少要 $n-1$ 条边（生成树是边数最少的连通生成子图） | | $e = n-1$ | **不一定是生成树** | 可能是"环 + 孤立点"这类既不连通又有环的图 | | $e > n-1$ | **一定有环** | 生成树上再加一条边，其两端之间就出现了第二条路径 | 中间那条的反例：$n=4$、边为 $(0,1),(1,2),(2,0)$，顶点 3 孤立、$0,1,2$ 成环。**"$n-1$ 条边"既不保证连通，也不保证无环。** 反过来，边足够多也能强行保证连通： > 🔴 $e>\dfrac{(n-1)(n-2)}{2}\Rightarrow$ 图一定连通。**不等号必须严格大于**——取等号时可能不连通，反例是 $K_{n-1}$ 再加一个孤立点。 直觉是这样的：一张不连通的图，边最多也只能挤在各自的块内部；而"块内塞得最满"的极端形态就是**一个孤立顶点 + 剩下 $n-1$ 个点组成完全图**，此时边数恰好是 $\dfrac{(n-1)(n-2)}{2}$。既然题给的边数比这个最大值还大，图就不可能不连通。数值感受一下（$n=6$）：$\dfrac{5\times4}{2}=10$，所以边数 $\ge 11$ 必连通；而边数 $=10$ 时，"$K_5$ + 1 个孤立点"恰好 10 条边且不连通。 **〔原文中此段为可折叠内容〕上面那句"极端形态"的严格证明（想看清 $\frac{(n-1)(n-2)}{2}$ 怎么算出来的就展开）** 反证。假设图不连通，则顶点集可以划分成两个非空部分，大小为 $k$ 与 $n-k$（$1\le k\le n-1$），且**两部分之间一条边都没有**。所有边只能落在各自内部，边数最多是两个完全图之和： $$f(k)=\binom{k}{2}+\binom{n-k}{2}=\frac{k^2+(n-k)^2-n}{2}$$ $k^2+(n-k)^2$ 关于 $k$ 是开口向上的二次函数，在 $[1,\,n-1]$ 上的最大值只可能在端点取到，即 $k=1$ 或 $k=n-1$，此时 $k^2+(n-k)^2=1+(n-1)^2$，代回得 $$f_{\max}=\frac{1+(n-1)^2-n}{2}=\frac{n^2-3n+2}{2}=\frac{(n-1)(n-2)}{2}$$ 即**不连通的图边数最多只能是 $\dfrac{(n-1)(n-2)}{2}$**。题设边数比这个上界还大，假设不成立。∎ 这个证明给出的信息比结论多：它顺带回答了"$n$ 个顶点的不连通无向图最多多少条边"，也说明这个界是**紧的**——$e=\dfrac{(n-1)(n-2)}{2}$ 时图**可能**不连通、也**可能**连通，所以判据里的不等号必须严格。 > ⚠️ **有向图的边数判据别照搬。** $e>(n-1)(n-2)$ 只能推出**基图**（抹掉方向的无向图）连通，**推不出强连通**——弧的方向可以全部朝同一侧，此时任何一对顶点都没法互相到达。 ## 二部图 顶点集 $V$ 能划分成两个互不相交的非空子集 $V_1$ 与 $V_2$，使得图中**每条边的两个端点分属不同子集**，这样的图叫**二部图**（二分图）。 **判定定理**：$G$ 是二部图 $\iff$ $G$ 中不含**奇数长度的回路**。 为什么？把两个子集染成两种颜色，那么每走一条边必然换一次色。沿一条回路走一圈回到起点，颜色必须还原，所以走过的边数只能是偶数。反过来，若图中没有奇环，就可以按"到某个起点的距离的奇偶性"给顶点染色，这个染色一定合法。由此可直接读出两个特例：**树一定是二部图**（无回路自然无奇回路），**含三角形的图一定不是**。 **完全二部图 $K_{m,n}$** 指 $V_1$ 中每个顶点都与 $V_2$ 中每个顶点相连，共 $m\times n$ 条边。在 $m+n$ 固定时，边数在 $m$、$n$ 尽量接近处取到最大（均值不等式）。 ## 边数公式速查 复习时只看这一节即可，每一条的来历都在正文里。 | 图类型 | 边数公式 / 范围 | 取到边界的图长什么样 | |--------|--------------|------| | 完全图 | 无向 $n(n-1)/2$；有向 $n(n-1)$ | 每对顶点一条边 / 两条反向弧 | | 无向连通图 | $n-1\le e\le n(n-1)/2$ | 下界为生成树，上界为完全图 | | 强连通图 | $n\le e\le n(n-1)$ | 下界为一个有向环 | | 不连通无向图 | $e\le (n-1)(n-2)/2$ | 1 个孤立点 + $K_{n-1}$ | | 完全二部图 $K_{m,n}$ | $m\times n$ | $V_1$、$V_2$ 各 $m$、$n$ 个顶点 | | $n$ 顶点 $k$ 分量的生成森林 | $n-k$ 条边 | 每个分量各贡献一棵生成树 | | 连通分量个数 | 下界 $\max(n-e,\,1)$；上界 $n-k+1$（$k$ 为满足 $\binom{k}{2}\ge e$ 的最小值） | 每条边最多消灭一个分量；边挤在尽量少的顶点里 | | 度与边数 | 无向 $\sum TD(v)=2e$；有向 $\sum ID=\sum OD=e$ | 握手定理 | ## 考点速记 四条结论，正文里都推过一遍，记不住可以现推： 1. **$\sum TD(v)=2e$**（有向图为 $\sum ID=\sum OD=e$）——计数题的起点，忘了就用"换个数法"现推。 2. **$en-1$ 必有环；$e=n-1$ 两者都推不出来。** 3. **$e>\dfrac{(n-1)(n-2)}{2}$ 必连通**，界紧且不等号必须严格；关键是记住"不连通时边数最多的形态是 $K_{n-1}$ 加一个孤立点"。 4. **极大**（连通分量）与**极小**（生成树）是从两个方向卡边界，别混。 **这一节在真题里被考过的形式**（下方「真题练习」逐题对应）： - **由度数反推顶点数的极值**：给出总边数和一部分顶点的度，问顶点数最少是多少。先用握手定理把总度数锁死，再让剩下的顶点各自取极端。 - **只给 $|V|$ 与 $|E|$ 的大小关系判连通**：整道题四个选项都在这两个数之间比大小，逐个举反例。 - **保证任何情况下都连通的最少边数**：问的是"不管怎么连都连通"，落在 $\dfrac{(n-1)(n-2)}{2}+1$，不是 $n-1$。 - **区分度、入度与出度**：给邻接矩阵问某顶点的出度（按行还是按列），或问在邻接表上求出度、入度的时间复杂度差别。 - **有向图的概念判断**：入度为 0 的顶点是否一定存在、顶点度都不小于 2 是否一定有回路，这类命题的真伪。 - **路径长度的上界**：无环时任何路径最多 $n-1$ 条边，有环时长度没有上界。 > **易错**：**度**在有向图里是"入度 + 出度"。邻接矩阵里**按行数得到的是出度、按列数得到的是入度**，只数一个方向就中招了。 > **易错**：**"保证连通的最少边数"不是"连通图的最少边数"。** 后者是 $n-1$（生成树），前者要问"不管边怎么连都连通"，得用 $\dfrac{(n-1)(n-2)}{2}+1$。读题先分清问的是"任何一种连法"还是"存在一种连法"。 > **易错**：**路径长度数的是边，不是顶点。** 一条路径上顶点数比边数多 1，给你一串顶点序列问长度，先数边。 **〔原文中此段为可折叠内容〕教材出处** - 严蔚敏《数据结构（C 语言版）》（第 2 版）**印刷 p149**，§6.1.1 图的定义： "图 (Graph) $G$ 由两个集合 $V$ 和 $E$ 组成……$V$ 是顶点的有穷非空集合， $E$ 是 $V$ 中顶点偶对的有穷集合"，并指出 $E(G)$ 可以为空集。 - 同书**印刷 p150**，§6.1.2 基本术语（2）（3）：无向完全图 $n(n-1)/2$ 条边、 有向完全图 $n(n-1)$ 条弧；"有很少条边或弧（如 $e