有向无环图的拓扑排序——CSP-J1真题讲解

【题目】

考虑一个有向无环图，该图包括4条有向边：(1,2)，(1,3)，(2,4)，和(3,4)。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）

A. 4, 2, 3, 1

B. 1, 2, 3, 4

C. 1, 2, 4, 3

D. 2, 1, 3, 4

【解析】

本题考查有向无环图（DAG）的拓扑排序问题。

这里面涉及到3个概念：

1．有向无环图（DAG，Directed Acyclic Graph）

所谓的图，就是一堆节点和边。图好比是一张情网，节点是情网中的人，边是情网中人和人的关系。

有向指两个节点间的关系是有方向的，就好比两个人如果有关系，只能是单相思关系。

环是指从一个顶点出发，经过一系列边和顶点后，最终又回到该起点的路径。无环就是图中没有这样的环，也就是说不会返回起点。

2．有向边

前面说过边表示两个节点的关系，有向边就是表示有方向性的关系。比如有这么两个人：u和v，它们的关系是u爱v，而v不爱u。要表示这种单相思关系可以用“(u，v)”的形式表示，称作“节点u指向节点v”，画成图就是下面这样子：

这条带箭头的线就是“有向边”了。

3．拓扑排序

拓扑是个音译词，来自topology（拓扑学）中的topo。topo的本义是place（地点、位置），这是一个数学上的概念，含义很复杂，我们可以简单地理解拓扑排序是关于“前后位置”的排序。

对于一个有向无环图，拓扑排序是将图的所有顶点排成一个线性序列，使得对于每一条有向边 (u，v)，顶点 u 在序列中出现在顶点 v 的前面。

还是拿单相思情网举例，拓扑排序相当于要把所有困在情网中的人排成一队。排队时要保证任何有单相思关系的两个人，关系的生产者（相思者）排在消费者（被相思者）之前。

下面就来做一下这道题，题中给出了4条有向边：(1,2)，(1,3)，(2,4)，和(3,4)，也就是4种单相思关系：1爱2，1爱3，2爱4，3爱4。用图表示为：

这个图的有效拓扑排序必须要同时满足上图的4种关系。

其实这种关系更像是一种任务或课程的先后关系，比如上图就是课程1要排在课程2、3之前，课程2要排在课程4之前，课程3要排在课程4这前。求它的拓扑排序就相当于要你对这4门课进行排序。

现在要找出答案非常简单，只需要按每个选项的顺序在图上走一遭，如果和图中箭头方向没有冲突，就是有效的。

A. 4, 2, 3, 1：第1步就违反了图中的方向关系，排除。

B. 1, 2, 3, 4：没有违反图中的方向关系，因为2、3节点间没有关系，怎么来都行，正确。

C. 1, 2, 4, 3：4、3间违反了图中的方向关系，3应在4之前。

D. 2, 1, 3, 4：第1步违反了图中的方向关系，排除。

是不是很简单呢？

这道题就是名词唬人，实际没什么难度。

就算你完全不知道这些名词的含义，按理也应该能求出答案。你看到 (1,2)，(1,3)，(2,4)，(3,4)这样的数据，这是什么样的数据呢？前面有那么明晃晃的两个字——有向。所以这组数据一定是和表示方向有关系。什么样的方向呢？人家都说是“拓扑排序”了，你管他娘的什么“拓扑”，只要知道是“排序”就足够了。你就纯把它当成对数字排序，所以这种方向关系一定指的是数字的前后。所以，管它什么鸟图、鸟拓扑，你还想不到把选项中数字与这组数据的前后关系作对比吗？只要二者前后关系相一致，那就是答案呗。

【题目来源】

2023 CCF非专业级别软件能力认证第一轮 (CSP-J1) 入门级C++语言试题 第12题