Code59 零基础 · 图 · 42—52¶
先读 第 0 课，再按每题“完整题干与条件 → 输入输出示例 → 人话讲解与状态推演 → 完整函数与逐句说明 → 自测”学习。题干整理和教学补充分别标注，原速查内容放在每题最后。
本篇对应全书第 42—52 题。记 V 为顶点数、E 为边数；邻接表遍历通常 O(V+E)，邻接矩阵扫描通常 O(V²)。题意为转述，例子为本次补充；每题直接附完整函数，来源仍链接正式稿。除 Floyd 外，本章矩阵按 0 无边、非 0 有边；Floyd 的无边必须用 INF，二者不可混用。
先弄明白：图的“暴力”不是一个专门算法¶
暴力是一种解题策略：把可能的候选逐一尝试，再验证是否合格。例如“找所有根”，就让每个顶点都当一次候选根，每次用 DFS 检查它能否到达全图。外层逐个试是枚举，内层 DFS 是验证工具。
DFS 是沿着一条分支深入再返回，BFS 是一层一层向外扩展；它们本身不是“低级方法”。在单次可达性问题中，遍历已经是自然的高效解法。Floyd 虽有三层循环，却是有明确状态含义的动态规划，不是枚举所有路径。
这 11 题先学四组基础：邻接表/矩阵与度数；DFS/BFS 和 visited；连通、树、欧拉通路的条件；拓扑排序与 Floyd 的状态更新。最小生成树、Dijkstra 等仍是 408 图章节内容，只是不在这 11 题中，不能据此当成不考。
读代码前：编译环境与类型¶
本章展示的是完整函数，不是每题各有一个 main 的独立程序。练习编译一题时，将所需类型、辅助函数与题目函数放在同一份学习用 C 文件里，再添加调用它的 main；第 0 课给了最小程序例子。常用标准头文件如下（它们提供打印、分配空间、真假类型、整数上限）：
以下是本章使用的类型定义，不是要执行的解题步骤。字段含义见第 0 课；不要把不同章节重复的同名类型在同一文件中再定义多次。
typedef struct ArcNode {
int adjvex;
struct ArcNode *nextarc;
} ArcNode, *ArcPtr;
typedef struct {
char data;
ArcNode *firstarc;
} VertexNode;
typedef struct {
VertexNode adjList[MAXSIZE];
int numVertices;
int numEdges;
} Graph;
/**/ #define INF INT_MAX
typedef struct {
char vertex[MAXSIZE];
int edge[MAXSIZE][MAXSIZE];
int numVertices;
int numEdges;
} MatrixGraph;
42｜离起点最远的一个顶点（本章第 1 题）¶
题目与要求¶
题目（依据原题整理）：给定一个无向连通图和起点 v，设计一个算法，求出与 v 距离最远的一个顶点。
已知条件：本题按无权图处理，每条边走一步；两顶点之间的距离指最短路径包含的边数。图连通，所以每个顶点都能从 v 到达。
需要得到：距离 v 最远的一个顶点编号；最远点不唯一时，返回其中任意一个即可。
输入 → 输出示例（教学补充）：顶点为 0、1、2、3，无向边为 0—1、0—2、2—3，起点为 0 → 距离依次为 0、1、1、2，返回顶点 3。
约定与提醒（教学补充）：原题简称“路径长度最大”，本节根据原解 BFS 明确为“最短距离中的最大值”，不是寻找绕路最长的路径。带权图不能直接用这里的每边一步；输入顶点编号必须合法。
题干回源：Code59 PDF 第 20 页；回源 · PDF 第 20 页 · b_20_7；PDF 第 20 页 · b_20_8；PDF 第 20 页 · b_20_9
。
1. “离得最远”先把距离的意思说清¶
把顶点看成地点，每条无权边算一步。某地点的距离是从起点到它最少走几步，题目要这些最短距离中最大的一个。它不是让你故意绕远路求最长路径。
输入无向连通图与起点 A；图的边为 A-B、A-C、B-D、C-E、E-F；输出 F。图里每个顶点在代码中用整数编号表示，A 等字母只是帮助看图。
2. 像水波扩散，一圈一圈发现¶
| 出队处理谁 | 新发现并排到队尾 | 操作后的待处理队列 | last |
|---|---|---|---|
| 初始 | A 先入队 | A | A |
| A | B、C | B、C | A |
| B | D | C、D | B |
| C | E | D、E | C |
| D | 无 | E | D |
| E | F | F | E |
| F | 无 | 空 | F |
距离层次是 A 为 0，B/C 为 1，D/E 为 2，F 为 3。最后出队的是最远层中的一个；同层有多个最远点时，不承诺特定是哪一个。
3. 完整函数与逐句说明¶
代码段 1¶
int farthestVertexByBFS(Graph G, int start) {
bool visited[MAXSIZE] = {false};
int queue[MAXSIZE];
int front = 0, rear = 0;
int last = start;
visited[start] = true;
queue[rear++] = start;
while (front < rear) {
int v = queue[front++];
last = v;
for (ArcPtr p = G.adjList[v].firstarc;
p != NULL; p = p->nextarc) {
int w = p->adjvex;
if (!visited[w]) {
visited[w] = true;
queue[rear++] = w;
}
}
}
return last;
}
visited 清成 false，表示还没发现；queue 存待处理编号；front/rear 清零；last 先设起点，保证只有单顶点时也有答案。给起点做标记并入队。
while 队列非空时，取队首 v、令 last=v。for 从 G.adjList[v].firstarc 出发遍历 v 的每条出边；p 是边结点地址，p->adjvex 才是目的顶点编号 w。若 w 没发现过，先标记再入队，防止另一个前驱又把同一个 w 重复排队。
所有待处理点做完后队列空，交回最后处理的 last。这里不需要专门记录每点距离，因为 BFS 队列已经按距离非递减顺序组织好了访问。
4. 自己试与为何不是 DFS 最后一个¶
如果 A 的一支通向很远的 D，另一支只有近邻 C，DFS 可能先走完深支再最后访问 C，所以“最后访问”不自动代表远。练习星形 A 连 B、C、D：三个距离都为 1，返回其中任一都对。不同权值道路下“边数少”不等于“总路程短”，本法前提不能丢。
学懂后回看：结论、复杂度与回源¶
题意与结论：无权无向连通图中，距离指最短路径边数。做 BFS，最后一个出队顶点位于最远层，返回它即可。
思路推导：BFS 先访问距离 0 的起点，再访问距离 1、2……的顶点，所以最后处理的那层距离最大。这里求的是“各点到起点的最短距离中最大者”，不是找最长简单路径。
走一遍：边为 A-B、A-C、B-D、C-E、E-F。从 A 出发，各层为 [A]、[B,C]、[D,E]、[F]。F 最后出队，距离为 3，返回 F。如果最远层有两个顶点，返回其中任意一个都符合题意。
代码抓手与正确性：visited[start]=true 后入队；每次出队令 last=v；新邻接点在入队时就标记，避免被多个前驱重复入队。首次入队时已找到最少边数的路径，因此最后出队对应最大最短距离。
复杂度与易错点：邻接表时间 O(V+E)，空间 O(V)。若图不连通，这只能找起点所在连通分量内的最远点；若边有不同权值，BFS 层数不再等于最短加权距离。DFS 最后访问的点不保证最远，例如走完很深的一支再访问起点的近邻。
回源：PDF 第 20 页；回源 · PDF 第 20 页 · b_20_7；PDF 第 20 页 · b_20_8；PDF 第 20 页 · b_20_9
。正式代码
43｜有向图两顶点间是否有路径（本章第 2 题）¶
题目与要求¶
题目（依据原题整理）：有向图采用邻接表存储，设计一个算法，判断从顶点 Vi 到顶点 Vj 是否存在路径。
已知条件：输入图、起点和终点；边有方向，行走时只能沿箭头方向前进。
需要得到：能从起点到终点返回真，否则返回假；本题不要求列出路径或计算最短距离。
输入 → 输出示例（教学补充）：图中只有边 0→1、1→2 → 查询 0 到 2 返回真，查询 2 到 0 返回假。
约定与提醒（教学补充）：把箭头反着走不能算可达。下面代码把顶点到自身视为可达，即允许长度为 0 的路径；DFS 与 BFS 都可完成本题，均需避免在环里反复访问。
题干回源：Code59 PDF 第 21 页；回源 · PDF 第 21 页 · b_21_0；PDF 第 21 页 · b_21_3
。
1. 判断能不能到，不要求列出所有走法¶
输入有向边 A→B、B→C、C→B、A→D。问 A 能到 C 吗，答案真；问 D 能到 C 吗，答案假。箭头只能顺着走。
start 是出发点，target 是目标，current 是 DFS 本次到达的地方。visited 记哪些地方已经探索过，遇到 C→B→C 这种环时，不再无限绕圈。
2. 两种遍历，都可以完成同一个判断¶
DFS 从 A 开始：标 A，走到 B，标 B，走到 C；C 正好是目标，交回 true，B 收到后交回 true，A 再交回 true。它找到一条就够，不必再去 D。
BFS 从 A 开始：队列 A；处理 A，B、D 入队；处理 B，C 入队；处理 D，没新点；处理 C，命中目标，返回 true。
| 找 C→A 的 DFS | 当前情况 | 为什么继续/停止 |
|---|---|---|
| 到 C | 不是 A，标记 C | 可去 B |
| 到 B | 不是 A，标记 B | 下一边去 C，但 C 已标 |
| B 没有未查出边 | 返回 false | C 也再无新路 |
| 回到 C | 返回 false | 没有到 A 的有向路径 |
3. 完整函数与逐句说明¶
代码段 1¶
bool reachableDFSImpl(Graph G, int current, int target,
bool visited[]) {
if (current == target)
return true;
visited[current] = true;
for (ArcPtr p = G.adjList[current].firstarc;
p != NULL; p = p->nextarc) {
int next = p->adjvex;
if (!visited[next] && reachableDFSImpl(G, next, target, visited))
return true;
}
return false;
}
bool reachableDFS(Graph G, int start, int target) {
bool visited[MAXSIZE] = {false};
return reachableDFSImpl(G, start, target, visited);
}
代码段 2¶
bool reachableBFS(Graph G, int start, int target) {
bool visited[MAXSIZE] = {false};
int queue[MAXSIZE];
int front = 0, rear = 0;
queue[rear++] = start;
visited[start] = true;
while (front < rear) {
int v = queue[front++];
if (v == target)
return true;
for (ArcPtr p = G.adjList[v].firstarc;
p != NULL; p = p->nextarc) {
int w = p->adjvex;
if (!visited[w]) {
visited[w] = true;
queue[rear++] = w;
}
}
}
return false;
}
DFS 的辅助函数先判断当前是否就是目标，命中直接返回真；否则标记当前，逐条读出边得到 next。条件 !visited[next] && reachableDFSImpl(...) 表示“这个点还没查，而且从它递归能到目标”；成立就向上传 true。所有出边都没成功，才走到函数末 return false。外面的包装函数每次创建一份全新的 visited，再启动递归。
BFS 版本先初始化队列并标起点。每次取出 v 先检查目标；不是目标就扫描邻接点，未访问的标记并入队。while 全部处理完仍没命中才返回 false，不是在一个邻居没命中时就提前判失败。
4. 自己试一下¶
输入 A→B，只问 B→A：不能逆向，答案假。问 A→A：正式函数立即为真，采用允许长度 0 的可达性定义；若题目问“必须至少走一条边还能回原点”，那是另一件事。每次新查询重置 visited，不能把上次遍历的痕迹当本次已探索。
学懂后回看：结论、复杂度与回源¶
题意与结论：从 start 沿出边做 DFS 或 BFS，能访问到 target 就为真；把所有可达点都查完还没找到，则为假。
思路推导：不需要枚举每一条可能路径。一个顶点是否已探索过可以共享记录：第二次到达同一点，不会带来新的后续可达点，因此用 visited 跳过。
走一遍：有边 A→B、B→C、C→B、A→D。找 A 到 C：DFS 可走 A→B→C，成功返回；找 D 到 C：D 无出边，直接失败。找 C 到 A 时会经过 C→B，但 B 再指回已访问的 C，不再递归，最终失败。
代码抓手与正确性：DFS 在进入当前顶点后标记，递归某邻居返回 true 时立即向上传 true；BFS 在入队时标记，出队时检查是否为目标。遍历探索所有可达邻居，不漏任何可达点，又靠 visited 避免环上无限重复。
复杂度与易错点：邻接表最坏时间 O(V+E)、空间 O(V)。有向路径不能逆着箭头走。每次独立查询要清空 visited。正式代码 start==target 返回 true，按允许长度 0 的可达性处理；若题目要求非空路径回到自身，那是另一个判定。
回源：PDF 第 21 页；回源 · PDF 第 21 页 · b_21_0；PDF 第 21 页 · b_21_3；PDF 第 21 页 · b_21_6；PDF 第 21 页 · b_21_1；PDF 第 21 页 · b_21_7；PDF 第 21 页 · b_21_8
。正式代码
44｜输出有向图全部根（本章第 3 题）¶
题目与要求¶
题目（依据原题整理）：在有向图中，如果从顶点 r 到图中所有顶点都存在路径，就称 r 为图的根结点。编写算法，输出给定有向图的所有根结点。
已知条件：输入采用邻接表存储的有向图；“根”必须按本题的可达性定义判断。
需要得到：输出每一个满足条件的顶点，可能有一个、多个，也可能一个都没有。
输入 → 输出示例（教学补充）：顶点 0、1、2，边为 0→1、1→0、1→2 → 输出根顶点 0、1；顶点 2 不能到达其他顶点，不能输出。
约定与提醒（教学补充）：图的根不等于“入度为 0”，示例中的两个根入度都不为 0。本题也不要求输入是一棵树；每个顶点按约定可到达自身。
题干回源：Code59 PDF 第 21 页；回源 · PDF 第 21 页 · b_21_2
。
1. 这里的“根”不是画在图最上面的点¶
定义是：从 r 出发，顺箭头能到达全部顶点，r 就是根。不要求入度为 0，也不要求只有一个。
输入 A→B、B→A、B→C。输出 A、B。直观做法就是逐一提名 A、B、C，然后分别验证；这叫枚举，也就是本题可以说的“暴力试候选”。验证过程用 DFS，DFS 不是“暴力”这个词的同义词。
2. 一名候选对应一张新的签到表¶
| 本轮候选 start | 从它可走到哪些点 | visited[A,B,C] | 是否输出 |
|---|---|---|---|
| A | A→B，再由 B 到 C | 真、真、真 | A 是根 |
| B | B→A，同时 B→C | 真、真、真 | B 是根 |
| C | 只有 C | 假、假、真 | 不输出 C |
如果沿用第一轮的 visited，到 C 时表里仍全真，会把 C 错当根。因此“每轮清空”是正确性的必要步骤，不是为了代码整洁。
3. 完整函数与逐句说明¶
代码段 1¶
void markReachable(Graph G, int v, bool visited[]) {
visited[v] = true;
for (ArcPtr p = G.adjList[v].firstarc;
p != NULL; p = p->nextarc) {
if (!visited[p->adjvex])
markReachable(G, p->adjvex, visited);
}
}
void printAllRootVertices(Graph G) {
for (int start = 0; start < G.numVertices; start++) {
bool visited[MAXSIZE] = {false};
markReachable(G, start, visited);
bool reachesAll = true;
for (int v = 0; v < G.numVertices; v++) {
if (!visited[v]) {
reachesAll = false;
break;
}
}
if (reachesAll)
printf("%d ", start);
}
}
markReachable 不返回真假，它的工作是把所有能到的顶点对应标记写成 true；标当前后，沿每条未访问邻居继续递归。共享同一个 visited 数组，所以各分支能看到彼此已经探索过的点。
外层 for 把 start 从 0 试到 V-1；每轮在循环内部新建清零的 visited，再调用标记函数。reachesAll=true 先暂认合格，内层逐一检查，只要发现一个 false，就改为 false 并 break。最后只有仍为 true 才 printf 当前 start 的编号。
4. 自己试与工作量¶
若图完全强连通，每个点都能到全部点，每个点都输出。若 A→B 且另有孤立 C，没有根。不是所有入度 0 的点都合格。
一次 DFS 大致看 V 个点和 E 条边；V 个候选各做一次，乘起来是 V×(V+E)。不是“DFS 一次线性，所以整题也线性”。先掌握这套可执行方法，再考虑强连通分量优化。
学懂后回看：结论、复杂度与回源¶
题意与结论：从 r 能到达所有顶点，就称 r 为本题的根。逐个顶点当起点做遍历，访问全图的起点全部输出。这就是本组里很典型的“枚举候选＋验证”。
思路推导：先解决简单问题“这个 r 是不是根”：DFS 后看 visited 是否全真。再把 r 从 0 到 V-1 逐个试。不要一上来试图背复杂优化，先把这个完整可用的解法掌握。
走一遍：有边 A→B、B→A、B→C。从 A 可到 A、B、C，输出 A；清空 visited 后从 B 也能到全图，输出 B；再从 C 只能到 C，不输出。答案有两个根，不一定唯一。
代码抓手与正确性：外层每换一个 start 都要重新清零 visited；markReachable 标记该起点的可达集合；之后检查每个标记。枚举覆盖所有候选、验证又与根定义完全一致，所以不会漏根或错收。
复杂度与易错点：一次遍历加检查 O(V+E)，共 V 次，时间 O(V(V+E))，空间 O(V)。根不等于“入度为 0 的点”：本例 A、B 入度都不为 0，却都是根；两个互不连通的孤立点入度都是 0，却都不能覆盖全图。强连通分量可用于更快求解，但不属于正式代码的这套方法。
回源：PDF 第 21 页；回源 · PDF 第 21 页 · b_21_2；PDF 第 21 页 · b_21_4；PDF 第 21 页 · b_21_9
。正式代码
45｜无向连通图是否存在 EL 路径（本章第 4 题，2021）¶
题目与要求¶
题目（依据原题整理）：已知无向连通图 G=(V,E)，且 |E|>0，采用邻接矩阵存储。若存在一条包含所有边、长度恰为 |E| 的路径，称为 EL 路径。已知当奇度顶点个数为不大于 2 的偶数时存在这种路径，设计算法判断：存在返回 1，否则返回 0。
已知条件：图已经保证连通且至少有一条边；顶点的度是与它连接的边数。
需要得到：只判断有没有恰好经过每条边一次的走法，不要求输出具体走法。
输入 → 输出示例（教学补充）：无向边为 0—1、1—2 → 可走 0—1—2，返回 1；中心 0 分别连 1、2、3 的三叉星形图 → 返回 0。
约定与提醒（教学补充）：每条边恰好一次，不是每个顶点恰好一次；可以重复经过顶点。下面矩阵计度按无自环、无重边的简单图使用，不能把边权相加当作度；不连通图不满足题设。
题干回源：Code59 PDF 第 22 页；回源 · PDF 第 22 页 · b_22_0
。
1. EL 路径是“每条边恰好走一次”¶
可以多次经过同一个顶点，但不能漏边或重复走边。它和“每个顶点恰好一次”不是同类限制。题设已经给无向连通图，且至少有一条边。
这题只问有没有，不要求真的把路线写出来。统计每个顶点接了多少条边，奇数度顶点有 0 个或 2 个就存在。
2. 用进门、出门理解为什么关注奇偶¶
在路线中间到达一个顶点，要再离开它，通常一次进入配一次离开，使用的边成对。若起终点不同，只有起点可多一条离开边、终点多一条进入边，因此两个端点为奇度；若起终点同一处，所有边都能成对。
| 例子 | 每点度数 | 奇度点数 | 存在吗 |
|---|---|---|---|
| A-B-C-D | 1、2、2、1 | 2 | 存在，A 走到 D |
| 三角形 | 2、2、2 | 0 | 存在，绕一圈回起点 |
| 中心 A 连 B、C、D | 3、1、1、1 | 4 | 不存在 |
前面解释给出必要性；连通无向图下“0 或 2 也足够”是欧拉通路定理，本题直接使用，不是靠几个例子当成证明。
3. 完整函数与逐句说明¶
代码段 1¶
int hasEulerTrail(MatrixGraph G) {
int oddCount = 0;
for (int i = 0; i < G.numVertices; i++) {
int degree = 0;
for (int j = 0; j < G.numVertices; j++) {
if (G.edge[i][j] != 0)
degree++;
}
if (degree % 2 != 0)
oddCount++;
}
return oddCount == 0 || oddCount == 2;
}
oddCount 是奇度顶点的总数。外层 i 每换一个顶点，就把它自己的 degree 清零；内层 j 扫这一行，发现与 j 有边就 degree++。一个顶点一行扫完后，degree%2!=0 表示奇数，才给 oddCount 加一。
最后返回一个逻辑式：oddCount 等于 0“或者”等于 2，真在 int 返回值中为 1，假为 0。这个函数没有做连通检查，因为输入题设已保证连通。
4. 自己试与边界¶
两个分离的三角形共 6 点，每点偶度，却没办法一条路线走遍两部分；所以没有连通保证时不能只用奇偶判定。度是边条数，不是权值之和。正式矩阵计数按无自环简单图理解，若题目给自环，其度贡献应为 2，需要调整计数。
学懂后回看：结论、复杂度与回源¶
题意与结论：题设已保证连通且 E>0。能恰好经过每条边一次的欧拉通路存在，当且仅当奇度顶点个数为 0 或 2；扫描矩阵统计即可，不必真的把路径找出来。
思路推导：路径每进入一个中间顶点，还要沿另一条边离开，边两两配对，所以中间点度数为偶数。只有不同的起点、终点可能各剩一条不配对边，形成两个奇度点；若首尾相同，则所有点均偶度。充分性还依赖无向连通图的欧拉定理。
走一遍：链 A-B-C-D 的度为 1,2,2,1，两个奇度点，存在从 A 到 D 的 EL 路径。三角形度为 2,2,2，0 个奇度点，存在欧拉回路。三叉星中心连三个叶子，度为 3,1,1,1，4 个奇度点，不存在。
代码抓手与正确性：对每个顶点扫描一行，统计有边的项数作为度；奇度则 oddCount++，最后判断 oddCount==0 || oddCount==2。无向图奇度顶点总数必为偶数，不能出现“只有 1 个奇度点”。
复杂度与易错点：邻接矩阵时间 O(V²)、空间 O(1)。没有连通前提时，仅看奇度数不够，例如两个分离的三角形全部偶度，却无法一条通路覆盖全图边。正式表示按普通无自环简单图理解；若允许自环或平行边，度数统计需适配，自环贡献 2。边权之和不是度数。
回源：PDF 第 22 页；回源 · PDF 第 22 页 · b_22_0；PDF 第 22 页 · b_22_4
。正式代码
46｜输出全部 K 顶点（本章第 5 题，2023）¶
题目与要求¶
题目（依据原题整理）：有向图 G 采用邻接矩阵存储，把出度大于入度的顶点称为 K 顶点。编写算法，输出所有 K 顶点，并返回 K 顶点的数量。
已知条件：出度是从该顶点发出的边数，入度是指向它的边数；本节普通邻接矩阵中 0 表示无边，非 0 表示有边。
需要得到：K 顶点的标识列表和总个数，两项都要给出。
输入 → 输出示例（教学补充）：顶点 0、1、2，边为 0→1、0→2、1→2 → 仅顶点 0 的出度 2 大于入度 0，输出顶点 0，返回数量 1。
约定与提醒（教学补充）：这里 K 不是一个要输入的整数，而是题目给这类顶点起的名字。出度等于入度不算 K 顶点；统计的是边数，不是权值总和。
题干回源：Code59 PDF 第 22 页；回源 · PDF 第 22 页 · b_22_1
。
1. K 顶点：发出去的箭头比收到的多¶
入度是进入某顶点的边数，出度是离开它的边数。K 顶点只是一种按这个比较筛出来的点，不是第 K 个顶点，也不是度等于 K。
输入 A→B、A→C、C→B，输出 A 并返回数量 1。C 入出一样，不合格。
2. 用矩阵的行和列分别数¶
| 顶点 i | 第 i 行的非零项：出度 | 第 i 列的非零项：入度 | 出>入？ |
|---|---|---|---|
| A | 到 B、C，两条 | 无，0 条 | 2>0，是 |
| B | 无，0 条 | 从 A、C 来，两条 | 0>2，否 |
| C | 到 B，一条 | 从 A 来，一条 | 1>1，否 |
edge[i][j] 读作从 i 到 j；反过来 edge[j][i] 读作从 j 到 i。把行列含义认清，这题的大半就解决了。
3. 完整函数与逐句说明¶
代码段 1¶
int printKVertices(MatrixGraph G) {
int count = 0;
for (int i = 0; i < G.numVertices; i++) {
int indegree = 0;
int outdegree = 0;
for (int j = 0; j < G.numVertices; j++) {
if (G.edge[i][j] != 0) outdegree++;
if (G.edge[j][i] != 0) indegree++;
}
if (outdegree > indegree) {
printf("%c ", G.vertex[i]);
count++;
}
}
return count;
}
count 是已经找到多少个 K 顶点，开始为 0。外层选当前 i，每次独立把 indegree、outdegree 清零。内层 j 从 0 到 V-1，同一次循环分别检查行项与列项，存在边才把对应计数加一。
一整行列数完才比较出度、入度，不是在数到一半时就判定。成立时 printf 用 %c 打印 G.vertex[i] 的顶点标签，再 count++。循环全结束 return count，返回的是数量，不是顶点编号。
4. 自己试一下¶
只有 A→B：A 是，B 不是，输出 A、数量 1。只有一个无边顶点 A：入出都是 0，严格大于不成立，数量 0。若误写 >=，就把所有入出相等的点也收进来了。
学懂后回看：结论、复杂度与回源¶
题意与结论：K 顶点满足出度严格大于入度。矩阵第 i 行统计 i 发出的边，第 i 列统计指向 i 的边，逐点比较并输出。
思路推导：先读矩阵语义：edge[i][j] 表示 i→j。固定 i 扫 j，就是统计 i 的出边；固定第二个下标 i，扫 edge[j][i]，就是统计入边。这一题关键不是复杂算法，而是别把行列弄反。
走一遍：边为 A→B、A→C、C→B。A 出度 2、入度 0，是 K 顶点；B 出度 0、入度 2，不是；C 出度 1、入度 1，也不是。输出 A，返回数量 1。
代码抓手与正确性：外层遍历 i；每个新 i 都把 indegree/outdegree 重新置 0；内层同时统计行和列；满足 outdegree>indegree 才打印并增加 count。统计直接对应定义，最后 count 就是输出数量。
复杂度与易错点：时间 O(V²)，工作空间 O(1)。大于不是大于等于。题目要求“输出顶点并返回数量”，两件都要做。带权矩阵若仍用 0 表无边，只统计非零项个数，不把权值当边条数；若 0 也可以是合法边权，应另设存在性规则。
回源：PDF 第 22 页；回源 · PDF 第 22 页 · b_22_1；PDF 第 22 页 · b_22_7
。正式代码
47｜邻接表统计入度与出度（本章第 6 题）¶
题目与要求¶
题目（依据原题整理）：有向图采用邻接表存储，计算每个顶点的入度和出度，分别保存在两个数组中。
已知条件：输入有向图，顶点按 0 到 |V|-1 编号；每个顶点的邻接链列出从它出发的边。
需要得到：indegree[i] 保存顶点 i 的入度，outdegree[i] 保存顶点 i 的出度；数组下标与顶点编号对应。
输入 → 输出示例（教学补充）：边为 0→1、0→2、1→2 → indegree=[0,1,2]，outdegree=[2,1,0]。
约定与提醒（教学补充）：一条 u→v 要计入 u 的出度和 v 的入度，不能把两个计数都加在同一个顶点上。没有入边或出边的计数应为 0，不能遗留未初始化值。
题干回源：Code59 PDF 第 22 页；回源 · PDF 第 22 页 · b_22_2
。
1. 看到一条边，就给两端各记一笔¶
输入邻接表 A:[B,C]，B:[C]，C:[]，输出每个点的入度和出度两个数组。每条 A→B 同时意味着“A 发出一条”和“B 收到一条”，不用为了找 B 的入边再单独遍历全图。
v 是当前出发顶点编号；p 指 v 的一条边记录；p->adjvex 是这条边到达的顶点编号。不要把边记录地址 p 当成顶点编号使用。
2. 两个数组怎么一起变化¶
| 扫到哪条边 | 出度数组 [A,B,C] | 入度数组 [A,B,C] |
|---|---|---|
| 初始清零 | [0,0,0] |
[0,0,0] |
| A→B | [1,0,0] |
[0,1,0] |
| A→C | [2,0,0] |
[0,1,1] |
| B→C | [2,1,0] |
[0,1,2] |
3. 完整函数与逐句说明¶
代码段 1¶
void calculateDegrees(Graph G, int indegree[], int outdegree[]) {
for (int i = 0; i < G.numVertices; i++) {
indegree[i] = 0;
outdegree[i] = 0;
}
for (int v = 0; v < G.numVertices; v++) {
for (ArcPtr p = G.adjList[v].firstarc;
p != NULL; p = p->nextarc) {
outdegree[v]++;
indegree[p->adjvex]++;
}
}
}
第一个 for 只负责把两个输出数组的前 V 个位置都清零；不能依赖调用者恰好给了全零数组。第二个外层 for 挨个访问顶点 v；内层从 firstarc 到 NULL，看完 v 的所有出边记录。
每遇一条边，outdegree[v]++ 给出发者加一，indegree[p->adjvex]++ 给到达者加一。p=p->nextarc 是移动到同一个顶点邻接链表中的下一条边记录，不是沿这条图边递归到邻居。
4. 自己试与自检办法¶
若再加入 C→A，则出度 [2,1,1]，入度 [1,1,2]。全部入度之和与全部出度之和都应等于有向边总数 4，这能帮你快速查错。空间里两个输出数组各需要 V 个格，不能说整件事完全没用数组，只能说除此之外工作空间常数。
学懂后回看：结论、复杂度与回源¶
题意与结论：把全部度数数组清零，每遇到一条 v→w，就令 outdegree[v]++、indegree[w]++，一次扫描所有边完成。
思路推导：入度不必对每个顶点再遍历全图寻找指向它的边。每条边天然贡献两个信息：来源顶点出度加一、目的顶点入度加一，在访问边时同时记账即可。
走一遍：邻接表为 A:[B,C]，B:[C]，C:[]。读 A→B 后 A 出度 1、B 入度 1；读 A→C 后 A 出度 2、C 入度 1；读 B→C 后 B 出度 1、C 入度 2。最终出度 [2,1,0]，入度 [0,1,2]。
代码抓手与正确性：外层 v 是链表所属的出发顶点，边结点的 adjvex 是到达顶点 w。不能对二者同一个下标都加在 v 上。每条有向边只存一次、处理一次，因此两种度数都恰好统计完整。
复杂度与易错点：初始化 O(V)、扫描边 O(E)，合计 O(V+E)。两个输出数组占 O(V)，此外工作空间 O(1)。可用 Σ入度=Σ出度=E 做自检；无向邻接表通常每条边存两次，不能直接把边结点总数当 E。
回源：PDF 第 22 页；回源 · PDF 第 22 页 · b_22_2；PDF 第 22 页 · b_22_3；PDF 第 22 页 · b_22_8
。正式代码
48｜无向图是否是一棵树（本章第 7 题）¶
题目与要求¶
题目（依据原题整理）：设计一个算法，判断给定无向图是否是一棵树，也就是它是否连通且没有环。
已知条件：输入无向图的邻接表；不能预先假定它已经连通。本讲解按非空的简单无向图讨论。
需要得到：整张图是一棵树时返回真，否则返回假，不是仅判断从某个点出发看到的局部结构。
输入 → 输出示例（教学补充）：顶点 0、1、2、3，边 0—1、1—2、1—3 → 真；若改为 0—1、1—2、2—0，顶点 3 孤立 → 假，虽然边数也等于顶点数减 1。
约定与提醒（教学补充）：单独一个顶点、没有边也是树。无向邻接表通常将一条边存两次，不能把邻接项总数直接当边数；本函数把没有顶点的图判为假。
题干回源：Code59 PDF 第 23 页；回源 · PDF 第 23 页 · b_23_2；PDF 第 23 页 · b_23_0
。
1. 树不是“看起来像树”的画法，而是满足条件¶
对无向图，判断树可以检查两件事：所有顶点连成一片；边数刚好比顶点数少 1。输入若 4 点三条边 A-B、B-C、C-D，是树；若三角形加一个孤立点，虽然也有三条边，却不是树。
visited 防重复计数；reachableCount 记从起点实际摸到几个不同点；numEdges 是图里真实的无向边条数。
2. 两个条件缺一个都不行¶
| 4 顶点的图 | 从 A 能访问多少点 | E=V-1？ | 结论 |
|---|---|---|---|
| A-B-C-D 链 | 4 | 3=4-1 | 树 |
| A-B-C-A，加孤立 D | 3 | 3=4-1 | 不连通，不是树 |
| A-B-C-D-A 四边形 | 4 | 4!=4-1 | 有多余边成环，不是树 |
连通图至少要 V-1 条边；达到最少条数时没有多余边形成环。这个定理让我们不必另写一次复杂判环。
3. 完整函数与逐句说明¶
代码段 1¶
void countReachableVertices(Graph G, int v,
bool visited[], int *count) {
visited[v] = true;
(*count)++;
for (ArcPtr p = G.adjList[v].firstarc;
p != NULL; p = p->nextarc) {
if (!visited[p->adjvex])
countReachableVertices(G, p->adjvex, visited, count);
}
}
bool isTree(Graph G) {
if (G.numVertices == 0)
return false;
bool visited[MAXSIZE] = {false};
int reachableCount = 0;
countReachableVertices(G, 0, visited, &reachableCount);
return reachableCount == G.numVertices
&& G.numEdges == G.numVertices - 1;
}
辅助 DFS 先把当前 v 标为已访问，再 (*count)++ 改同一份计数；之后沿未访问邻居递归。星号和括号说明增加的是地址里存的整数，不是增加指针地址。
主函数先把空图按约定判 false；visited 全清零，reachableCount=0；从编号 0 开始，把计数地址 &reachableCount 交给 DFS。最后要求计数==顶点总数，并且边数==顶点数-1，两条件用 && 连接。
4. 自己试一下¶
单顶点无边：访问数 1 等于 V，E=0=1-1，返回 true。邻接表中一条无向边常在两端各存一条记录，那是两份记录、不是两条真实边；numEdges 不应误填成它们的总数。此判定用于无向图，不直接套有向图。
学懂后回看：结论、复杂度与回源¶
题意与结论：无向图是树，当且仅当连通且 E=V-1。从一个顶点做 DFS 数到达点数，再检查边数。
思路推导：连通无向图至少要 V-1 条边才能连起所有顶点；恰好 V-1 时无多余边形成环。反过来，树本身就连通且有 V-1 条边，因此这两个条件既必要又充分。
走一遍：4 个点，边 A-B、B-C、C-D。从 A 能到 4 点，E=3=4-1，是树。对照：三角形 A-B-C-A 加孤立点 D，也是 V=4、E=3，但从 A 只到 3 点，所以不是树。
代码抓手与正确性：visited 保证每个点只计一次，reachableCount 统计实际到达顶点数；最终两个条件用 &&。正式结构中的 numEdges 应是真实无向边数，不是邻接表中边结点总数。
复杂度与易错点：时间 O(V+E)，空间 O(V)。不能只看 E=V-1，也不能只看连通。正式代码空图返回 false；单顶点、无边返回 true。这个定理用于无向图，不能直接用于有向图判树。
回源：PDF 第 23 页；回源 · PDF 第 23 页 · b_23_2；PDF 第 23 页 · b_23_0；PDF 第 23 页 · b_23_1；PDF 第 23 页 · b_23_5
。正式代码
49｜Floyd 全源最短路径（本章第 8 题）¶
题目与要求¶
题目（依据原题整理）：使用 Floyd 算法，计算有向图或无向图中每一对顶点之间的最短路径长度；记录路径信息，以便需要时还原相应路径。
已知条件：输入带权邻接矩阵，edge[i][j] 表示边权，无边为 INF，对角线为 0。要求不存在负权回路，相关有限距离及加法不超出代码的表示范围。
需要得到：全体顶点对的距离矩阵 dist 和路径记录；不可达仍要标为不可达，不能伪造距离 0。
输入 → 输出示例（教学补充）：有向边 0→1 权 2、1→2 权 3、0→2 权 10，没有其他边 → dist=[[0,2,5],[INF,0,3],[INF,INF,0]]；0 到 2 的最短路径为 0→1→2。
约定与提醒（教学补充）：本题与前面普通 0/1 邻接矩阵的含义不同，0 权边可以是真实边。负权回路会使相关最短距离没有有限最小值，下面函数不提供完整的负环报错机制。
题干回源：Code59 PDF 第 23 页；回源 · PDF 第 23 页 · b_23_3
。INF 保护与不可达输出是锁定稿的校订。
1. Floyd 解决的是“任意两点之间最短要多长”¶
假设 A→B 长 3，B→C 长 2，A→C 直接长 10。显然 A 绕 B 到 C 只要 5，比直达 10 更短。Floyd 把这个“试着经过某个中转点”推广到所有点对。
dist[i][j] 存目前已知的最短长度；k 是本轮允许加入的中转点；intermediate[i][j] 记录这次改进借用了哪个中转点，以后据此还原路线。INF 表示不通，不能当普通大数随便相加。
2. 一张距离表的具体更新¶
初始距离表：
| 出发→到达 | A | B | C |
|---|---|---|---|
| A | 0 | 3 | 10 |
| B | INF | 0 | 2 |
| C | INF | INF | 0 |
允许 B 中转时，检查 i=A、j=C：先问 A→B 通吗、B→C 通吗，两者都通；算 candidate=3+2=5；5<原来的10，所以 dist[A][C] 改成 5，intermediate[A][C] 记 B。检查 C→A 则因不通不能相加，仍 INF。
3. 三层循环究竟分别在枚举什么¶
最外层 k：这轮新增哪一个允许使用的中转点。中间 i：从哪里出发。最内层 j：想到哪里。它不是在把所有完整路线挨条列出来，而是在复用前几轮已经算好的两段最短距离，这叫动态规划。
处理完 k 时，答案允许使用编号 0..k 的内部中转点。一条最优路径要么不用 k，保持旧答案；要么用 k，把它拆成 i→k 与 k→j 比较。这就是 min(旧值,两段之和) 的依据，也说明 k 不能任意移到最内层。
4. 完整函数与逐句说明¶
代码段 1¶
void floyd(MatrixGraph G,
int dist[][MAXSIZE],
int intermediate[][MAXSIZE]) {
int n = G.numVertices;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = G.edge[i][j];
intermediate[i][j] = -1;
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF) {
long long candidate = (long long)dist[i][k] + dist[k][j];
if (candidate < dist[i][j]) {
dist[i][j] = (int)candidate;
intermediate[i][j] = k;
}
}
}
}
}
}
void printIntermediateVertices(int u, int v,
int intermediate[][MAXSIZE]) {
int k = intermediate[u][v];
if (k == -1)
return;
printIntermediateVertices(u, k, intermediate);
printf("%d ", k);
printIntermediateVertices(k, v, intermediate);
}
void printShortestPath(int u, int v,
int dist[][MAXSIZE],
int intermediate[][MAXSIZE]) {
if (dist[u][v] == INF) {
printf("no path\n");
return;
}
if (u == v) {
printf("%d\n", u);
return;
}
printf("%d ", u);
printIntermediateVertices(u, v, intermediate);
printf("%d\n", v);
}
第一个函数先取顶点数 n，再用双循环复制原始距离、把全部 intermediate 初始化为 -1（暂没记录中转点）。接着 k/i/j 三循环，先排除不可达的两段，再以 long long 计算候选和；只有更短才同时改距离和中转记录，不更短就保持旧答案。
第二个函数只打印路径的内部中转点：取 k，若为 -1 没有需要继续展开的中转点，返回；否则先打印 u→k 内部，再打印 k，再打印 k→v 内部。这是递归展开“之前记录过的两段”，不是再次搜索图。
第三个函数负责整条路径：先用 dist 判断是否不可达，不能只靠 intermediate=-1，因为直接相连也可能没有中转记录；若 u==v，打印它一次；其余情况先打印起点 u，调用内部点打印函数，最后打印终点 v。
5. 自己试与前提边界¶
若 A→B=4、B→C=8、A→C=7，经 B 得 12，比 7 更长，不更新。若 B→C 不通，即使 INF 数值很大也不能直接相加，必须走可达性判断。
本算法允许某些负边，但若存在影响路径的负环，反复绕圈可以让距离无限下降，最短有限值不成立；当前函数未完整处理这种情况。实际有限路径长度仍需能放入 int；宽类型候选计算不是所有溢出问题的通行证。
学懂后回看：结论、复杂度与回源¶
题意与结论：求每一对顶点的最短距离。依次允许顶点 k 作为新的中间点，检查 i→k→j 是否比当前 i→j 更短。
思路推导：处理完 k 后，dist[i][j] 表示仅允许 0..k 作为内部中间点时的最短距离。一条最短路要么不经过 k（沿用旧答案），要么经过 k（拆成 i 到 k、k 到 j）。所以转移为 dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])。
走一遍：边 A→B=3，B→C=2，A→C=10。初始化 A 到 C 为 10；允许 B 做中间点时，比 10 与 3+2=5，更新为 5，并记 intermediate[A][C]=B。恢复路径时先输出 A，再递归输出 A→B 与 B→C 间的中间点，最后输出 C，得到 A→B→C。
代码抓手与正确性：循环顺序为 k 在最外层、i 和 j 在内层，这是状态阶段，不可随意把 k 放最内层。初始化对角为 0、无边为 INF。只有 dist[i][k] 和 dist[k][j] 都可达时才相加；intermediate=-1 只表示无记录的中间点，不能单独判断是否可达。
复杂度与易错点：时间 O(V³)，距离与路径记录空间 O(V²)。允许负边，但要排除会使所求距离无下界的负环；负环影响的点对不能正常输出有限最短路。正式函数没有完整负环处理。无向负权边可来回走形成负闭合游走，同样不能简单照用。代码用宽整数做加法，但有限结果转回 int 仍要求范围合法。Floyd 是动态规划，不是把所有路径列出来试。
回源：PDF 第 23 页；回源 · PDF 第 23 页 · b_23_3
。正式代码
50｜邻接表拓扑判有向环（本章第 9 题）¶
题目与要求¶
题目（依据原题与校订说明整理）：给定采用邻接表存储的有向图，使用拓扑排序判断是否存在有向环。
已知条件：输入有向图；有向环指沿箭头前进一圈后可以回到出发顶点。
需要得到：有环返回 true，无环返回 false；不要求输出拓扑序或环上的具体顶点。
输入 → 输出示例（教学补充）：边 0→1、1→2 → false；再加入 2→0 → true。
约定与提醒（教学补充）：原资料标题把“有/无向图”混写在一起；本讲解沿用已核对的校订，仅把此拓扑算法用于有向图。返回 true 的含义是“有环”，别误读成“拓扑排序成功”。
题干回源：Code59 PDF 第 23—24 页；回源 · PDF 第 23 页 · b_23_4；PDF 第 24 页 · b_24_0
。
1. 把有向边读成“先完成谁，才能做谁”¶
A→B 表示 B 还等 A。入度为 0 就是“已经没有未完成前置要求”，可以先处理。处理 A 后，所有从 A 发出的要求都解除，使后继入度减一。
图有环时可能出现 B 等 C、C 又等 B，谁也启动不了。拓扑处理能删完所有点则无环，删不完则有环。函数 true 的含义是“有环”，别把它当排序成功。
2. 用一个卡住的过程理解判环¶
图 A→B、B→C、C→B。
| 时刻 | 剩余入度 A、B、C | 可处理栈 | 已处理数 |
|---|---|---|---|
| 初始 | 0、2、1 | A | 0 |
| 取 A，解除 A→B | A 已完成，B=1，C=1 | 空 | 1 |
| 栈空 | B 仍等 C，C 仍等 B | 没新候选 | 1<3 |
因此返回 true。若改成 A→B→C，A 释放 B，B 再释放 C，最终处理 3 个，返回 false。
3. 完整函数与逐句说明¶
代码段 1¶
bool hasDirectedCycleList(Graph G) {
int indegree[MAXSIZE] = {0};
int stack[MAXSIZE];
int top = -1;
int visitedCount = 0;
for (int v = 0; v < G.numVertices; v++) {
for (ArcPtr p = G.adjList[v].firstarc;
p != NULL; p = p->nextarc)
indegree[p->adjvex]++;
}
for (int v = 0; v < G.numVertices; v++) {
if (indegree[v] == 0)
stack[++top] = v;
}
while (top != -1) {
int v = stack[top--];
visitedCount++;
for (ArcPtr p = G.adjList[v].firstarc;
p != NULL; p = p->nextarc) {
if (--indegree[p->adjvex] == 0)
stack[++top] = p->adjvex;
}
}
return visitedCount != G.numVertices;
}
indegree 初始为零；stack 保存当前可处理点；top=-1 表示栈空；visitedCount 记录已经处理的点数。先扫邻接表，把每条边目的点的入度加一；再找所有 0 入度点，用 stack[++top]=v 压栈（先增加 top，再写入）。
while 栈不空，v=stack[top--] 先取当前栈顶，再 top 减一；计数加一。扫描 v 的出边，对每个目的点执行前置递减 --indegree[...]：先解除这条要求，再问是否恰好降到 0，是才入栈。
最后看处理数是否不等于 V。辅助入度变小代表逻辑删边，原邻接表不必真的拆掉。visitedCount 这个名字不是普通 DFS 的 visited 数组，别混用。
4. 自己试与不能套无向图的原因¶
A→B、C→B：开始 A、C 都可处理；先处理谁都行，但 B 必须等两条入边都解除。处理完三点说明无环，即使顺序不唯一。无向边双向存储不代表两个相互依赖的有向任务，不能直接用本代码把每条无向边都看作二元环。
学懂后回看：结论、复杂度与回源¶
题意与结论：反复取出入度 0 顶点，逻辑删除其出边；能删完全部顶点则无环，剩下一部分删不动就有环。本函数约定有环返回 true。
思路推导：入度 0 顶点没有未完成的前驱，可以先处理。删除它后，某些后继也可能失去最后一个前驱。若剩余非空子图每个点都有前驱，沿前驱不断追溯，有限顶点中必重复，从而存在环。
走一遍：A→B、B→C、C→B。初始入度 A=0、B=2、C=1，只有 A 可取。删 A→B 后 B 入度从 2 降到 1，没有新候选；已处理 1 个而 V=3，所以有环。若改为链 A→B→C，会依次释放 A、B、C，处理数为 3，无环。
代码抓手与正确性：先扫描边统计入度，把所有 0 入度点压栈；弹出 v 后遍历它的邻接表，对每个 w 做 --indegree[w]，恰变成 0 时压栈。最后返回 visitedCount!=V。这里只改辅助入度，不必真的删原图边。
复杂度与易错点：时间 O(V+E)，空间 O(V)。visitedCount 实际是拓扑处理数，不是普通 DFS 访问数。拓扑排序用于有向图；无向边在邻接表中双向存储，不能按这套 0 入度消除法直接判环。原稿“有/无向图”混称已在正式版纠正。
回源：PDF 第 23—24 页；回源 · PDF 第 23 页 · b_23_4；PDF 第 24 页 · b_24_0
。正式代码
51｜邻接矩阵拓扑判有向环（本章第 10 题）¶
题目与要求¶
题目（依据原题与校订说明整理）：给定采用邻接矩阵存储的有向图，使用拓扑排序判断图中是否存在有向环。
已知条件：edge[i][j] 非 0 表示有边 i→j，0 表示无边；本题不是无向图判环。
需要得到：有环返回 true，无环返回 false，结果含义与第 50 题相同。
输入 → 输出示例（教学补充）：矩阵 [[0,1,0],[0,0,1],[0,0,0]] 表示 0→1→2 → false；将第 2 行第 0 列改为 1、补上 2→0 → true（行列编号从 0 开始）。
约定与提醒（教学补充）：邻接矩阵只改变图的保存方式，不改变有向环的定义。原稿“有/无向图”的混写同样不沿用；也不能用矩阵是否对称来代替判环。
题干回源：Code59 PDF 第 24 页；回源 · PDF 第 24 页 · b_24_1；PDF 第 24 页 · b_24_2
。
1. 原理不变，只把邻接表换成方格表¶
仍然做“取 0 入度点，解除出边要求，数最终处理了多少点”。矩阵列 i 表示哪些人指向 i，用来算入度；矩阵行 v 表示 v 指向哪些人，用来解除要求。
输入 A→B、A→C、B→D、C→D。无环，应返回 false。
2. D 要等两件事，不能提前入栈¶
| 操作 | B、C、D 的剩余入度 | 当前可处理点 |
|---|---|---|
| 初始 | 1、1、2 | A |
| 处理 A，扫描 A 行 | 0、0、2 | B、C |
| 按栈次序先处理 C | B 待处理、C 完成、D=1 | B |
| 处理 B | D=0 | D |
| 处理 D | 全部完成 | 空 |
如果 D 从 2 减到 1 就入栈，意味着另一个前置要求还没完成就执行了 D，是错误的。
3. 完整函数与逐句说明¶
代码段 1¶
bool hasDirectedCycleMatrix(MatrixGraph G) {
int indegree[MAXSIZE] = {0};
int stack[MAXSIZE];
int top = -1;
int visitedCount = 0;
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
if (G.edge[j][i] != 0)
indegree[i]++;
}
}
for (int v = 0; v < G.numVertices; v++) {
if (indegree[v] == 0)
stack[++top] = v;
}
while (top != -1) {
int v = stack[top--];
visitedCount++;
for (int w = 0; w < G.numVertices; w++) {
if (G.edge[v][w] != 0 && --indegree[w] == 0)
stack[++top] = w;
}
}
return visitedCount != G.numVertices;
}
初始化四个辅助量同上一题。双循环算第 i 列：有 edge[j][i] 才给 indegree[i] 加一。然后把所有 0 入度编号压栈。
每次出栈 v、计数加一，接着 w 从 0 到 V-1 扫整行；edge[v][w]!=0 && --indegree[w]==0 是先确认边存在，再减少度数，再判断是否刚归零。因为 && 短路，无边时绝不能减 w 的入度。归零才压栈；栈空后比较访问数与 V。
4. 自己试与复杂度差异¶
只有一条 A→B，处理 A 时只对 B 的入度减一，不能让其他无关点也跟着减。邻接矩阵即使很少边，也必须逐格检查一行，初始化更要扫 V×V 格，所以时间 O(V²)。换成邻接表可以直接列出存在的边，才得到上一题的 O(V+E)。
学懂后回看：结论、复杂度与回源¶
题意与结论：判定原理与上一题完全相同，只是入度从矩阵列统计，删除出边时扫描矩阵行。处理顶点数小于 V 就有环。
思路推导：更换存储结构不等于更换算法。邻接表可以直接列出 v 的所有出边；邻接矩阵必须把整行的 V 个位置都检查一遍，判断哪些位置真的有边。
走一遍：边 A→B、A→C、B→D、C→D，初始入度 [0,1,1,2]。取 A，扫描 A 行后变 [0,0,0,2]；B、C 都可处理。先取 C 时 D 降到 1，还不能入栈；再取 B 时 D 降到 0，才入栈。四点都处理完，返回 false（无环）。
代码抓手与正确性：统计 i 入度用 edge[j][i]；处理 v 出边用 edge[v][w]。只有有边时才减少 w 的入度，并且只有“刚降为 0”的那一次入栈，避免重复计数。逻辑删边过程与邻接表版本相同。
复杂度与易错点：初始化扫描 V² 个矩阵项，处理每个点还可能扫一行，总时间仍 O(V²)，空间 O(V)。不能把上一题 O(V+E) 原封不动搬过来。即使图很稀疏，矩阵也得检查大量无边位置。
回源：PDF 第 24 页；回源 · PDF 第 24 页 · b_24_1；PDF 第 24 页 · b_24_2
。正式代码
52｜拓扑序是否唯一（本章第 11 题，2024）¶
题目与要求¶
题目（依据原题整理）：有向图采用邻接矩阵存储，设计一个算法，判断它的拓扑排序是否唯一。拓扑序是把全部顶点排成一列，且每条边的起点都排在终点之前。
已知条件：输入有向图；一张图可能没有拓扑序，也可能只有一种或有多种。
需要得到：存在且仅存在一个拓扑序时返回 true；有多种或因有环而不存在时返回 false。
输入 → 输出示例（教学补充）：0→1→2 → 唯一顺序为 0,1,2，返回真；只有 0→2、1→2 → 0,1,2 和 1,0,2 都合法，返回假；0→1、1→0 → 无拓扑序，也返回假。
约定与提醒（教学补充）：找出一种顺序不等于证明唯一；整个过程每一步都需检查能选择的顶点。不要把“无环”直接当成“拓扑序唯一”。
题干回源：Code59 PDF 第 24 页；回源 · PDF 第 24 页 · b_24_3
。
1. “有拓扑序”与“只有一种拓扑序”要分开¶
拓扑序是满足每条有向边先后约束的一种顶点排列。A→B→C 只允许 A、B、C；A→B、A→C 允许 A、B、C 或 A、C、B，不唯一。
判断办法：每一步可选的 0 入度点必须恰好一个，并且最终处理完全部点。多个选项意味着存在分叉；没有选项但还剩点，意味着有环无合法序。
2. 直接看“候选人数”怎样变化¶
| 图 | 初始候选 | 处理第一点后 | 最终结论 |
|---|---|---|---|
| A→B→C | A 一人 | B 一人，再 C 一人 | 唯一 |
| A→B，A→C | A 一人 | B、C 两人 | 不唯一 |
| A→B，B→A | 无人 | 根本不能开始 | 无拓扑序 |
为什么两个候选可交换？在无环图里，两者当前都没有未完成前驱，不存在必须先做其中某一个的限制，所以可以选择不同的先后顺序。
3. 完整函数与逐句说明¶
代码段 1¶
bool hasUniqueTopologicalOrder(MatrixGraph G) {
int indegree[MAXSIZE] = {0};
int stack[MAXSIZE];
int top = -1;
int visitedCount = 0;
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
if (G.edge[j][i] != 0)
indegree[i]++;
}
}
for (int v = 0; v < G.numVertices; v++) {
if (indegree[v] == 0)
stack[++top] = v;
}
if (top > 0)
return false;
while (top != -1) {
int v = stack[top--];
visitedCount++;
for (int w = 0; w < G.numVertices; w++) {
if (G.edge[v][w] != 0 && --indegree[w] == 0)
stack[++top] = w;
}
if (top > 0)
return false;
}
return visitedCount == G.numVertices;
}
前面的入度统计与入栈同矩阵拓扑排序。新增的 if(top>0) 是查栈里至少两点：top 从 -1 计，0 表示一个，1 表示两个。因此不能写 top>=0，否则连唯一一个也会被当作“不唯一”。
先检查初始栈，每次处理 v 的所有出边后，再检查一次更新后的栈。只检查最开始不够，分叉可能后来才出现，A→B、A→C 就是例子。
候选过多直接 return false；一直没过多时，循环结束还要 visitedCount==V。若存在环，可能全程都没有两人候选，但最终也处理不完，仍返回 false。这个 false 统一表示“不满足存在且唯一”，具体是多解还是无解要看图。
4. 自己试一下¶
独立两个点 A、B 没有边：初始栈有两个，top=1，不唯一，AB 与 BA 都行。只有一个无自环点：top=0，取完计数等于 V，唯一。把栈改队列可能换一种输出顺序，但不会把本来多种顺序的图变成数学上唯一。
学懂后回看：结论、复杂度与回源¶
题意与结论：要存在且唯一，每一步必须恰好只有一个 0 入度候选，并最终处理全部顶点。有多个候选则不能判为唯一；删不完则无拓扑序。
思路推导：对于 DAG，若某步有两个可选点 u、v，就能先 u 后 v，也能先 v 后 u，得到不同拓扑序；若每一步都只有唯一选择，整个顺序就被强制确定。一般有向图还需检查环，不能只看是否出现多个候选。
走一遍：链 A→B→C 的候选集合依次为 {A}、{B}、{C}，唯一。叉形 A→B、A→C 先是 {A}，取 A 后变 {B,C}，可得到 ABC 或 ACB，不唯一。A→B、B→A 一开始没有候选，处理数 0，不存在拓扑序，更谈不上唯一。
代码抓手与正确性：栈顶从 -1 开始，候选数量是 top+1，所以 top>0 表示至少两个候选。每次删完当前点的出边后再检查候选数，同时保留栈中先前尚未处理的候选。最后必须 visitedCount==V，防止把“从来没有两个候选”误当成唯一。
复杂度与易错点：矩阵时间 O(V²)，空间 O(V)。只检查初始 0 入度点是否唯一不够，后面也可能分叉。栈换队列只改变选点策略，不改变唯一性；图有环时应说“无拓扑序”，而不是“有很多拓扑序”。空图的返回属于实现约定，考试通常给非空图。
回源：PDF 第 24 页；回源 · PDF 第 24 页 · b_24_3；PDF 第 24 页 · b_24_4
。正式代码