【数据结构】深入浅出图论：拓扑排序算法全面解析与应用实践

(拓扑排序)

图的基本应用

导读

大家好，很高兴又和大家见面啦！！！

在上一篇内容中，我们探讨了图论的基础概念和应用。今天，我们将深入探讨一个在图论中极为重要的概念——拓扑排序，它在工程调度、任务安排和依赖关系管理中有着广泛的应用。

在开始拓扑排序之前，让我们先回顾一下有向无环图（DAG图） 的核心特性：

• 有向性：图中的边具有明确的方向性，表示一种单向关系
• 无环性：图中不存在任何循环路径，即不可能从某个顶点出发沿着有向边最终又回到该顶点
• 传递性：如果存在路径从顶点A到顶点B，再从B到C，则A与C之间存在间接的前驱后继关系

DAG图的这些特性使其成为表示具有先后顺序关系的活动的理想工具，这正是AOV网的基础。

在实际工程和任务调度中，我们经常需要处理各种具有依赖关系的活动。例如：

• 软件编译过程中的模块依赖关系
• 课程学习的先修条件
• 项目开发中的任务先后顺序

拓扑排序正是解决这类问题的关键算法：它将DAG图中的所有顶点排列成一个线性序列，使得对于任何一条有向边 <u, v>

通过本文，您将深入了解：

• AOV网如何用DAG图表示活动及其依赖关系
• 拓扑排序的核心算法思想及其实现方式
• 如何通过代码实现拓扑排序算法
• 拓扑排序与逆拓扑排序的关系

让我们开始探索拓扑排序的奥秘，理解这一强大工具如何帮助我们理清复杂工程中的依赖关系，确保任务按照正确的顺序执行！

一、拓扑排序

1.1 基本概念

1.1.1 AOV网

基本定义

AOV网 （Activity On Vertex NetWork, 用顶点表示活动的网）：在有向无环图（DAG图）中，每个顶点都表示一个活动，有向边 <V_i, V_j>V_i 必须先于活动 V_j 进行的这样一种关系，整个图表示一个完整的工程，则将这种 DAG图 称为 顶点表示活动的网络 ，简称 AOV网.

定义理解

graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C

上图就是通过 DAG图 表示的吃苹果这个工程：我们如果想吃苹果了，首先我们得去买苹果，买完苹果后，我们需要把苹果洗一下，之后可以根据个人的喜好选择是否去皮，最后我们就可以吃上苹果了。

在整个工程中，每个顶点都代表了这个工程中的一种活动，并且每个活动的先后顺序都是通过有向边进行连接，即我们只能先买完了苹果，才能洗苹果，不可能先洗苹果再买苹果。

graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C
B--->A

在上图中，我们可以看到存在着一个环路：买苹果与洗苹果这两个活动所构成的环路，放在整个工程中，就表示，我们在买苹果前需要先洗苹果，我在洗苹果前需要先买苹果，由此我们不难看出，整个工程在实施的过程中，就陷入了一个死循环——到底是先买苹果还是先洗苹果？

因此，为了避免出现这种问题，AOV网 一定是一个 DAG图，即：从顶点 V_i 到顶点 V_j 的有向边 <V_i, V_j>V_i 一定是活动 V_j 的直接前驱，活动 V_j 一定是活动 V_i 的直接后继，这种前驱与后继的关系具有传递性，即：

graph LR
A[买苹果]--->B[洗苹果]--->D[削苹果皮]--->C[吃苹果]

在上图中，买苹果一定是洗苹果的直接前驱，是削苹果皮的前驱，是吃苹果的前驱；吃苹果一定是削苹果皮的直接后继，是洗苹果的后继，是买苹果的后继。

由此可知，在 AOV网 中，任何活动 V_i 都不可能以它自己作为自己的前驱或者后继，即不可能存在环路。

1.1.2 拓扑排序

基本定义

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

1. 每个顶点出现且只出现一次
2. 若顶点 A 在序列中排在顶点 B 的前面，则图中不存在从 B 到 A 的路径

或定义为：拓扑排序是对 DAG图 中各顶点的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中 B 出现在 A 的后面。

每个AOV网都有一个或多个拓扑排序序列。

定义理解

拓扑排序实际上就是指的完成一个工程时，工程中各个活动的先后顺序。为了方便大家理解，我们还是以吃苹果这个工程为例：

graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C

在这个工程中，总共有4个顶点，所谓的拓扑排序就是需要按照事情的先后顺序对这4个顶点进行排序，因此，其拓扑排序序列只有一个：

graph LR
A[买苹果]--->B[洗苹果]--->D[削苹果皮]--->C[吃苹果]

这时有朋友可能就会有疑问了，为什么 买苹果-->洗苹果-->吃苹果 这条路径不属于拓扑排序呢？

这是因为，拓扑排序的排序对象是DAG图中的所有顶点，当我们按照： 买苹果-->洗苹果-->吃苹果 这条路径进行排序时，那么剩余的削苹果皮这个活动就无法参与到排序中，如果我们直接将其添加到吃苹果的后面，即：买苹果-->洗苹果-->吃苹果-->削苹果皮，那么这里就存在以下问题：

