🏷️ 知识点：拓扑排序

若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。

拓扑排序

A. 存在，且唯一

B. 存在，且不唯一

C. 存在，可能不唯一

D. 无法确定是否存在

[tag_link]

正确答案：C

主对角线以下元素均为零，表示只可能存在 i→j (i<j) 的边，不可能沿边从较大编号回到较小编号，所以图中无有向环，一定存在拓扑序列。

但拓扑序列未必唯一。例如 3 个顶点只有边 1→3、2→3 时，邻接矩阵是严格上三角矩阵，1,2,3 与 2,1,3 都是合法拓扑序。因此选 C。

反过来，DAG 在任意编号下的邻接矩阵未必是三角矩阵；按某个拓扑序给顶点重新编号后，才可得到严格上三角矩阵。

修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的（ ）。

DFS 图的遍历

A. 拓扑有序序列 B. 逆拓扑有序序列 C. 广度优先搜索序列 D. 深度优先搜索序列

[tag_link]

正确答案：B

DFS 对任意有向边 vᵢ→vⱼ，DFS 从 vᵢ 沿该边访问 vⱼ 时，必须先完成 vⱼ 及其后继的递归，才能回到 vᵢ。把输出语句放在退出递归前，就会先输出后继 vⱼ，再输出前驱 vᵢ。因此所有边的终点都排在起点之前，输出序列是逆拓扑有序序列，选 B；若把该完成序列逆序，才得到拓扑序。

下列关于图的叙述中，正确的是（ ）。

图的概念

A. 有向图必定存在入度为 0 的顶点 B. 有向无环图的拓扑排序有序序列存在且唯一 C. 各顶点的度均大于等于 2 的无向图必有回路 D. 可用 BFS 算法求出带权图中每一对顶点的最短路径

[tag_link]

正确答案：C

逐项判断：

• A 错。一个有向环中每个顶点的入度都为 1，因此有向图不一定有入度为 0 的顶点。
• B 错。DAG 一定存在拓扑序，但某一步若有多个零入度候选，选择顺序不同就会产生多个拓扑序。
• C 对。若无向图无环，则每个非空有限森林至少有一个度为 0 或 1 的顶点；反过来，每个顶点度至少为 2 的无向图不可能是森林，必有回路。
• D 错。BFS 只能直接求无权图或各边等权图的单源最短路径，不能求一般带权图的每对最短路径；非负权单源问题可用 Dijkstra，多源问题可用 Floyd。

已知有向图 G=(V, A)，其中 V={a,b,c,d,e}，A={<a,b>, <a,c>, <d,c>, <d,e>, <b,e>, <c,e>}，对该图进行拓扑排序，下面序列中不是拓扑排序的是（ ）。

A. a,d,c,b,e B. d,a,b,c,e C. a,b,d,c,e D. a,h,c,d,e

拓扑排序

[tag_link]

正确答案：D

拓扑排序要求对于有向图中的每一条边，在排序序列中顶点 u 必须出现在顶点 v 之前。 给定图 G 的顶点集 V={a,b,c,d,e}，边集 A={, , , , , }，因此约束条件为：a 在 b 和 c 之前，d 在 c 和 e 之前，b 在 e 之前，c 在 e 之前。

逐一检查选项：

• 选项 A（a,d,c,b,e）：a 在 b 和 c 之前，d 在 c 和 e 之前，b 和 c 在 e 之前，所有边约束均满足，是拓扑排序。 >
• 选项 B（d,a,b,c,e）：d 在 c 和 e 之前，a 在 b 和 c 之前，b 和 c 在 e 之前，所有边约束均满足，是拓扑排序。 >
• 选项 C（a,b,d,c,e）：a 在 b 和 c 之前，d 在 c 和 e 之前，b 和 c 在 e 之前，所有边约束均满足，是拓扑排序。 >
• 选项 D（a,h,c,d,e）：序列中包含顶点 h，而 h 不在图 G 的顶点集 V 中，因此不是有效序列。 > 即使假设 h 是 b 的笔误，序列变为 a,b,c,d,e，此时边要求 d 在 c 之前，但序列中 d 在 c 之后，违反约束。 > 故选项 D 不是拓扑排序。 >

因此，不是拓扑排序的序列是选项 D。 >

对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是()。

A.3,1,2,4,5,6

B.3,1,2,4,6,5

C.3,1,4,2,5,6

D.3,1,4,2,6,5

[tag_link]

正确答案：D

