数据结构 第 6 章 名词库

每条最多四行：是／不是／易混／范围。

建设进度：✅ 6.1 图的基本概念　✅ 6.2 图的存储及基本操作　✅ 6.3 图的遍历　✅ 6.4 图的应用　（全章完整）

---

6.1 图的基本概念

图

• 是：由顶点集 和边集 组成的结构。
• 不是：图不可以是空图。
• 范围： 一定非空， 可以为空（此时只有顶点没有边）。

弧头 / 弧尾

• 是：有向边 中， 是弧尾（起点）， 是弧头（终点）。
• 范围：十字链表的 tailvex/headvex 两个域名直接来自这里。

简单图 / 多重图

• 是：简单图 = 不存在重复边 + 不存在顶点到自身的边。
• 范围：本书中仅讨论简单图。

度 / 入度 / 出度

• 是：无向图 = 依附于 的边数；有向图 。
• 范围：无向图度数之和 ；有向图入度之和 = 出度之和 = 。
• 易混：树里的「度」只算孩子数（出度），每条边只数一次。

路径长度

• 是：路径上边的数目。
• 不是：不是顶点数。
• 易混：与第 7 章的「查找长度数结点」方向相反。

简单路径 / 简单回路

• 是：简单路径 = 顶点不重复出现；简单回路 = 除第一个和最后一个顶点外其余不重复。
• 范围：若一个图有 个顶点且边数大于 ，则一定有环。

距离

• 是：从 到 的最短路径长度。
• 范围：不存在路径则记为 。

子图 / 生成子图

• 是： 且 ； 的子图称生成子图。
• 不是：并非 和 的任何子集都能构成子图——边的两个端点必须在顶点子集中。
• 范围：生成子图的判据只有一个：顶点集完全相同。

连通分量 / 强连通分量

• 是：无向图中的极大连通子图；有向图中的极大强连通子图。
• 不是：措辞是「极大」不是「最大」。
• 范围：边数 必非连通；非连通图最多 条边。

---

6.2 图的存储

邻接矩阵

• 是：二维数组存边， 表示 到 是否有边（或权值）。
• 范围：空间 ，与边数无关；表示唯一；适合稠密图；无向图对称。
• 易混：有向图行是出度、列是入度；删边方便，删顶点需大量移动数据。

邻接表

• 是：每个顶点一个边表单链表。
• 范围：无向图空间 、有向图 ；适合稀疏图。
• 不是：表示不唯一——边表的链接次序取决于建表算法及边的输入次序。
• 易混：求有向图某顶点的入度必须遍历整个邻接表；求出度只需数本表结点。

十字链表

• 是：有向图的链式存储；弧结点 tailvex headvex hlink tlink info，顶点结点 data firstin firstout。
• 不是：不能存无向图。
• 范围：hlink 指弧头相同的下一条弧，tlink 指弧尾相同的下一条弧；出度入度都好求；表示不唯一，但一个十字链表唯一确定一个图；顶点结点之间顺序存储。

邻接多重表

• 是：无向图的链式存储；边结点 ivex ilink jvex jlink info，顶点结点 data firstedge。
• 不是：不能存有向图。
• 范围：同一条边在邻接表中用两个结点表示，在邻接多重表中只有一个结点；删边方便。

图的基本操作

• 是：Adjacent Neighbors InsertVertex DeleteVertex AddEdge RemoveEdge FirstNeighbor NextNeighbor。
• 范围：操作独立于存储结构，只是实现性能不同；FirstNeighbor/NextNeighbor 无结果时返回 。

---

6.3 图的遍历

BFS / DFS

• 是：BFS 用队列逐层扩展；DFS 用栈（或递归）深入回溯。
• 范围：邻接矩阵下 ，邻接表下 ；空间都是 。
• 易混：BFS 只对无权图求最短路径，带权要用 Dijkstra。

生成树 / 生成森林

• 是：遍历中「首次到达某顶点所用的边」构成的树；非连通图得到生成森林。
• 范围：邻接矩阵下唯一，邻接表下不唯一；边数恒为 。

遍历与连通性

• 是：无向图中调用遍历的次数 = 连通分量数。
• 不是：有向图中「一次遍历访问完所有顶点」不等于强连通，只说明该顶点可达所有顶点。

---

6.4 图的应用

最小生成树（MST）

• 是：带权连通无向图中权值之和最小的生成树。
• 范围：边数恒为 ；只对连通无向图有定义；权值之和唯一，树形不一定唯一（各边权互不相等时唯一）。

MST 性质

• 是： 是 的非空子集，若 是 、 中权值最小的边，则必存在一棵包含 的最小生成树。

Prim 算法

• 是：从一个顶点开始，每次把「与当前树集合距离最近的顶点」并入。
• 范围：，与边数无关，适合稠密图；只能用于带权无向图。

Kruskal 算法

• 是：按权值递增选边，两端在不同连通分量才加入。
• 范围：，适合稀疏图；判回路用并查集。