• 从AOV网中进行分析：图中并不存在吃苹果-->削苹果皮这条路径
• 从实际意义进行分析：苹果都吃了，我们还削哪门子的苹果皮？

这时可能有盆友说，我可以边吃边啃苹果皮，这不也是成立的吗？虽然这种事情我也做过，但是如果我们将这条路径放入到 DAG图中，我们就会得到下面这个图：

graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C-->D

可以看到此时的图中，就已经存在环了，此时的图，就已经不属于DAG图了，因此，该图自然就不存在拓扑排序了。

1.2 算法思想

在获取一个 DAG图 的拓扑排序时，我们需要优先确定的是活动的起始顶点，以吃苹果这个工程为例：

graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C

在这个工程中，起始顶点很显然是买苹果，这是因为该顶点不存在前驱结点，以图的角度来说，那就是：该顶点的入度为0

当我们将该顶点去掉后，其出度也需要一并去掉，即：

graph LR
B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C

此时的图中，可以看到洗苹果这个顶点不再存在前驱顶点，因此，该顶点为该图中的起始顶点，这时我们继续去掉该顶点及其出度，我们就得到了下图：

graph LR
C[吃苹果]
D[削苹果皮]--->C

可以看到，此时的图中，入度为0的顶点为：削苹果皮，因此该顶点为此图的起始顶点，将其去掉后，我们就得到了下图：

graph LR
C[吃苹果]
C

可以看到，此时的图中，入度为0的顶点为：吃苹果，因此该顶点为此图的起始顶点，将其去掉后，图就变成了空图，按照顶点去掉的先后顺序，我们就得到了该图的拓扑排序：

• 买苹果-->洗苹果-->削苹果皮-->吃苹果

从上述的过程，我们可以总结出拓扑排序的获取步骤：

1. 获取图中，入度为0的顶点
2. 去掉该顶点及其出度
3. 重复上述步骤，直到图中不存在顶点入度为0或图为空图

这里可能有朋友会奇怪，为什么是不存在顶点的入度为0？这里我们以下图为例：

graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C-->D

当我们按照上述步骤执行时，我们在去掉洗苹果这个顶点后，我们就得到了下图：

graph LR
C[吃苹果]
D[削苹果皮]--->C-->D

可以看到，由于剩余的两个顶点成环，因此两个顶点的入度与出度均为1，所以图中不存在入度为0的顶点。

在理解了这点后，我们就可以理解，对于判断入度为0这个条件，实际上就是在判断该图是否存在环路。

1.3 算法实现

1.3.1 C语言代码

这里我们采用邻接矩阵的方式来实现拓扑排序：

int S[MAXVERNUM];						// 记录顶点的栈
int indegree[MAXVERNUM];				// 记录各顶点的入度
int Sort_list[MAXVERNUM];				// 排序数组
// 邻接矩阵实现
bool TopologicalSort(Graph G) {
	InitStack(S);						// 初始化栈
	int top = 0;						// 栈顶
	// 找工程中的起始顶点
	for (int i = 0; i < G.Mgraph.ver_num; i++) {
		if (indegree[i] == 0) {			// 当前顶点入度为0
			Push(S, i);					// 该顶点入栈
			top += 1;
		}
	}
	int count = 0;						// 已排序的顶点数
	while (!IsEmpty(S) || count) {
		int i = Pop(S, top);			// 栈顶元素出栈
		top -= 1;
		Sort_list[count] = i;			// 排序栈顶元素
		count += 1;
		// 删除该顶点对应的所有出度
		for (int j = 0; j < G.Mgraph.ver_num; j++) {
			if (G.Mgraph.edge[i][j]) {	// 判断是否存在弧<i, j>
				indegree[j] -= 1;		// 该顶点入度-1
			}
			if (indegree[j] == 0) {		// 该顶点入度为0
				Push(S, j);				// 该顶点入栈
			}
		}
	}
	return count == G.Mgraph.ver_num;	// 判断是否完成所有顶点的排序
}

1.3.2 代码解释

	InitStack(S);						// 初始化栈
	int top = 0;						// 栈顶

整个排序的过程，我们是借用栈来实现，通过记录顶点编号的栈来判断图中是否存在入度为0的顶点；

	// 找工程中的起始顶点
	for (int i = 0; i < G.Mgraph.ver_num; i++) {
		if (indegree[i] == 0) {			// 当前顶点入度为0
			Push(S, i);					// 该顶点入栈
			top += 1;
		}
	}

在算法的第一个for循环中，我们主要进行的是寻找图中起始入度为0的顶点，并对其通过栈进行记录；

	int count = 0;						// 已排序的顶点数
	while (!IsEmpty(S) || count) {
		int i = Pop(S, top);			// 栈顶元素出栈
		top -= 1;
		Sort_list[count] = i;			// 排序栈顶元素
		count += 1;
		// 删除该顶点对应的所有出度
		for (int j = 0; j < G.Mgraph.ver_num; j++) {
			if (G.Mgraph.edge[i][j]) {	// 判断是否存在弧<i, j>
				indegree[j] -= 1;		// 该顶点入度-1
			}
			if (indegree[j] == 0) {		// 该顶点入度为0
				Push(S, j);				// 该顶点入栈
			}
		}
	}