按照 拓扑排序 的算法，每次都选择入度为 0 的结点从图中删去，此图中一开始只有结点 3 的入度为 0；删掉结点 3 后，只有结点 1 的入度为 0; 删掉结点 1 后，只有结点 4 的入度为 0；删掉结点 4 后，结点 2 和结点 6 的入度都为 0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为 3,1 4,2,6,5 和 3,1,4,6,2,5, 选 D。

若将 n 个顶点 e 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（）

复杂度分析 邻接表 拓扑排序

A. (O(n)) B. (O(n+e)) C. (O(n^2)) D. (O(n\log_2 n))

[tag_link]

正确答案：B

用邻接表实现 Kahn 拓扑排序时，初始化入度并让每个顶点至多入队、出队一次，共 O(n)；删除某顶点的出边时，每条弧只沿邻接表扫描一次，共 O(e)。因此总时间复杂度为 O(n+e)，选 B。若改用邻接矩阵，每次查找出边要扫描一整行，通常为 O(n²)。

下列选项中，不是如下有向图的拓扑序列的是（ ）

拓扑排序

A. 1, 5, 2, 3, 6, 4 B. 5, 1, 2, 6, 3, 4 C. 5, 1, 2, 3, 6, 4 D. 5, 2, 1, 6, 3, 4

[tag_link]

正确答案：D

拓扑排序 每次只能输出当前入度为 0 的结点。初始只有 1 和 5 的入度为 0，因此前两位只能是 1,5 或 5,1；选项 D 的第二位是 2，却把仍未输出的 1 放在第三位，违反图中的前驱约束。A、B、C 逐边检查均满足前驱先于后继，故选 D。

给定如下有向图，该图的拓扑有序序列的个数是（ ）。

拓扑排序

A. 1 B. 2 C. 3 D. 4

[tag_link]

正确答案：A

按 Kahn 算法逐步删除入度为 0 的顶点。初始只能选 A；删除 A 后只能选 B，随后依次只能选 C、D、E、F。每一步的零入度候选都只有一个，因此唯一的拓扑序列是 A→B→C→D→E→F，个数为 1。

在有向图 G 的拓扑序列中，若顶点 Vᵢ 在顶点 Vⱼ 之前，则下列情形不可能出现的是（ ）。

A. G 中有弧<Vᵢ, Vⱼ> B. G 中有一条从 Vᵢ 到 Vⱼ 的路径 C. G 中没有弧<Vᵢ, Vⱼ> D. G 中有一条从 Vⱼ 到 Vᵢ 的路径

拓扑排序

[tag_link]

正确答案：D

拓扑序列是针对有向无环图（DAG）的一种顶点排序，要求对于图中的任意有向边，起点在终点之前。

因此，若顶点Vᵢ在拓扑序列中位于Vⱼ之前，则图中不能存在从Vⱼ到Vᵢ的路径，否则会形成环路，违反拓扑序列的定义。

分析选项：

• A：存在弧（即从Vᵢ到Vⱼ的有向边）是可能的，因为该边方向与序列顺序一致，符合拓扑序列要求。 >
• B：存在从Vᵢ到Vⱼ的路径也是可能的，路径意味着Vᵢ是Vⱼ的前驱，在拓扑序列中自然位于其前。 >
• C：没有弧同样可能，因为Vᵢ和Vⱼ之间可能通过其他顶点间接连通，或没有直接关联但序列顺序由其他边决定。 >
• D：存在从Vⱼ到Vᵢ的路径是不可能的，因为如果有这样的路径，根据拓扑序列性质，Vⱼ必须位于Vᵢ之前，这与已知的Vᵢ在Vⱼ之前矛盾。 >

因此，不可能出现的情形是D。 >

对下图进行拓扑排序，可以得到不同拓扑序列的个数是()。

A. 4

B. 3

C. 2

D. 1

[tag_link]

正确答案：B

初始只有 a 的入度为 0，所以第一位必须是 a。删除 a 的出边后，b 与 e 都可选：

• 先选 e，后续被约束为 b,c,d，得到 aebcd；
• 先选 b，随后可先选 c 或 e，分别得到 abced、abecd。

因此共有 3 个不同的拓扑序列，选 B。

下列关于图的叙述中，正确的是（ ）。

Ⅰ. 回路是简单路径

Ⅱ. 存储稀疏图，用邻接矩阵比邻接表更省空间

Ⅲ. 若有向图中存在拓扑序列，则该图不存在回路

图的概念

A. 仅 Ⅱ

