图的基本概念

2026 大纲 五（一）图的基本概念。后面所有算法都直接引用本篇的定义。

图是什么

图 $G=(V,E)$ 由顶点集 $V$ 和边集 $E$ 组成。这里有一处容易被略过的不对称：$V$ 是有穷非空集合——不存在没有顶点的图；而 $E$ 可以是空集——$n$ 个孤零零的顶点、一条边都没有，它仍然是一个合法的图。

图与前面学过的线性表、树的根本区别，在于顶点之间的关系是任意的。线性表里一个元素只跟前驱后继有关系，树里一个结点只跟父结点和孩子有关系，而图里任意两个顶点之间都可能有关系。

🔴 图没有顺序存储。 不是不能用数组，而是不能用元素在数组中的位置来表示边——位置只编码得了"谁挨着谁"这一种关系，图却要表达任意两点之间的关系。所以后面的邻接矩阵、邻接表，都得把边显式记下来。

在"顶点之间有关系"这个共同点之上，边还有两个可变的维度，后面所有算法的分类都是从这两条长出来的：

• 边可以有方向。 无向图的边记作 $(v,w)$，$(v,w)$ 与 $(w,v)$ 是同一条边；有向图的边叫弧，记作 $⟨v,w⟩$，$v$ 是弧尾、$w$ 是弧头，$⟨v,w⟩\ne ⟨w,v⟩$。
• 边可以带权。 边上标的数值叫权，带权的图叫网。权可以是距离、代价、容量，取决于这张图在建模什么。

最后约定一个前提：既没有重复边、也没有顶点到自身的边的图叫简单图，反之叫多重图。408 若无特别说明一律默认简单图——本篇后面所有边数上界公式，都只在简单图下成立。

这一篇剩下的内容，就是沿着上面这两个维度往下展开的：

先动手看一眼

加载可视化中...

下面这些结论全都能在图上先"看"出来，建议按这个顺序拨：切到「度/入度/出度」点任意一个顶点，观察它的 $ID$、$OD$、$TD$ 三个数是怎么对上的；切到「完全图」，比对面板里的 $|E|$ 与 $C(n,2)$；切到「连通性」和「强连通分量」，把同一组顶点在无向、有向两种模式下来回切，看分量的划分怎么变。

看完你应该确认两件事：同一组顶点，有向图能放下的边是无向图的两倍；以及方向一变，"能互相到达"这件事就可能整片塌掉。本篇后半的计数结论，基本都是这两件事的量化。

有向图与无向图

方向的有无，直接决定了同一组顶点最多能放多少条边。$n$ 个顶点两两之间只能放一条无向边，所以无向图最多 ${\displaystyle \frac{n(n-1)}{2}}$ 条；换成有向图，每一对顶点可以放两条方向相反的弧，于是翻倍成 $n(n-1)$ 条。边数达到这个上限的简单图叫完全图。

子图是从原图里挖出来的一块：$V^{\prime }\subseteq V$、$E^{\prime }\subseteq E$。但 ⚠️ 顶点子集和边子集不能随便挑——$E^{\prime }$ 中每条边的两个端点都必须留在 $V^{\prime }$ 里，否则挖出来的东西根本不是一张图。只删边、不删顶点（即 $V^{\prime }=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=\frac{1}{2}\sum TD(v)$。
3. 已知边数和一部分顶点的度，可以反过来卡出顶点数的下界。

完全图的边数其实也是握手定理的一个直接推论：每个顶点与其余 $n-1$ 个顶点都相邻，度之和为 $n(n-1)$，除以 2 就是 ${\displaystyle \frac{n(n-1)}{2}}$。它和上一节"两两配对"的数法得到同一个结果不是巧合——本来就是同一件事的两种数法。

度还带出一组常用的粗分类：边很少的图叫稀疏图、边很多的叫稠密图，两者没有绝对分界，经验规则是 $e<n{\log }_{2}n$ 算稀疏。这个分类唯一的用处是选型：稠密图用邻接矩阵、配 Prim；稀疏图用邻接表、配 Kruskal。

路径、回路与距离

路径是从 $v$ 到 $w$ 的一串顶点序列，路径长度是路径上边（弧）的数目。

⚠️ 路径长度数的是边，不是顶点——一条路径上的顶点数总比边数多 1，这个差 1 要留神。带权图里另有一个带权路径长度，指路径上各边权值之和。

在此之上加限制，就得到几个成组出现的术语：顶点不重复出现的路径叫简单路径；首尾顶点相同的路径叫回路（环）；除首尾外顶点不重复的回路叫简单回路。