在完成对起始顶点的记录后，我们通过变量count来记录当前完成排序的顶点数量，通过判断栈是否为空，来控制循环是否结束：

• 当栈为空，说明图中不存在入度为0的顶点，此时会存在两种情况
  • 图中的顶点均完成排序，循环结束时，count 与图中的顶点数相同
  • 图中存在未排序的顶点，即图中存在环，循环结束时，count 小于图中的顶点数

整个循环的过程，算法一直在重复进行：

• 将栈顶元素出栈
• 对出栈元素进行排序
• 删除该元素的所有出入
• 对新的入度为0的元素进行入栈

由于这里我们是通过邻接矩阵实现，因此我们在对其出度进行删除时，实际上是通过遍历以顶点 i 为起始点的矩阵，判断其对应的分区中是否存在以顶点 j 为终点的弧，若存在，入度数组 indegree 中其顶点 j 所对应的入度数量-1；

若我们通过邻接表实现的话，我们只需要遍历顶点 i 的边表即可，将边表中存在的顶点 j 所对应的入度数量-1；

整体的视线并不复杂，这里我就不再赘述。为了方便大家更好的理解上述代码，这里我给大家展示一下头文件中的内容：

typedef char VerType;
typedef int EdgeType;
typedef int InfoType;
#define MAXVERNUM 5
typedef struct MatrixGraph {
	VerType verlist[MAXVERNUM];					// 顶点表
	EdgeType edge[MAXVERNUM][MAXVERNUM];		// 边矩阵
	InfoType info;								// 边权值
	int ver_num;								// 顶点数
	int edge_num;								// 边数
}MG;
typedef struct ArcNode {
	int adjver;									// 邻接顶点
	struct ArcNode* nextarc;					// 下一条弧指针
	InfoType info;								// 边权值
}ANode;
typedef struct VerNode {
	VerType data;								// 顶点信息
	ANode* firtarc;								// 第一条弧指针
}VNode;
typedef struct AdjListGraph {
	VNode verlist[MAXVERNUM];					// 顶点表
	int vernum;									// 顶点数
	int arcnum;									// 弧数
}ALG;
typedef struct Graph {
	MG Mgraph;									// 邻接矩阵
	ALG ALGraph;								// 邻接表
}Graph;

感兴趣的朋友可以自己动手实现一下。

1.4 算法评价

从上述的代码实现我们不难看出，当我们采用邻接矩阵实现时，外层循环需要完成对所有顶点的遍历，内层循环同样也要完成对所有顶点的遍历，因此对应的时间复杂度为：O(|V|^2)

若我们改用邻接表实现的话，内层循环我们只需要对该顶点对应的边进行遍历即可，即对应的时间复杂度为：O(|V| + |E|)

在整个实现的过程中，我们需要额外开辟3个大小与顶点数相同，或者与最大顶点数相同的整型数组空间，即空间复杂度为：O(|V|)

二、逆拓扑排序

在了解了何为拓扑排序后，逆拓扑排序实际上就是将原先的入度改为出度，在算法实现的过程中，通过判断出度为0的顶点来依次获取顶点序列， 这里我就不再多加赘述，作简单的了解即可，以吃苹果这个工程为例：

graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C

其拓扑排序与逆拓扑排序分别为：

• 拓扑排序：买苹果 --> 洗苹果 --> 削苹果皮 --> 吃苹果
• 逆拓扑排序：吃苹果 --> 削苹果皮 --> 洗苹果 --> 买苹果

结语

通过本文的系统学习，相信大家已经对拓扑排序的核心概念和实现方法有了扎实的理解。让我们简单回顾一下本文的关键知识点：

📚 本文核心内容总结

1. AOV网与DAG图的密切关系：AOV网建立在有向无环图（DAG图）基础上，用顶点表示活动，用有向边清晰定义活动间的依赖关系，其无环特性确保了工程不会陷入死循环。
2. 拓扑排序的算法精髓：通过不断选择入度为0的顶点，逐步构建满足所有前置条件的活动序列，既确定了执行顺序，又能有效检测图中的环路。
3. 实践与应用价值：
   • 邻接矩阵实现：时间复杂度O(V²)
   • 邻接表实现：优化至O(V + E)
   • 空间复杂度稳定在O(V)

🔜 下篇预告：关键路径分析

虽然拓扑排序解决了"执行顺序"的问题，但实际工程管理中我们更关心："完成整个工程的最短时间是多少？哪些任务是影响工期的关键环节？"

这就是我们下一篇要深入探讨的关键路径（Critical Path）分析。通过关键路径方法，您将能够：

• ⏰ 精确计算工程的最短完成时间
• 🔍 识别关键任务（任何延迟都会影响总工期）
• 📊 优化资源分配，提高工程效率

期待在下一篇文章中与您继续探索图论的实用价值！