B. 仅 Ⅰ、Ⅱ

C. 仅 Ⅲ

D. 仅 Ⅰ、Ⅲ

[tag_link]

正确答案：C

第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为 简单路径 ；简单回路除首尾顶点外不重复，但“简单路径”要求路径中的顶点不重复，所以回路不是简单路径，Ⅰ错误。稀疏图的边数远小于 n²，邻接矩阵固定占用 O(n²)，邻接表只占 O(n+e)，Ⅱ错误。存在拓扑序列等价于有向图无环，若 拓扑排序 输出结束后仍有顶点未输出，则剩余子图存在有向环。因此Ⅲ正确，仅Ⅲ正确，选 C。

使用直接插入排序对序列进行升序排序，以下比较次数最少的是（ ）

A. 30,27,56,41,80,95,69 B. 31,43,26,55,63,99,77 C. 61,84,51,23,34,91,40 D. 93,32,48,81,50,21,72

[tag_link]

正确答案：B

【解析】 直接插入排序的比较次数取决于序列的初始有序程度。对于每个序列，从第二个元素开始，将其与前面已排序的元素从后往前比较，直到找到正确位置，记录比较次数。

• 选项 A：序列 30, 27, 56, 41, 80, 95, 69 的总比较次数为1+1+2+1+1+3=9次。
• 选项 B：序列 31, 43, 26, 55, 63, 99, 77 的总比较次数为1+2+1+1+1+2=8次。
• 选项 C：序列 61, 84, 51, 23, 34, 91, 40 的总比较次数为1+2+3+4+1+5=16次。
• 选项 D：序列 93, 32, 48, 81, 50, 21, 72 的总比较次数为1+2+2+3+5+3=16次。比较次数最少的是选项 B，共 8 次。

若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是()。

A. 起泡排序

B. 插入排序

C. 选择排序

D. 二路归并排序

[tag_link]

正确答案：B

本题考查各种内部排序算法的特点。

对于冒泡排序和选择排序，每一趟都能确定一个元素的最终位置，而题目中，前 2 个元素和后 2 个元素均不是最小或最大的 2 个元素并按序排列。

选项 D 中的 2 路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。

插入排序在每趟排序后能确定前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特征。

如何对无环有向图中的顶点重新编号，使得该图的邻接矩阵中所有的 1 都集中到对角线以上？

[tag_link]

参考答案

对该 DAG 进行拓扑排序，并按拓扑序列依次编号为 1,2,…,n。对任意弧 i→j，拓扑序都要求 i 排在 j 之前，因此新编号满足 i<j；对应的邻接矩阵元素 A[i][j] 只可能位于主对角线上方。拓扑排序可用入度为 0 的顶点逐步删除，若有多个候选顶点，任取其一即可。

推导

DAG 必然存在拓扑序。重新编号后，若矩阵下三角位置 A[i][j]（i>j）为 1，就表示存在弧 i→j，与拓扑序中 i 应排在 j 前矛盾。因此所有 1 均在主对角线上方；该性质不要求拓扑序唯一。

易错点

只按原编号排序不一定成立；必须使用拓扑序。矩阵上三角方向取决于约定的弧方向和编号顺序，本文约定 A[i][j]=1 表示 i→j。

2023 年 10 月 26 日，神州十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导工程。以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已如有向图 G 采用邻接矩阵存储，类型定义如下：

typedef struct // 图的类型定义
{
    int numVertices, numEdges; // 图的顶点数和有向边数
    char verticesList[MAXV];   // 项点表，MAXV 为以定义常量
    int Edge[MAXV][MAXV];      // 邻接矩阵
} MGraph

请设计算法：int uniquely(MGraph G)。判定 G 是否存在唯一的拓扑序列，若是则返回 1，否则返回 0。要求：

(1) 给出算法的基本设计思想（4 分）

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释（9 分）

拓扑排序 邻接矩阵

[tag_link]

1）算法基本设计思想输出拓扑序列的过程如下：依次从图中选取入度为 0 的点进行输出。确保拓扑序列唯一需要保证如下条件：在输出拓扑序列时，每一次有且仅有一个入度为 0 的顶点。所以这题最直观的思路就是进行 numEdges 轮遍历，如果每轮遍历只有一个顶点的入度为 0，则图中存在唯一的拓扑序列；否则不存在唯一的拓扑序列。

2）算法实现