Dijkstra 算法

• 是：单源最短路径；每轮选 dist 最小的点并入 ，再以它为中转更新其余点。
• 范围：；有向无向都可用；要求边权非负。
• 易混：与 Prim 的三点区别——目的（最短路径树 vs 最小生成树）、思路（比累计距离 vs 比单条边权）、适用图（Dijkstra 有向无向皆可，Prim 只能无向）。

Floyd 算法

• 是：求每对顶点之间的最短路径，。
• 范围：；允许负权边，但不允许负权回路；有向无向皆可。

AOV 网 / AOE 网

• 是：AOV 顶点表示活动、边表示前后关系且无权；AOE 顶点表示事件、边表示活动且有权。
• 范围：两者都是有向无环图；AOE 网仅有一个源点和一个汇点。

拓扑排序

• 是：反复输出入度为 0 的顶点并删除其出边。
• 范围：邻接表 ；结果可能不唯一；唯一性的判据是每次输出时入度为 0 的顶点是否唯一。
• 易混：「各顶点为线性序列」只是唯一性的充分非必要条件；邻接矩阵为三角矩阵 存在拓扑序列，反之不一定。

逆拓扑排序

• 是：反复输出出度为 0 的顶点并删除其入边。
• 范围：计算 时要用；实现上用栈记录拓扑序列，从栈顶到栈底即逆拓扑序。

关键路径 / 关键活动

• 是：源点到汇点所有路径中长度最大的路径；其上的活动为关键活动。
• 范围：关键路径长度 = 完成整个工程的最短时间；关键路径可能不唯一。

四个参量

• 是： 取 Max 从前往后（拓扑序）； 取 Min 从后往前（逆拓扑序）；；；。
• 范围： 的活动即关键活动；关键路径上的顶点满足 。

---

高频范围限定清单

常见说法	范围限定
「图可以是空图」	错。 一定非空， 可空
「 中 是弧头」	错。 是弧尾（起点）
「本书讨论多重图」	错。仅讨论简单图
「无向图度数之和 = 边数」	错。
「路径长度是顶点数」	错。是边数
「简单回路顶点都不重复」	错。首尾两个相同
「、 的任意子集构成子图」	错。边的端点必须在顶点子集中
「生成子图的边集与原图相同」	错。是顶点集相同
「连通分量是最大连通子图」	教材用词是「极大」
「边数 则连通」	错。只有「 必非连通」成立
「 点 边一定是树」	错。还要连通
「邻接矩阵空间与边数有关」	错。恒为
「邻接表表示唯一」	错。取决于边的输入次序
「邻接矩阵表示不唯一」	错。唯一
「有向图邻接表求入度方便」	错。必须遍历整个邻接表
「无向图邻接表空间 」	错。
「邻接矩阵删顶点方便」	错。需大量移动数据
「十字链表可存无向图」	错。只能存有向图
「邻接多重表可存有向图」	错。只能存无向图
「邻接多重表一条边用两个结点」	错。只有一个
「hlink 指弧尾相同的下一条弧」	错。hlink 是头链
「firstin 指以该顶点为弧尾的弧」	错。firstin 是弧头
「图的基本操作依赖存储结构」	错。操作独立，性能不同
「BFS 用栈」	错。用队列
「遍历复杂度是 」	只在邻接表下；邻接矩阵是
「BFS 能求带权图最短路径」	错。只对无权图
「广度优先生成树唯一」	邻接矩阵下唯一，邻接表下不唯一
「非连通图遍历得生成树」	错。得生成森林
「有向图一次遍历访问完即强连通」	错。只说明该点可达所有点
「最小生成树唯一」	错。权值和唯一，树形不一定
「MST 对有向图有定义」	错。只对连通无向图
「Prim 适合稀疏图」	错。，适合稠密图
「Prim 可用于有向图」	错。只能用于带权无向图
「Dijkstra 只能用于有向图」	错。有向无向皆可
「Dijkstra 能处理负权边」	错。要求非负
「Floyd 不能有负权边」	错。允许负权边，不允许负权回路
「拓扑序列唯一 ⟺ 顶点成线性序列」	错。只是充分非必要条件
「有拓扑序列则邻接矩阵是三角矩阵」	错。反之才成立
「AOV 网的边有权值」	错。AOV 无权，AOE 有权
「AOE 网可有多个源点」	错。仅一个源点、一个汇点
「关键路径是最短路径」	错。是最长路径，但等于最短完成时间
「关键路径唯一」	错。可能多条
「加快任一关键活动都能缩短工期」	错。多条关键路径时要看公共活动
「 取 Min」	错。取 Max； 才取 Min
「 是弧终点的最早发生时间」	错。是起点的
「」	错。
「 用拓扑序算」	错。用逆拓扑序，需用栈

链接

• 🏠 返回总览：数据结构第 6 章：图总览
• 📕 附录入口：数据结构附录