五、图（第 51-64 题）
51. 无向图中，所有顶点的度之和等于边数的( )倍。
标签：【互联网/国企笔试高频】
A. 1 B. 2 C. 3 D. 不确定
答案：B
【结论】 所有顶点的度之和 = 2 × 边数，选 B。
【逐项辨析】
- A 1：漏掉了“每条边贡献两个度”这一事实。
- B 2：正确。 每条边有两个端点，各贡献 1 度。
- C 3：无依据。
- D 不确定：这个倍数对任何无向图都恒为 2。
【知识点】 握手定理(Handshaking Lemma):
无向图:Σdeg(v) = 2|E| (度之和 = 2 × 边数)推导： 每条边 (u, v) 连接两个顶点，对 u 贡献 1 度、对 v 贡献 1 度，共 2 度。所有边累加即得 2|E|。
一个重要推论：任何无向图中，度为奇数的顶点个数必为偶数（因为度之和是偶数）。
示例:三角形(3 个顶点、3 条边)
每个顶点度都是 2 → 度之和 = 2+2+2 = 6 = 2 × 3 ✓
奇度顶点数 = 0(偶数) ✓
示例:一条链 a—b—c(3 个顶点、2 条边)
度:a=1, b=2, c=1 → 度之和 = 4 = 2 × 2 ✓
奇度顶点:a 和 c,共 2 个(偶数) ✓【记忆锚点】 “一条边给两个度，度之和是边数两倍”。
【易混对比】 无向图 vs 有向图的度
| 无向图 | 有向图 | |
|---|---|---|
| 度的定义 | 与该顶点相连的边数 | 入度 + 出度 |
| 求和公式 | Σdeg(v) = 2|E| | Σ入度 = Σ出度 = |E| |
有向图不乘 2，因为一条有向边只贡献 1 个出度和 1 个入度（见第 53 题）。
【自测】 一个无向图有 10 条边，则所有顶点的度之和是多少？
答：20。由 Σdeg(v) = 2|E| = 2 × 10 = 20。与第 53 题连考。
【知识关联】
- 同库连考：与第 53 题（有向图 Σ入=Σ出=|E|）构成握手定理双题；与第 52/54/64 题（完全图边数、连通最少边）同属「图计数」；与第 55 题（邻接表空间 O(n+e)）相连——无向邻接表边结点总数=2e，正是本定理的存储体现。
- 工程实现：社交网络校验「关注/好友关系总数」；网络端口连接数统计；邻接矩阵无向图对称，非零元=2e（见第 54 题）。工程图库统计边时用该不变量做完整性检查。
- 408 / 国企真题：408「无向图所有顶点度之和」答案 2|E|；国网常考推论「奇度顶点个数为偶数」；与有向图公式混用是最高频错项。
- 面试追问:①「10 条边度之和？」（20）；②「奇度顶点为何必偶数个？」（度之和为偶数）；③「自环贡献几度？」（无向自环贡献 2 度）。
【拓展延伸】
变式问法:①「度之和是边数几倍？」（2 倍，本题）；②「有向图入度之和？」（=|E|）；③「给定度序列能否构成简单图？」（Erdős–Gallai 定理/握手定理必要条件）。
工程映射：社交「好友总数×2=握手次数」；电网出线回路数与节点度；编译器调用图边统计。
易错提醒：无向乘 2，有向不乘；选项 D「不确定」错在该比值恒为 2。多重图/带自环时公式微调，但选择题默认简单图。
52. 一个有n个顶点的无向连通图，最少有( )条边。
标签：【互联网/国企笔试高频】
A. n-1 B. n C. n(n-1)/2 D. n²
答案：A
【结论】 n 个顶点的无向连通图最少 n−1 条边（即一棵生成树），选 A。
【逐项辨析】
- B n：这是有向强连通图的最少边数（所有顶点构成一个大环），不是无向图。
- A n−1：正确。 连通要求任意两点间有路径；用最少边实现连通，结构就是树。
- C n(n−1)/2：这是无向完全图的边数，是“最多”而非“最少”，方向反了。
- D n²：无向图边数上限是 n(n−1)/2，达不到 n²（除非允许自环 / 多重边）。
【知识点】 四类图的边数范围（必背表）：
| 图类型 | 最少边 | 最多边 |
|---|---|---|
| 无向连通图 | n − 1 | n(n−1)/2 |
| 有向强连通图 | n | n(n−1) |
| 无向图（不要求连通） | 0 | n(n−1)/2 |
| 有向图（不要求强连通） | 0 | n(n−1) |
两条推导依据：1. n 个顶点要连通，至少 n−1 条边（树的性质：连通且无环 ⟺ 边数 = 顶点数 − 1）；再加 1 条边就成环。 2. 无向图边数“除以 2” 是因为无向边没有方向，(u,v) 与 (v,u) 是同一条边；有向边 (u,v) 与 (v,u) 是两条。
【记忆锚点】 “连通看树(n−1)，完全看对(n(n−1)/2)；无向除以 2，有向不除。”
【易混对比】 本题最大陷阱是“无向”与“有向”一字之差:
- 无向连通 → 最少 n−1（树）
- 有向强连通 → 最少 n（环）
题干问的是“无向连通”，答案必须是 n−1；若题干改成“有向强连通”，答案变成 n。考试中这两个词经常被故意调换来设置陷阱。
【自测】 一个有 n 个顶点的有向强连通图，最少有多少条边？
答：n 条（所有顶点构成一个环）。与本题对照记忆。国网真题库同型题。
【知识关联】
- 同库连考：与第 51 题（无向图度之和=2|E|）、第 53 题（有向图 Σ入=Σ出=|E|）构成握手定理族；与第 54、55 题（邻接矩阵/邻接表的空间开销）对照「计数 vs 存储」。
- 工程实现：握手定理是图论不变量；网络拓扑、社交图统计都用。
- 408 / 国企真题:408 与国网必背。
- 面试追问:①「有向图度之和？」（2e，入度出度各 e）；②「为何无向是 2e？」（一条边贡献两个端点的度）。
【拓展延伸】
完整验算:
无向:Σdeg(v) = 2e
有向:Σin = Σout = e, Σdeg = 2e
e=10 → 无向度之和 20变式：奇度顶点个数必为偶数（握手定理推论）。
工程应用：图数据质量校验、页排名入度统计。
53. 在有向图中，所有顶点的入度之和与出度之和的关系是( )
标签：【互联网/国企笔试高频】
A. 入度之和 > 出度之和 B. 入度之和 < 出度之和 C. 入度之和 = 出度之和 D. 不确定
答案：C
【结论】 入度之和 = 出度之和 = 边数，选 C。
【逐项辨析】
- A 入度之和 > 出度之和：无依据。
- B 入度之和 < 出度之和：无依据。
- C 入度之和 = 出度之和：正确。 两者都等于边数 |E|。
- D 不确定：这个等式对任何有向图都恒成立。
【知识点】 有向图的度定理
Σ入度 = Σ出度 = |E|推导： 每条有向边 u → v 从一个顶点出发（贡献 1 个出度），到另一个顶点结束（贡献 1 个入度）。所有边累加，出度总数与入度总数都恰好等于边数。
示例:a → b, a → c, b → c(3 条边)
出度:a=2, b=1, c=0 → 合计 3
入度:a=0, b=1, c=2 → 合计 3
两者相等,都等于边数 3 ✓由“入度之和 = 出度之和”还可推出：有向图中所有顶点的度数之和 = 2|E|（度 = 入度 + 出度）。
【记忆锚点】 “有向图：一条边一个出、一个入，所以入度出度都等于边数”。
【易混对比】 无向图 vs 有向图（最常设的一对干扰）：
| 无向图 | 有向图 | |
|---|---|---|
| 度之和 | Σdeg(v) = 2|E| | Σ（入+出） = 2|E| |
| 入度 / 出度 | 无此概念 | Σ入 = Σ出 = |E| |
关键区别：无向图“度之和 = 2|E|”；有向图“入度之和 = 出度之和 = |E|”。两者不可混淆。
【自测】 一个有 8 条边的有向图，所有顶点的入度之和是多少？
答：8。等于边数。与第 51 题连考。
【知识关联】
- 同库连考：与第 51 题（无向图度之和=2|E|）构成「握手定理」双题——本题考有向版「Σ入=Σ出=|E|」，第 51 题考无向版「Σdeg=2|E|」；与第 52 题（无向连通最少边 n−1）、第 64 题（有向完全图边数 n(n−1)）连成「图的计数」专题；与第 55 题（邻接表 vs 矩阵）中「邻接矩阵行和=出度、列和=入度」直接对应。
- 工程实现：社交关注图中「入度=粉丝数、出度=关注数」，二者总和恒等即关注关系总量；网页链接图里 PageRank 的随机游走也建立在「每条边贡献一出一入」之上；JDK 无内置图结构，工程图库（JGraphT、Neo4j）统计边数时都用这一不变量做校验。
- 408 / 国企真题：408 数据结构图章选择题高频；国网计算机类「图的基本概念」模块常以「下列等式恒成立的是」形式出现，干扰项往往是「入度之和=2|E|」（与无向公式混用）或「入度之和>出度之和」。
- 面试追问:①「有向图所有顶点的度之和是多少？」（=入+出总和=2|E|，不是|E|）；②「强连通有向图最少几条边？」（n，恰好一个有向环）；③「邻接矩阵里怎么快速验证本定理？」（矩阵所有元素之和=|E|；第 i 行和=顶点 i 的出度，第 j 列和=入度）。
【拓展延伸】
变式问法:①「有向图中入度之和等于出度之和吗？」（恒等，且都等于边数）；②「某顶点入度为 3、出度为 2，则该点度是多少？」（5，度=入+出）；③「无向图能否谈入度？」（不能，无向图只有度）。
工程映射：有向依赖图（Maven 依赖、编译 include）用入度做拓扑排序入口；微服务调用链统计 QPS 时，「调用次数出=入」是核对账单的不变量。
408 延伸：常与「邻接矩阵非零元个数」连考——有向图矩阵非零元=e，无向图=2e（对称矩阵），本质都是本定理的矩阵表述。
易错提醒：选项 D「不确定」极具迷惑性——对任意有向图该等式都成立，并非「有时成立」；个别顶点入度≠出度很正常，但全图求和必然相等。
54. 对于一个有n个顶点、e条边的无向图，用邻接矩阵存储时，矩阵的大小为( )，非零元素个数为( )
标签：【互联网/国企笔试高频】
A. n×n,e B. n×n,2e C. e×e,e D. n×e,2e
答案：B
【结论】 矩阵大小 n×n，非零元素 2e 个，选 B。
【逐项辨析】
- A n×n, e：非零元素算少了 —— 无向图是对称矩阵，每条边对应两个 1。
- B n×n, 2e：正确。 大小由顶点数决定，非零元素由边数 × 2 决定。
- C e×e, e：矩阵大小由顶点数决定，不是边数。
- D n×e, 2e：邻接矩阵必须是方阵，行数 = 列数 = 顶点数。
【知识点】 邻接矩阵的存储规律
A[i][j] = 1 表示存在边 (i, j)
A[i][j] = 0 表示不存在边
无向图:A[i][j] = A[j][i](对称矩阵)→ 非零元素 2e 个
有向图:A[i][j] ≠ A[j][i] → 非零元素 e 个
带权图:A[i][j] 存权值(无边时存 ∞ 或 0)| 维度 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(n²)，与边数无关 | O(n + e) |
| 判断 (i,j) 是否有边 | O(1) | O(deg(i)) |
| 求某顶点所有邻接点 | O(n) | O(deg(i)) |
| 适合 | 稠密图 | 稀疏图 |
【记忆锚点】 “矩阵看顶点（方阵 n×n），无向要对称（非零 2e 个）”。
【易混对比】 注意区分：①矩阵大小只与顶点数有关(n×n);②矩阵非零元素个数与边数有关（无向 2e、有向 e）。这两个问题常在同一道题里同时考查。
【自测】 一个有 5 个顶点、6 条边的有向图，用邻接矩阵存储，矩阵大小和非零元素个数分别是多少？
答：矩阵大小 5×5，非零元素 6 个（有向图不翻倍）。与第 55 题连考。
【知识关联】
- 同库连考：与第 55 题（空间开销上邻接表适合稀疏图）同一决策的两面——本题考矩阵的大小与非零元个数，第 55 题考何时改用邻接表；与第 51/53 题握手定理呼应（无向非零元 2e、有向 e）；与第 57 题（邻接表 BFS O(V+E)，矩阵 O(V²)）相连：存储选择改变算法复杂度。
- 工程实现：稠密图用矩阵便于 Floyd、传递闭包、O(1) 判边；稀疏图用表。带权图矩阵存权值、无边存 ∞；工程上还有邻接多重表、十字链表等针对特殊操作的结构。
- 408 / 国企真题：408「邻接矩阵大小/非零元个数」原题双空：大小恒 n×n，无向非零元 2e、有向 e；国网常给 n、e 具体数字计算。错项套路=把大小算成 e×e 或 n×e（矩阵必须方阵）。
- 面试追问:①「n=5、e=6 的无向图矩阵？」（5×5，非零 12）；②「有向？」（5×5，非零 6）；③「空间复杂度？」（矩阵 O(n²) 与 e 无关，表 O(n+e)）。
【拓展延伸】
变式问法:①「无向图矩阵大小与非零元？」（n×n，2e，本题）；②「有向图？」（n×n，e）；③「邻接矩阵适合？」（稠密图/需 O(1) 判边）。
工程映射：小规模全连接拓扑、距离矩阵、可达性闭包用矩阵；社交/Web 图用邻接表或 CSR 压缩存储。
易错提醒：大小只看顶点数，非零元才看边数；无向对称所以乘 2。带权图非零元统计要小心「权值为 0 的边」的教材约定差异。
55. 在空间开销上，邻接表最适合存储( )的图。
标签：【互联网/国企笔试高频】
A. 稠密图 B. 带权图 C. 完全图 D. 稀疏图
答案：D
【结论】 邻接表最适合存储稀疏图，选 D。
【逐项辨析】
- A 稠密图：邻接矩阵 O(n²) 反而更省（邻接表还要额外存指针），不选。
- D 稀疏图：正确。 邻接表空间 O(n+e),e 远小于 n² 时明显节省空间。
- C 完全图：属稠密图，用邻接矩阵更省。
- B 带权图：带权与否只决定边上是否多存一个权值，与“邻接表 / 邻接矩阵”的空间取舍无关，不构成区分标准。
【知识点】 存储结构的空间对比
邻接矩阵:空间 O(n²) —— 与边数无关,恒为 n×n
邻接表: 空间 O(n + e) —— 与边数相关| 图的类型 | e 的量级 | 邻接矩阵 O(n²) | 邻接表 O(n+e) | 更省的选择 |
|---|---|---|---|---|
| 稀疏图 | e ≪ n² | 浪费大量空间 | 空间小 | 邻接表 |
| 稠密图 | e ≈ n² | 空间合适 | 指针开销大 | 邻接矩阵 |
| 完全图 | e = n(n−1)/2 | 空间合适 | 指针开销大 | 邻接矩阵 |
【记忆锚点】 “边少用表（邻接表），边多用阵（邻接矩阵）”——看边数 e 相对 n² 的大小。
【易混对比】 注意“带权”不是区分标准 —— 邻接表可在结点里多存一个 weight 字段，邻接矩阵可把 1 换成权值，两者都能存带权图。判断选择的标准只有一个：图是稀疏还是稠密。
【自测】 一个有 1000 个顶点、2000 条边的图，用哪种结构更省空间？
答：邻接表。n² = 1,000,000 而 n + e = 3000，邻接表节省约 99.7% 的空间。与第 54 题连考。
【知识关联】
- 同库连考：与第 51 题（无向图度之和=2e，邻接表结点总数=2e）、第 53 题（有向图 Σ入=Σ出=e）共同刻画「边如何被存储结构计数」；与第 64 题（完全图边数）对照——完全图 e=n(n−1)/2 属稠密，正是邻接矩阵的主场；与第 58/63 题（图算法复杂度）相连：BFS/DFS 在邻接表上 O(n+e)，在矩阵上 O(n²)，存储选择直接改变复杂度表达式。
- 工程实现：NetworkX、JGraphT、Neo4j 默认邻接表；Floyd-Warshall 与传递闭包必须邻接矩阵（要 O(1) 判边 + 矩阵乘法语义）；社交网络亿级边却人均关注数百，是典型稀疏图，绝不会用 n×n 矩阵。无向邻接表每条边存两次（两端各一结点），有向只存一次，面试常考这一实现细节。
- 408 / 国企真题：408「图的存储」必考邻接表/邻接矩阵空间对比；国网选择题高频问法：「n 顶点 e 边的图，邻接表空间复杂度」→ O(n+e)，矩阵恒 O(n²)，与 e 无关。
- 面试追问:①「n=1000、e=2000，矩阵要多少存储单元？」（10⁶，邻接表约 3×10³，差三个数量级）；②「带权图邻接表怎么改？」（边表结点加 weight/adjvex 两字段）；③「何时矩阵反超？」（e > n²/log n 或需要频繁判边时）。
【拓展延伸】
变式问法:①「空间开销上邻接表最适合？」（稀疏图，本题）；②「判任意两点是否有边，哪个结构更快？」（矩阵 O(1)；表需扫该点邻接表 O(度)）；③「十字链表/邻接多重表解决什么？」（有向图找入边、无向图高效删边等矩阵与简单邻接表都别扭的操作）。
工程映射：图数据库按边密度自动选存；OSPF 路由器拓扑在区域内部近似稀疏用链式存储，路由计算时再物化；编译器 SSA 依赖图、社交 Feed 图都是「边≪n²」的工程常态。
易错提醒：不要把「带权图」当成选择标准——矩阵存权、表结点加 weight 都可以；判断标准只有 e 相对 n² 的大小。另注意邻接表建表可头插 O(1) 也可尾插保持边序，考试默认头插即可。
56. BFS（广度优先搜索）使用的辅助数据结构是( ),DFS（深度优先搜索）使用的是( )
标签：【互联网/国企笔试超高频】
A. 队列，栈 B. 栈，队列 C. 队列，队列 D. 栈，栈
答案：A
【结论】 BFS 用队列、DFS 用栈，选 A。
【逐项辨析】
- A 队列，栈：正确。 BFS 用队列(FIFO)按层扩展；DFS 用栈(LIFO)深入回溯。
- B 栈，队列：两者颠倒。
- C 队列，队列：BFS 正确，但 DFS 用队列无法实现“深入到底再回溯”。
- D 栈，栈：BFS 用栈会退化成类似 DFS 的遍历，无法保证按层。
【知识点】 BFS 与 DFS 的核心对比（必背）：
| BFS（广度优先） | DFS（深度优先） | |
|---|---|---|
| 辅助结构 | 队列 | 栈（递归实现用系统栈） |
| 遍历方式 | 按层扩展，由近及远 | 沿一条路径深入到底，再回溯 |
| 能否求无权图最短路 | 能 | 不能 |
| 典型应用 | 最短路径（无权）、层序打印 | 拓扑排序、连通分量、迷宫回溯 |
| 邻接表时间复杂度 | O(V+E) | O(V+E) |
BFS 遍历示意(起点 A):
队列:A → 出 A,入 A 的邻接点 B、C → 出 B,入 B 的邻接点 D → ...
访问顺序:A, B, C, D, ... (按层推进)
DFS 遍历示意(起点 A):
栈:A → 出 A,入 B、C → 出 C(栈顶)→ ... → 一条路走到底再回溯
访问顺序:A, C, ..., B, ... (先走深)【记忆锚点】 “BFS 排队（队列）按层走，DFS 堆叠（栈）走到底”。
【易混对比】 与第 26 题（栈 / 队列应用）连考：队列应用含 BFS、进程调度；栈应用含 DFS、递归、括号匹配。BFS 用队列、DFS 用栈是图论模块最高频的记忆点。
【自测】 递归实现的 DFS 使用的是什么栈？
答：函数调用栈（隐式的栈）。每次递归调用把当前状态压栈，返回时弹栈，等价于显式使用栈。与第 26 题连考。
【知识关联】
- 同库连考：与第 57 题（BFS/DFS 时间复杂度 O(V+E)）、第 61 题（BFS 才保证无权图最短路）、第 26 题（栈队列应用）交叉。
- 工程实现:Java 中 BFS 用
ArrayDeque,DFS 用递归栈或显式Stack/Deque；树的层序=BFS。 - 408 / 国企真题:408 与国网必考。
- 面试追问:①「递归 DFS 用什么栈？」（函数调用栈）；②「迭代 DFS 为何用栈？」（模拟递归后进先出）。
【拓展延伸】
完整验算:BFS 按层 → 队列；DFS 走到底再回溯 → 栈。
变式：双端 BFS、迭代加深 DFS、双向 BFS。
工程应用：最短路径、连通分量、拓扑依赖、迷宫、编译期可达性。
57. BFS和DFS的时间复杂度相同，均为( )（设顶点数为V，边数为E，使用邻接表存储）。
标签：【互联网/国企笔试高频】
A. O(V) B. O(E) C. O(V+E) D. O(V×E)
答案：C
【结论】 邻接表存储下 BFS 与 DFS 均为 O(V+E)，选 C。
【逐项辨析】
- A O(V)：只算了顶点访问，漏了边检查。
- B O(E)：只算了边检查，漏了顶点访问。
- C O(V+E)：正确。 每个顶点访问一次 + 每条边检查一次。
- D O(V×E)：这是双重循环的量级，遍历只需单次扫描。
【知识点】 遍历的时间复杂度取决于存储结构:
| 存储结构 | BFS 复杂度 | DFS 复杂度 | 原因 |
|---|---|---|---|
| 邻接表 | O(V+E) | O(V+E) | 每个顶点访问 1 次、每条边检查 1 次 |
| 邻接矩阵 | O(V²) | O(V²) | 找每个顶点的邻接点都要扫一整行 |
为什么邻接矩阵是 O(V²)?
每个顶点都要扫描矩阵中它所在的那一整行(V 个元素)来找邻接点,
共 V 个顶点 × 每行 V 个元素 = O(V²)注意：邻接表下是 O(V+E) 而非 O(V×E) —— 每个顶点只访问一次，每条边最多检查两次（无向图）。
【记忆锚点】 “顶点加边，一次搞定(O(V+E))；矩阵扫行，平方量级(O(V²))”。
【易混对比】 注意 BFS 与 DFS 的时间复杂度相同，差别在空间复杂度与遍历顺序:
| BFS | DFS | |
|---|---|---|
| 时间（邻接表） | O(V+E) | O(V+E) |
| 空间 | O(V)（队列最宽为 O(V)) | O(V)（递归栈最深为 O(V)) |
【自测】 若图用邻接矩阵存储，BFS 和 DFS 的时间复杂度分别是多少？
答：都是 O(V²)。与第 54、55 题连考。
【知识关联】
- 同库连考：与第 56 题（BFS 用队列、DFS 用栈）、第 54/55 题（存储结构与空间）、第 61 题（BFS 才保证无权最短路）、第 60 题（拓扑可用 BFS/DFS）成图算法网；与第 23/26 题（队列应用）衔接。
- 工程实现：大规模图用 CSR/CSC 压缩邻接表；GPU 图计算（GraphBLAS）也基于边列表。面试答复杂度必须先问存储结构——同一 BFS，邻接表 O(V+E)、矩阵 O(V²)。Web 爬虫 BFS、社交一度人脉、网络层 TTL 扫描都是工程 BFS。
- 408 / 国企真题：408「邻接表存储下 BFS/DFS 时间复杂度」标准 O(V+E)；矩阵存储 O(V²)。国网常把两种存储并排设问，错项 O(V×E) 来自误把「每点扫所有边」当成平方级交叉。
- 面试追问:①「为何是 V+E 不是 VE？」（每顶点访问一次，每条边检查 O(1) 次）；②「无向图边检查几次？」（邻接表里每条边出现 2 次，仍是 O(E)）；③「空间复杂度？」（都 O(V) 量级：队列/递归栈+访问标记）。
【拓展延伸】
变式问法:①「邻接表 BFS/DFS 复杂度？」（O(V+E)，本题）；②「邻接矩阵？」（O(V²)）；③「边表存储适合什么算法？」（Kruskal 按边排序）。
工程映射：六度分隔实验、垃圾回收可达性标记、迷宫连通块染色、编译器可达性分析，实现时先确认图如何存储再估复杂度。
易错提醒：题干写「使用邻接表」时答案锁定 O(V+E)；若改成矩阵要会切换到 O(V²)。BFS 与 DFS 时间复杂度相同，差别在遍历顺序与空间/应用场景。
58. Dijkstra算法用于求解( )
标签：【互联网/国企笔试高频】
A. 最小生成树 B. 单源最短路径（无负权边） C. 所有顶点对之间的最短路径 D. 最大流
答案：B
【结论】 Dijkstra 求单源最短路径（无负权边），选 B。
【逐项辨析】
- A错：最小生成树用 Prim 和 Kruskal 算法。
- B 对:Dijkstra 是贪心算法，求带权图单源最短路径，要求无负权边。
- C错：所有顶点对之间的最短路径用 Floyd 算法。
- D错：最大流用 Ford-Fulkerson 等算法。
【知识点】 最短路与最小生成树算法归属（必背）：
| 算法 | 求什么 | 适用条件 | 核心思想 |
|---|---|---|---|
| Dijkstra | 单源最短路径 | 无负权边 | 贪心：每次选距源点最近的未访问顶点 |
| Bellman-Ford | 单源最短路径 | 允许负权边，可判负环 | 对所有边松弛 V−1 轮 |
| Floyd | 多源（所有顶点对）最短路径 | 允许负权边，不允许负环 | 动态规划，三重循环 |
| Prim | 最小生成树 | 无向连通图 | 从顶点出发逐步扩展 |
| Kruskal | 最小生成树 | 无向连通图 | 按边权从小到大选，不成环则加入 |
为什么 Dijkstra 不能处理负权边？ 因为它的贪心前提是“已确定的最近顶点不会再被更短的路径更新”。若存在负权边，后续可能通过负边找到更短的路径，贪心前提被破坏。
【记忆锚点】 “Dijkstra 单源无负权，Floyd 多源三重循环；Prim、Kruskal 求最小生成树”。
【易混对比】 本题最常设的干扰项是“所有顶点对之间的最短路径” —— 那是 Floyd 的职责。另外注意 Prim 与 Kruskal 都是求最小生成树，不是最短路径，这也是高频陷阱（见第 59 题）。
【自测】 若图中存在负权边，应该用哪个算法求单源最短路径？
答：Bellman-Ford（可处理负权边并检测负环）。与第 59 题连考。
【知识关联】
- 同库连考：与第 56 题（BFS 队列 / DFS 栈）、第 57 题（遍历复杂度：邻接表 O(V+E)、邻接矩阵 O(V²)）、第 61 题（遍历说法）对照。
- 工程实现：大规模稀疏图（社交网络）必须邻接表+邻接表 BFS/DFS。
- 408 / 国企真题:408 与国网。
- 面试追问:①「矩阵 BFS 为何 O(V²)？」（找邻居要扫一行）；②「空间？」（矩阵 V²，表 V+E）。
【拓展延伸】
完整验算:
邻接表:每个顶点出边遍历一次 → O(V+E)
邻接矩阵:每个顶点扫 n 行 → O(V²)变式：隐式图（状态空间）用生成邻居函数代替存储。
工程应用：大规模图计算（GraphX、Pregel）用表/压缩稀疏行 CSR。
59. 求最小生成树的算法有( )
标签：【互联网/国企笔试高频】
A. Dijkstra和Floyd B. Prim和Kruskal C. Dijkstra和Bellman-Ford D. DFS和BFS
答案：B
【结论】 求最小生成树用 Prim 和 Kruskal，选 B。
【逐项辨析】
- A Dijkstra 和 Floyd：都是最短路径算法，不是最小生成树。
- B Prim 和 Kruskal：正确。 两者都是求最小生成树的经典算法。
- C Dijkstra 和 Bellman-Ford：也都是最短路径算法。
- D DFS 和 BFS：是图的遍历算法，不用于求最小生成树。
【知识点】 两种最小生成树算法的对比
| Prim 算法 | Kruskal 算法 | |
|---|---|---|
| 核心思想 | 从顶点出发，逐步扩展 | 从边出发，按权值从小到大选 |
| 步骤 | 每次选“连接已选集合与未选集合的最小边” | 每次选权值最小且不成环的边 |
| 时间复杂度 | O(V²)（邻接矩阵） | O(E log E)（排序 + 并查集） |
| 适合 | 稠密图 | 稀疏图 |
| 依赖 | 顶点集合 | 并查集判环 |
Prim(从 A 出发): Kruskal(全局选边):
A → 选最小边连到集合 按权值排序所有边
→ 再选连接内外的最小边 依次选边,用并查集判断是否成环
→ 重复直到包含全部顶点 直到选够 V−1 条边【记忆锚点】 “Prim 加点（顶点起步），Kruskal 加边（边权起步）”。
【易混对比】 三类算法的归属极易混淆，务必分清
| 问题 | 算法 |
|---|---|
| 最小生成树 | Prim、Kruskal |
| 单源最短路径 | Dijkstra、Bellman-Ford |
| 多源最短路径 | Floyd |
“最短路径”与“最小生成树”是两个不同的问题 —— 前者求两点间路径最短，后者求连接所有顶点的边权和最小。这是最常设的干扰项。
【自测】 一个稠密图求最小生成树，用 Prim 还是 Kruskal 更好？
答：Prim。稠密图中 Prim 的 O(V²) 优于 Kruskal 的 O(E log E)（此时 E ≈ V²,log E 较大）。与第 58 题连考。
【知识关联】
- 同库连考：与第 58 题（Dijkstra 最短路）对照 —— MST vs 最短路；与第 52 题（连通图最少 n−1 条边）、第 55 题（稀疏图用邻接表）衔接。
- 工程实现：网络布线、聚类（层次聚类像 Kruskal）、电路设计。
- 408 / 国企真题:408 与国网。
- 面试追问:①「稠密图谁优？」(Prim 邻接矩阵 O(V²));②「稀疏？」（Kruskal 边排序+并查集）。
【拓展延伸】
完整验算:Prim 加点、Kruskal 加边；都得到 MST（权和最小）。
变式:Borůvka；次小生成树；曼哈顿 MST。
工程应用：聚类、网络设计、近似算法。
60. 拓扑排序可以应用于( )
标签：【互联网/国企笔试高频】
A. 无向图 B. 完全图 C. 有向有环图 D. 有向无环图(DAG)
答案：D
【结论】 拓扑排序只能用于有向无环图(DAG)，选 D。
【逐项辨析】
- A错：无向图没有“方向”概念，无法定义拓扑序。
- D 对：拓扑排序只能对 DAG 执行。
- C错：有环图无法进行拓扑排序（环上的顶点无法排出先后）。
- B错：完全图（含环）不能拓扑排序。
【知识点】 拓扑排序的定义与实现
定义:把 DAG 的所有顶点排成一个线性序列,
使每条边 (u, v) 中 u 都出现在 v 之前
实现(Kahn 算法):
1. 统计每个顶点的入度
2. 把所有入度为 0 的顶点入队
3. 出队一个顶点,输出它,并把它的所有邻接点入度减 1
4. 若某邻接点入度变为 0,入队
5. 重复直到队列为空判定环的技巧：若拓扑序列中的顶点数少于总顶点数，说明图中有环。
典型应用：任务调度、课程安排（先修课）、编译依赖解析、AOV 网。
【记忆锚点】 “有向无环才能拓扑，入度为 0 的先出队”。
【易混对比】 AOV 网 vs AOE 网
| AOV 网 | AOE 网 | |
|---|---|---|
| 顶点表示 | 活动 | 事件 |
| 边表示 | 活动间的先后关系 | 活动（带权，表示持续时间） |
| 用途 | 拓扑排序（判断能否顺利完工） | 关键路径（求最短工期） |
【自测】 对一个 DAG 做拓扑排序，得到的序列顶点数少于总顶点数，说明什么？
答：图中有环（存在循环依赖），不是 DAG。与第 62 题连考。
【知识关联】
- 同库连考：与第 62 题（拓扑序不唯一）构成「拓扑」双题——本题考适用对象必须是 DAG，第 62 题考结果可能不唯一；与第 61 题（算法归属：拓扑 vs 最短路/MST）对照，避免把拓扑误套到无向图或带权最短路；与第 56 题（DFS/BFS）相连：DFS 后序逆置也能得到拓扑序，且DFS 遇到回边即可判环。
- 工程实现：Maven/Gradle 构建依赖、Java 模块系统（module-info requires）、Webpack 模块图都要先拓扑排序再执行；
make的目标依赖解析同理。工程上若拓扑序顶点数 < 总顶点数，直接报「存在循环依赖」——这正是本题「有环不能拓扑」的工程化用法。 - 408 / 国企真题：408 图章「拓扑排序适用于」原题高频，标准答案永远是「有向无环图」；国网「AOV 网」考点常与关键路径（AOE 网）成对出现，区分点是：AOV 顶点=活动用拓扑，AOE 边=活动用关键路径。
- 面试追问:①「课程表问题怎么判能否修完？」（建有向图做拓扑，顶点数不够=有先修环）；②「Kahn 与 DFS 两种拓扑实现的差异？」（Kahn 用入度队列易判环；DFS 用 finish 时间逆置，见回边即有环）；③「无向图为什么不能拓扑？」（边无方向，不存在「谁先谁后」的约束语义）。
【拓展延伸】
变式问法:①「拓扑排序可用于？」（有向无环图，本题）；②「下列哪种图一定存在拓扑序？」（DAG）；③「拓扑排序能否用于检测有向图是否有环？」（能：输出顶点数少于 n 即有环）。
工程映射：任务调度器（Airflow DAG）、数据库事务死锁检测（等待图找环）、编译器头文件 include 解析、CI 流水线 stage 编排，全是「DAG + 拓扑」的工业实例。
易错提醒：选项 B「完全图」易误选——完全图默认无向或含双向边，必有环，不能拓扑；C「有向有环图」正是拓扑要排除的对象。另：拓扑排序只要求 DAG，不要求连通，森林也可拓扑。
61. 以下关于图的遍历，说法正确的是( )
标签：【互联网/国企笔试常考】
A. BFS一定能找到最短路径（无权图） B. DFS一定能找到最短路径 C. BFS只能用于连通图 D. DFS只能用于有向图
答案：A
【结论】 无权图中 BFS 一定能找到最短路径，选 A。
【逐项辨析】
- A 对：无权图（或等权图）中 BFS 按层遍历，第一次到达目标节点时经过的路径就是最短路径（经过的边数最少）。
- B 错：DFS 沿一条路径深入，不能保证找到最短路径。
- C 错：BFS 也能用于非连通图（对每个连通分量分别执行）。
- D 错：DFS 可用于有向图和无向图。
【知识点】 BFS 求无权图最短路径的原理
BFS 按层访问:
第 1 层:距源点 1 条边的所有顶点
第 2 层:距源点 2 条边的所有顶点
...
第 k 层:距源点 k 条边的所有顶点
第一次访问到目标顶点时,它必然处于"最早出现的层",
即边数最少的那条路径 → 最短路径 ✓示例:求 A 到 E 的最短路径(边数最少)
A ──── B ──── D
│ │
C ────────── E
BFS 从 A 出发:第 1 层 {B, C},第 2 层 {D, E}
E 在第 2 层被首次访问 → 最短路径长度 = 2(A→C→E) ✓注意：若图带权（边权不等），BFS 不再保证最短路，此时要用 Dijkstra 算法。
【记忆锚点】 “无权图找最短路，BFS 按层第一次到达就最短”。
【易混对比】 BFS 与 DFS 的适用面
| 问题 | BFS | DFS |
|---|---|---|
| 无权图最短路 | ✅ | ❌ |
| 带权图最短路 | ❌（用 Dijkstra） | ❌ |
| 连通分量 / 判连通 | ✅ | ✅ |
| 拓扑排序 | ✅（入度法） | ✅（DFS 逆后序） |
【自测】 带权图中求最短路径，能用 BFS 吗？
答：不能（除非所有边权相等）。带权图需用 Dijkstra（无负权）或 Bellman-Ford（允许负权）。与第 58 题连考。
【知识关联】
- 同库连考：与第 56/57 题（BFS/DFS 容器与复杂度）、第 59 题（MST 不是最短路）、第 60/62 题（拓扑）构成图算法决策表；与第 23/26 题（BFS 用队列）衔接。
- 工程实现：无权网格最短路（游戏四方向走格子、迷宫最少步）用 BFS；带权地图导航用 Dijkstra/A*；社交「几度人脉」是无权 BFS 层号。工程题先判「边权是否等价」再选算法。
- 408 / 国企真题：408「BFS 可用于求哪类图的最短路径」标准答案无权图/边权相等；干扰项「任意图最短路」错误。国网还考「非连通图能否 BFS」——能，对每个连通分量各做一次。
- 面试追问:①「BFS 为何无权最短？」（按层扩展，层号=边数距离）；②「带权为何不行？」（层≠权和，短边数路径可能总权更大）；③「0-1 BFS？」（双端队列处理边权仅 0/1 的特殊最短路）。
【拓展延伸】
变式问法:①「无权图最短路？」（BFS，本题）；②「带权非负？」（Dijkstra）；③「有负权？」（Bellman-Ford/SPFA）。
工程映射：路由器跳数、地铁最少换乘（换乘次数可作边权）、网络爬虫按层抓取、DNS 解析跳数限制。
易错提醒：选项 A 必须带「无权图」前提；若题干去掉「无权」二字则说法不严谨。C「BFS 只能用于连通图」错——非连通可多次 BFS。
62. 对于一个有向无环图(DAG)，拓扑排序的结果是( )
标签：【互联网/国企笔试常考】
A. 唯一的 B. 可能不唯一 C. 一定不存在 D. 只有一个
答案：B
【结论】 拓扑排序结果可能不唯一，选 B。
【逐项辨析】
- A 唯一的 / D 只有一个：只有在极特殊情况下才唯一（存在哈密顿路径），一般情况下不唯一。
- B 可能不唯一：正确。 当多个顶点入度同时为 0 时，它们的相对顺序可以任意。
- C 一定不存在：拓扑排序一定存在（只要图是 DAG）。
【知识点】 拓扑排序不唯一的例子
图:A → B, A → C(B、C 之间无边)
A 入度为 0,B、C 入度都为 1
合法拓扑序列:
A, B, C ✓
A, C, B ✓
两种都合法 → 不唯一唯一性条件：当且仅当图中存在一条经过所有顶点的路径（哈密顿路径）时，拓扑序列才唯一。
唯一的情形:A → B → C → D(链)
每个时刻只有一个入度为 0 的顶点 → 拓扑序列唯一:A, B, C, D【记忆锚点】 “谁入度为 0 谁先出；同时有多个 0，顺序就自由”。
【易混对比】 注意与“最小生成树不唯一”对照 —— 当图中存在相同权值的边时，最小生成树也可能不唯一。这两个“不唯一”是图论中常被一起考查的性质。
【自测】 什么情况下拓扑序列唯一？
答：当图中存在一条哈密顿路径（经过所有顶点的路径）时，拓扑序列唯一。与第 60 题连考。
【知识关联】
- 同库连考：与第 60 题（拓扑只能用于 DAG）是同专题的「适用性 vs 唯一性」两问；与第 59 题（求 MST 用 Prim、Kruskal）——「等权边时 MST 可能不唯一」见本题【易混对比】对照记忆图论两个「不唯一」；与第 56 题（DFS/BFS）相连：不同起点、邻接表不同的边序，都可能得到不同拓扑序。
- 工程实现：构建工具并行编译时，同一拓扑层内任务可乱序并行，层数决定关键路径长度——这正是「拓扑序不唯一」的工程红利；Kafka 分区内消息有偏序，跨分区无全序，类比「只约束相对先后」。LeetCode 210「课程表 II」要求返回任意一个合法拓扑序，题面就体现了不唯一。
- 408 / 国企真题：408 与国网常考判断题「AOV 网的拓扑排序结果唯一」——错；唯一性充要条件是「存在哈密顿路径 / 全序链」，属于进阶辨析项。
- 面试追问:①「拓扑排序唯一吗？」（不一定；多个入度 0 时相对顺序任意）；②「什么时候唯一？」（任意时刻入度 0 的顶点至多 1 个，等价于存在经过所有顶点的路径）；③「如何输出字典序最小的拓扑序？」（把入度 0 顶点放进最小堆/优先队列，而不是普通队列）。
【拓展延伸】
变式问法:①「DAG 的拓扑排序结果？」（一定存在，可能不唯一，选 B）；②「下列哪个图拓扑序唯一？」（一条链 A→B→C→D）；③「拓扑序不唯一是否说明算法错了？」（不，任一合法序都正确）。
工程映射：包管理器解析依赖时给出的安装顺序可以不同但都合法；并行 make -j 在无依赖任务间调度顺序也不固定；死锁预防中的资源有序分配，则是人为强制一个全序来消除环。
易错提醒：选项 C「一定不存在」把话说反了——DAG 一定存在拓扑序，这是定理；A/D 把「可能不唯一」夸大成「唯一」。答题时区分「存在性」（DAG 必有）与「唯一性」（一般没有）。
63. 关键路径是AOE网中( )
标签：【互联网/国企笔试常考】
A. 最短的路径 B. 最长的路径 C. 任意一条路径 D. 边数最少的路径
答案：B
【结论】 关键路径是 AOE 网中最长的路径，选 B。
【逐项辨析】
- A 最短的路径：关键路径不是最短路径。
- B 最长的路径：正确。 从源点到汇点的最长路径。
- C 任意一条路径：只有最长的那条（可能有多条）才是关键路径。
- D 边数最少的路径：关键路径看的是权值之和（时间），不是边数。
【知识点】 AOE 网与关键路径
AOE 网(Activity On Edge):
顶点 = 事件(状态)
边 = 活动,边权 = 活动持续时间
源点 = 入度为 0 的顶点(工程开始)
汇点 = 出度为 0 的顶点(工程结束)| 概念 | 含义 |
|---|---|
| 关键路径 | 从源点到汇点的最长路径 |
| 关键活动 | 关键路径上的活动 |
| 关键路径长度 | 工程的最短完成时间 |
| 最早开始时间 e(i) | 活动 i 最早可以开始的时间 |
| 最晚开始时间 l(i) | 不推迟整个工期的前提下最晚开始的时间 |
| 判据 | e(i) = l(i) 的活动是关键活动 |
为什么"最长路径"决定"最短工期"?
关键路径上的活动必须依次串行完成,总时间 = 各关键活动时间之和。
其他路径耗时更短,可以并行,不会拖慢总工期。
所以工程最快完成时间 = 关键路径长度。【记忆锚点】 “关键路径最长，却决定工期最短”——这是最容易被绕晕的一对概念。
【易混对比】 关键路径可能不唯一（存在多条等长的最长路径时），此时缩短工期必须同时缩短所有关键路径上的活动。另注意：缩短某个关键活动的时间，可能使原关键路径不再是关键路径（新的最长路径可能转移到别处）。
【自测】 若 AOE 网中某活动的 e(i) = l(i)，说明什么？
答：说明该活动是关键活动，位于关键路径上，它的延迟会直接导致整个工程延期。与第 60 题（AOV/AOE 区别）连考。
【知识关联】
- 同库连考：与第 60 题（AOV 网用拓扑排序）对照——AOV 顶点=活动，AOE 边=活动；与第 62 题（拓扑序不唯一）、第 57 题（遍历复杂度）同属图应用；关键路径与拓扑排序常在同一道综合题出现（先拓扑，再正推/反推求 e(i)、l(i)）。
- 工程实现：项目管理（甘特图、关键链）、芯片时序收敛、构建系统里「最长依赖链决定最短完成时间」、数据管道 stage 耗时分析，都是 AOE/关键路径思想。缩短工期要压缩所有关键路径上的活动，否则关键路径会转移到次长路径。
- 408 / 国企真题：408「关键路径是 AOE 网中源点到汇点的最长路径」原题；国网/银行常考判断「关键路径是最短路径」——错，它是权值和最长，却对应工程最短工期。计算题给 AOE 求关键活动 e=l。
- 面试追问:①「为何最长路径决定最短工期？」（关键活动无法并行，其他路径可并行不拖后腿）；②「e(i)=l(i) 说明？」（关键活动，无富余时间）；③「缩短一个关键活动工期一定缩短总工期？」（不一定，若有多条关键路径）。
【拓展延伸】
变式问法:①「关键路径是？」（AOE 网中最长路径，本题）；②「关键路径长度等于？」（工程最短完成时间）；③「AOV 与 AOE 区别？」（顶点活动 vs 边活动；拓扑 vs 关键路径）。
工程映射：软件发布流水线的关键阶段、施工网络计划 PERT/CPM、CPU 指令流水冒险延迟分析。
易错提醒：「最长」与「最短工期」是一对概念，选择题最爱反着说；D「边数最少」错在关键路径看权值之和不是边数。
64. n个顶点的有向完全图有( )条边。
标签：【互联网/国企笔试常考】
A. n(n-1)/2 B. n²-1 C. n² D. n(n-1)
答案：D
【结论】 有向完全图有 n(n−1) 条边，选 D。
【逐项辨析】
- A n(n−1)/2：这是无向完全图的边数，少了“方向”这一维度。
- D n(n−1)：正确。 有向完全图中每对顶点之间有两条方向相反的边。
- C n²：多算了 n 条（完全图的定义中不含自环）。
- B n²−1：无依据。
【知识点】 完全图的边数（必背）：
| 图类型 | 边数 | 推导 |
|---|---|---|
| 无向完全图 | n(n−1)/2 | 从 n 个顶点中选 2 个：C(n,2) |
| 有向完全图 | n(n−1) | 每对顶点有两条方向相反的边 |
推导:无向完全图
任意两个顶点之间都有一条边,即从 n 个顶点中任选 2 个的组合数
C(n, 2) = n(n−1)/2
有向完全图:每对顶点之间有 2 条边(双向)
2 × n(n−1)/2 = n(n−1)| n | 无向完全图边数 | 有向完全图边数 |
|---|---|---|
| 3 | 3 | 6 |
| 4 | 6 | 12 |
| 5 | 10 | 20 |
【记忆锚点】 “无向要除以 2，有向不除”——因为无向边 (u,v) 与 (v,u) 是同一条，有向边是两条。
【易混对比】 注意“完全图”不含自环：若允许自环，边数会再多 n 条（即 n²）。本题选项 C(n²)正是针对“忘记排除自环”设置的陷阱。
【自测】 有 6 个顶点的无向完全图有多少条边？有向完全图呢？
答：无向 6×5/2 = 15 条；有向 6×5 = 30 条。与第 52 题连考。
【知识关联】
- 同库连考：与第 52 题（无向连通最少边 n−1）、第 55 题（稀疏用邻接表）同属「图规模计算」；与第 51/53 题握手定理呼应——无向完全图度之和=2e=n(n−1)，有向完全图入度之和=出度之和=e=n(n−1)；与第 57 题（邻接表下 BFS/DFS 为 O(V+E)）统一符号。
- 工程实现：NetworkX/Neo4j 在稠密小图上可选矩阵加速；Floyd 的 O(V³) 与「完全图 e≈V²」的规模感一致。邻接矩阵在有向完全图上无空洞（除对角线），空间利用率 100%；稀疏图矩阵则几乎全是 0。JDK 无图容器，笔试只需记公式。
- 408 / 国企真题：408「完全图边数」必背两公式；国网常考变体：「n 个顶点的无向完全图有多少条边？有向呢？」或结合连通性问「至少加几条边变成完全图」（补边数 = n(n−1)/2 − 已有边数）。
- 面试追问:①「n=8 有向完全图多少边？」（8×7=56）；②「含自环的有向图最多多少边？」（n²，本题选项 C 的陷阱来源）；③「竞赛图是什么？」（每对顶点恰一条有向边，边数同无向完全图 n(n−1)/2）。
【拓展延伸】
变式问法:①「有向完全图边数？」（n(n−1)，本题）；②「无向完全图边数？」（n(n−1)/2）；③「n 顶点无向图至少再加多少边变完全？」（C(n,2)−e）。
工程映射：全连接拓扑（数据中心 leaf-spine 全互联、n 台主机两两加密通道）的成本按完全图边数估算；社交「可能认识的人」补边也可看作向完全图逼近。
易错提醒：默认完全图不含自环——C 选项 n² 是「允许自环」时的边数，多算的正是 n 条对角线。另：有向完全图每对顶点是两条反向边，不要除以 2。