int uniquely(MGraph g)
{
    int n = g.numVertices;
    int inDegrees[MAXV];

    /* 计算所有顶点的入度 */
    for (int v = 0; v < n; v++) {
        inDegrees[v] = 0;
        for (int i = 0; i < n; i++) {
            if (g.Edge[i][v] != 0)
                inDegrees[v] += g.Edge[i][v];
        }
    }

    /* 进行 n 轮拓扑删除 */
    for (int k = 0; k < n; k++) {

        int count0 = 0;   // 入度为 0 的顶点个数
        int v0 = -1;      // 本轮唯一可以选择的顶点

        /* 找所有入度为 0 的顶点 */
        for (int i = 0; i < n; i++) {
            if (inDegrees[i] == 0) {
                count0++;
                v0 = i;
            }
        }

        /* 若不是唯一一个，则拓扑序列不唯一 */
        if (count0 != 1) {
            return 0;
        }

        /* “删除”该顶点：将其入度设为 -1，避免重复选取 */
        inDegrees[v0] = -1;

        /* 更新其所有后继节点的入度 */
        for (int j = 0; j < n; j++) {
            if (g.Edge[v0][j] != 0)
                inDegrees[j]--;
        }
    }

    /* 所有步骤都唯一，拓扑序唯一 */
    return 1;
}

在有向图 G 的拓扑序列中，若顶点 v₁ 在顶点 v₂ 之前，则不可能出现的情形是（ ）。

A. G 中有弧 ⟨v₁,v₂⟩ B. G 中有一条从 v₁ 到 v₂ 的路径 C. G 中没有弧 ⟨v₂,v₁⟩ D. G 中有一条从 v₂ 到 v₁ 的路径

[tag_link]

正确答案：D

结论

D 正确。

推导

A 正确，直接弧要求 v₁ 在 v₂ 前；B 正确，前向路径同样保持该顺序；C 正确，不存在反向弧不构成矛盾；D 错误，v₂→…→v₁ 会要求 v₂ 先于 v₁。

易错点

把“序列中的先后”误认为必须存在直接弧；拓扑约束也由间接路径产生。

下列关于拓扑排序的说法中，错误的是（ ）。

Ⅰ．若某有向图存在环路，则该有向图一定不存在拓扑排序 Ⅱ．在拓扑排序算法中，为暂存入度为零的顶点，可以使用栈，也可以使用队列 Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为 1 Ⅳ．若有向图的拓扑有序序列唯一，则图中入度为 0 和出度为 0 的顶点都仅有 1 个

A. Ⅰ、Ⅲ、Ⅳ B. Ⅲ、Ⅳ C. Ⅱ、Ⅳ D. Ⅲ

[tag_link]

正确答案：D

结论

D 正确。

推导

陈述Ⅰ正确：有向环不能拓扑排序。陈述Ⅱ正确：栈或队列均可暂存入度为零的顶点。陈述Ⅲ错误：a→b、a→c、b→c 的 DAG 唯一序列 a,b,c，但 c 入度为 2。陈述Ⅳ正确：多个入度零或出度零顶点可交换。组合选项中，A 包含Ⅰ、Ⅲ、Ⅳ，B 包含Ⅲ、Ⅳ，C 包含Ⅱ、Ⅳ，只有选项 D 仅包含Ⅲ这一错误陈述。

易错点

唯一序列不等于每个顶点度数至多 1，关键是每一步是否只有一个可选入度零顶点。

下列关于拓扑排序的说法中，正确的是（ ）。

Ⅰ．顶点数大于 1 的强连通图不能进行拓扑排序 Ⅱ．在一个有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧 ⟨a,b⟩ Ⅲ．若有向无环图的拓扑序列唯一，则可以唯一确定该图

A. Ⅰ和Ⅱ B. Ⅰ、Ⅱ和Ⅲ C. 仅Ⅰ D. Ⅰ和Ⅲ

[tag_link]

正确答案：C

结论

C 正确。

推导

陈述Ⅰ正确：顶点数大于 1 的强连通图含环。陈述Ⅱ错误：a→x→b 时 a 在 b 前但无直接弧。陈述Ⅲ错误：图一仅有 a→b→c，图二还有 a→c，两图唯一拓扑序列都为 a,b,c。组合选项 A 包含Ⅰ、Ⅱ，B 包含Ⅰ、Ⅱ、Ⅲ，C 仅包含Ⅰ，D 包含Ⅰ、Ⅲ；因此只有选项 C 仅包含Ⅰ这一正确陈述。

易错点

拓扑序列表达偏序约束，不能反推出全部边，更不能唯一确定图。