距离是 $v$ 到 $w$ 的最短路径长度，不存在路径时记为 $\mathrm{\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>{\displaystyle \frac{(n-1)(n-2)}{2}}\Rightarrow$ 图一定连通。不等号必须严格大于——取等号时可能不连通，反例是 $K_{n-1}$ 再加一个孤立点。

直觉是这样的：一张不连通的图，边最多也只能挤在各自的块内部；而"块内塞得最满"的极端形态就是一个孤立顶点 + 剩下 $n-1$ 个点组成完全图，此时边数恰好是 ${\displaystyle \frac{(n-1)(n-2)}{2}}$。既然题给的边数比这个最大值还大，图就不可能不连通。数值感受一下（$n=6$）：${\displaystyle \frac{5\times 4}{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)=(\genfrac{}{}{0ex}{}{k}{2})+(\genfrac{}{}{0ex}{}{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}$$

即不连通的图边数最多只能是 ${\displaystyle \frac{(n-1)(n-2)}{2}}$。题设边数比这个上界还大，假设不成立。∎

这个证明给出的信息比结论多：它顺带回答了"$n$ 个顶点的不连通无向图最多多少条边"，也说明这个界是紧的——$e={\displaystyle \frac{(n-1)(n-2)}{2}}$ 时图可能不连通、也可能连通，所以这条规则里的不等号必须严格。

⚠️ 有向图的边数规则别照搬。 $e>(n-1)(n-2)$ 只能推出基图（抹掉方向的无向图）连通，推不出强连通——弧的方向可以全部朝同一侧，此时任何一对顶点都没法互相到达。

二部图

顶点集 $V$ 能划分成两个互不相交的非空子集 $V_1$ 与 $V_2$，使得图中每条边的两个端点分属不同子集，这样的图叫二部图（二分图）。

判定定理：$G$ 是二部图 $⟺$ $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$ 为满足 $(\genfrac{}{}{0ex}{}{k}{2})\ge e$ 的最小值）	每条边最多消灭一个分量；边挤在尽量少的顶点里
度与边数	无向 $\sum TD(v)=2e$；有向 $\sum ID=\sum OD=e$	握手定理

考点速记

四条结论，正文里都推过一遍，记不住可以现推：

1. $\sum TD(v)=2e$（有向图为 $\sum ID=\sum OD=e$）——计数题的起点，忘了就用"换个数法"现推。
2. $e<n-1$ 必不连通；$e>n-1$ 必有环；$e=n-1$ 两者都推不出来。
3. $e>{\displaystyle \frac{(n-1)(n-2)}{2}}$ 必连通，界紧且不等号必须严格；关键是记住"不连通时边数最多的形态是 $K_{n-1}$ 加一个孤立点"。
4. 极大（连通分量）与极小（生成树）是从两个方向卡边界，别混。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 由度数反推顶点数的极值：给出总边数和一部分顶点的度，问顶点数最少是多少。先用握手定理把总度数确定，再让剩下的顶点各自取极端。
• 只给 $|V|$ 与 $|E|$ 的大小关系判连通：整道题四个选项都在这两个数之间比大小，逐个举反例。
• 保证任何情况下都连通的最少边数：问的是"不管怎么连都连通"，落在 ${\displaystyle \frac{(n-1)(n-2)}{2}}+1$，不是 $n-1$。
• 区分度、入度与出度：给邻接矩阵问某顶点的出度（按行还是按列），或问在邻接表上求出度、入度的时间复杂度差别。
• 有向图的概念判断：入度为 0 的顶点是否一定存在、顶点度都不小于 2 是否一定有回路，这类命题的真伪。
• 路径长度的上界：无环时任何路径最多 $n-1$ 条边，有环时长度没有上界。

易错：度在有向图里是"入度 + 出度"。邻接矩阵里按行数得到的是出度、按列数得到的是入度，只数一个方向就中招了。

易错："保证连通的最少边数"不是"连通图的最少边数"。 后者是 $n-1$（生成树），前者要问"不管边怎么连都连通"，得用 ${\displaystyle \frac{(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<n{\log }_{2}n$）的图称为稀疏图，反之称为稠密图"。
• 同书印刷 p150，术语（6）度、入度和出度，并给出 $e=\frac{1}{2}\sum TD(v_i)$。
• 同书印刷 p151，术语（12）连通图的生成树： "一棵有 $n$ 个顶点的生成树有且仅有 $n-1$ 条边。如果一个图有 $n$ 个顶点和小于 $n-1$ 条边， 则是非连通图。如果它多于 $n-1$ 条边，则一定有环。但是，有 $n-1$ 条边的图不一定是生成树。"
• 同书印刷 p151，术语（11）强连通图和强连通分量、（13）有向树和生成森林。

相关知识

邻接矩阵 / 邻接表 / 十字链表与邻接多重表（三种存储）｜ BFS / DFS（连通分量与生成树的求法）｜ Prim / Kruskal（挑权和最小的生成树）｜ 拓扑排序（有向无环图上的顶点线性化）

相关文章

• 邻接矩阵
• 邻接表
• 十字链表与邻接多重表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Prim
• 最小生成树：Kruskal
• BFS 求无权图最短路径
• Dijkstra 算法
• Floyd 算法
• DAG 描述表达式
• 拓扑排序
• 关键路径

交互体验

前往完整可视化页面 →

真题练习

相关真题（19题）

2026Q62分2026Q72分2025Q62分2024Q4113分2023Q4113分2022Q62分2021Q72分2021Q4115分2019Q62分2017Q72分2016Q82分2015Q428分2014Q72分2014Q4210分2013Q72分2013Q82分2010Q72分2009Q72分2009Q4110分