若一个有向图的顶点不能排成一个拓扑序列，则判定该有向图（ ）。

A. 含有多个出度为 0 的顶点 B. 是个强连通图 C. 含有多个入度为 0 的顶点 D. 含有顶点数大于 1 的强连通分量

[tag_link]

正确答案：D

结论

D 正确。

推导

A、C 仅描述零度顶点数量，不阻止排序；B 过强，局部环图不必全图强连通；D 正确，排序剩余环中的顶点彼此可达，形成大于 1 个顶点的强连通分量。

易错点

不能把“存在强连通分量”误读成“整个图强连通”。

已知有向图 G=(V,E)，其中 V={v₁,v₂,v₃,v₄,v₅,v₆,v₇}，E={⟨v₁,v₂⟩,⟨v₁,v₃⟩,⟨v₁,v₄⟩,⟨v₂,v₅⟩,⟨v₃,v₅⟩,⟨v₃,v₆⟩,⟨v₅,v₇⟩,⟨v₆,v₇⟩,⟨v₄,v₆⟩}，G 的拓扑序列是（ ）。

A. {v₁,v₃,v₄,v₆,v₂,v₅,v₇} B. {v₁,v₃,v₂,v₆,v₄,v₅,v₇} C. {v₁,v₃,v₄,v₅,v₂,v₆,v₇} D. {v₁,v₂,v₅,v₃,v₄,v₆,v₇}

正确答案：A

结论

A 满足所有有向边的起点先于终点，是合法拓扑序列。

推导

逐项验证边约束：v₁ 在 v₂、v₃、v₄ 之前；v₂、v₃ 在 v₅之前；v₃、v₄ 在 v₆之前；v₅、v₆ 在 v₇之前。A 的位置顺序全部满足这些约束。

易错点

A 正确；B 将 v₆ 放在 v₄ 前违反 v₄→v₆；C 将 v₅ 放在 v₂ 前违反 v₂→v₅；D 将 v₅ 放在 v₃ 前违反 v₃→v₅。

若一个有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为（ ）。

A. 对称 B. 稀疏 C. 三角 D. 一般

正确答案：C

结论

C。按拓扑序给顶点编号后，邻接矩阵必为严格上三角或严格下三角矩阵。

推导

拓扑序要求每条边都从序号较小顶点指向序号较大顶点，所以一种编号方向下非零元素只在主对角线上方；若反向编号，则只在下方。无自环时主对角线为 0。

易错点

A 对称性属于无向图；B 拓扑序不限制边数，不能推出稀疏；D 忽略了拓扑序带来的方向约束。

用 DFS 算法遍历一个无环有向图，并在 DFS 算法退栈返回时输出相应的顶点，则输出的顶点序列是（ ）。

A. 逆拓扑有序 B. 拓扑有序 C. 无序的 D. 无法确定

正确答案：A

结论

A。退栈时输出的完成时间序列是逆拓扑序。

推导

对任意边 u→v，DFS 必须先完成后继 v，才可能完成 u，因此 v 的完成时间早于 u。按完成时间从先到后输出时，后继在前、前驱在后，正是拓扑序的逆序。

易错点

B 是把完成时间序列与其逆序混淆；C、D 忽略了无环条件下完成时间对每条边的严格约束。

试编写利用 DFS 实现有向无环图拓扑排序的算法。

[tag_link]

参考答案

用三色标记区分顶点状态：白色表示未访问，灰色表示仍在当前 DFS 递归栈中，黑色表示其所有后继都已处理。遇到指向灰色顶点的边就是回边，说明图中有环，不能得到拓扑序。

topologicalSort(G):
    color[v] = WHITE for every vertex v
    stack = empty
    for each vertex v:
        if color[v] == WHITE and not dfs(v):
            return "图中有环"
    return pop all vertices from stack

dfs(u):
    color[u] = GRAY
    for each v in Adj[u]:
        if color[v] == GRAY:
            return false
        if color[v] == WHITE and not dfs(v):
            return false
    color[u] = BLACK
    push u into stack
    return true

顶点 u 只有在所有后继完成后才入栈，因此对任意边 u→v，v 先于 u 入栈；最后按出栈顺序输出，就得到完成时间从晚到早的拓扑序。外层循环遍历所有白色顶点，因此也适用于不连通的 DAG。

采用邻接表时，每个顶点和每条边只处理常数次，时间复杂度为 O(V+E)，辅助空间为 O(V)（不计图本身）。