【数据结构】深入浅出图论：拓扑排序算法全面解析与应用实践
(拓扑排序)
图的基本应用导读大家好，很高兴又和大家见面啦！！！
在上一篇内容中，我们探讨了图论的基础概念和应用。今天，我们将深入探讨一个在图论中极为重要的概念——拓扑排序，它在工程调度、任务安排和依赖关系管理中有着广泛的应用。
在开始拓扑排序之前，让我们先回顾一下有向无环图（DAG图） 的核心特性：
有向性：图中的边具有明确的方向性，表示一种单向关系
无环性：图中不存在任何循环路径，即不可能从某个顶点出发沿着有向边最终又回到该顶点
传递性：如果存在路径从顶点A到顶点B，再从B到C，则A与C之间存在间接的前驱后继关系
DAG图的这些特性使其成为表示具有先后顺序关系的活动的理想工具，这正是AOV网的基础。
在实际工程和任务调度中，我们经常需要处理各种具有依赖关系的活动。例如：
软件编译过程中的模块依赖关系
课程学习的先修条件
项目开发中的任务先后顺序
拓扑排序正是解决这类问题的关键算法：它将DAG图中的所有顶点排列成一个线性序列，使得对于任何一条有向边
通过本文，您将深入了解：
AOV网如何用DAG图表示活动及其依赖关系
拓扑排序的核心算法思想及其实现方式
如何通过代码实现拓扑排序算法
拓扑排序与逆拓扑排序的关系
让我们开始探索拓扑排序的奥秘，理解这一强大工具如何帮助我们理清复杂工程中的依赖关系，确保任务按照正确的顺序执行！
一、拓扑排序1.1 基本概念1.1.1 AOV网基本定义AOV网 （Activity On Vertex NetWork, 用顶点表示活动的网）：在有向无环图（DAG图）中，每个顶点都表示一个活动，有向边
定义理解代码语言：javascript代码运行次数：0运行复制graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C上图就是通过 DAG图 表示的吃苹果这个工程：我们如果想吃苹果了，首先我们得去买苹果，买完苹果后，我们需要把苹果洗一下，之后可以根据个人的喜好选择是否去皮，最后我们就可以吃上苹果了。
在整个工程中，每个顶点都代表了这个工程中的一种活动，并且每个活动的先后顺序都是通过有向边进行连接，即我们只能先买完了苹果，才能洗苹果，不可能先洗苹果再买苹果。
代码语言：javascript代码运行次数：0运行复制graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C
B--->A在上图中，我们可以看到存在着一个环路：买苹果与洗苹果这两个活动所构成的环路，放在整个工程中，就表示，我们在买苹果前需要先洗苹果，我在洗苹果前需要先买苹果，由此我们不难看出，整个工程在实施的过程中，就陷入了一个死循环——到底是先买苹果还是先洗苹果？
因此，为了避免出现这种问题，AOV网 一定是一个 DAG图，即：从顶点 V_i 到顶点 V_j 的有向边
代码语言：javascript代码运行次数：0运行复制graph LR
A[买苹果]--->B[洗苹果]--->D[削苹果皮]--->C[吃苹果]在上图中，买苹果一定是洗苹果的直接前驱，是削苹果皮的前驱，是吃苹果的前驱；吃苹果一定是削苹果皮的直接后继，是洗苹果的后继，是买苹果的后继。
由此可知，在 AOV网 中，任何活动 V_i 都不可能以它自己作为自己的前驱或者后继，即不可能存在环路。
1.1.2 拓扑排序基本定义拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
每个顶点出现且只出现一次若顶点 A 在序列中排在顶点 B 的前面，则图中不存在从 B 到 A 的路径或定义为：拓扑排序是对 DAG图 中各顶点的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中 B 出现在 A 的后面。
每个AOV网都有一个或多个拓扑排序序列。
定义理解拓扑排序实际上就是指的完成一个工程时，工程中各个活动的先后顺序。为了方便大家理解，我们还是以吃苹果这个工程为例：
代码语言：javascript代码运行次数：0运行复制graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C在这个工程中，总共有4个顶点，所谓的拓扑排序就是需要按照事情的先后顺序对这4个顶点进行排序，因此，其拓扑排序序列只有一个：
代码语言：javascript代码运行次数：0运行复制graph LR
A[买苹果]--->B[洗苹果]--->D[削苹果皮]--->C[吃苹果]这时有朋友可能就会有疑问了，为什么 买苹果-->洗苹果-->吃苹果 这条路径不属于拓扑排序呢？
这是因为，拓扑排序的排序对象是DAG图中的所有顶点，当我们按照： 买苹果-->洗苹果-->吃苹果 这条路径进行排序时，那么剩余的削苹果皮这个活动就无法参与到排序中，如果我们直接将其添加到吃苹果的后面，即：买苹果-->洗苹果-->吃苹果-->削苹果皮，那么这里就存在以下问题：
从AOV网中进行分析：图中并不存在吃苹果-->削苹果皮这条路径从实际意义进行分析：苹果都吃了，我们还削哪门子的苹果皮？这时可能有盆友说，我可以边吃边啃苹果皮，这不也是成立的吗？虽然这种事情我也做过，但是如果我们将这条路径放入到 DAG图中，我们就会得到下面这个图：
代码语言：javascript代码运行次数：0运行复制graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C-->D可以看到此时的图中，就已经存在环了，此时的图，就已经不属于DAG图了，因此，该图自然就不存在拓扑排序了。
1.2 算法思想在获取一个 DAG图 的拓扑排序时，我们需要优先确定的是活动的起始顶点，以吃苹果这个工程为例：
代码语言：javascript代码运行次数：0运行复制graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C在这个工程中，起始顶点很显然是买苹果，这是因为该顶点不存在前驱结点，以图的角度来说，那就是：该顶点的入度为0
当我们将该顶点去掉后，其出度也需要一并去掉，即：
代码语言：javascript代码运行次数：0运行复制graph LR
B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C此时的图中，可以看到洗苹果这个顶点不再存在前驱顶点，因此，该顶点为该图中的起始顶点，这时我们继续去掉该顶点及其出度，我们就得到了下图：
代码语言：javascript代码运行次数：0运行复制graph LR
C[吃苹果]
D[削苹果皮]--->C可以看到，此时的图中，入度为0的顶点为：削苹果皮，因此该顶点为此图的起始顶点，将其去掉后，我们就得到了下图：
代码语言：javascript代码运行次数：0运行复制graph LR
C[吃苹果]
C可以看到，此时的图中，入度为0的顶点为：吃苹果，因此该顶点为此图的起始顶点，将其去掉后，图就变成了空图，按照顶点去掉的先后顺序，我们就得到了该图的拓扑排序：
买苹果-->洗苹果-->削苹果皮-->吃苹果从上述的过程，我们可以总结出拓扑排序的获取步骤：
获取图中，入度为0的顶点去掉该顶点及其出度重复上述步骤，直到图中不存在顶点入度为0或图为空图这里可能有朋友会奇怪，为什么是不存在顶点的入度为0？这里我们以下图为例：
代码语言：javascript代码运行次数：0运行复制graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C-->D当我们按照上述步骤执行时，我们在去掉洗苹果这个顶点后，我们就得到了下图：
代码语言：javascript代码运行次数：0运行复制graph LR
C[吃苹果]
D[削苹果皮]--->C-->D可以看到，由于剩余的两个顶点成环，因此两个顶点的入度与出度均为1，所以图中不存在入度为0的顶点。
在理解了这点后，我们就可以理解，对于判断入度为0这个条件，实际上就是在判断该图是否存在环路。
1.3 算法实现1.3.1 C语言代码这里我们采用邻接矩阵的方式来实现拓扑排序：
代码语言：javascript代码运行次数：0运行复制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]) { // 判断是否存在弧
indegree[j] -= 1; // 该顶点入度-1
}
if (indegree[j] == 0) { // 该顶点入度为0
Push(S, j); // 该顶点入栈
}
}
}
return count == G.Mgraph.ver_num; // 判断是否完成所有顶点的排序
}1.3.2 代码解释代码语言：javascript代码运行次数：0运行复制 InitStack(S); // 初始化栈
int top = 0; // 栈顶整个排序的过程，我们是借用栈来实现，通过记录顶点编号的栈来判断图中是否存在入度为0的顶点；
代码语言：javascript代码运行次数：0运行复制 // 找工程中的起始顶点
for (int i = 0; i < G.Mgraph.ver_num; i++) {
if (indegree[i] == 0) { // 当前顶点入度为0
Push(S, i); // 该顶点入栈
top += 1;
}
}在算法的第一个for循环中，我们主要进行的是寻找图中起始入度为0的顶点，并对其通过栈进行记录；
代码语言：javascript代码运行次数：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]) { // 判断是否存在弧
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；
整体的视线并不复杂，这里我就不再赘述。为了方便大家更好的理解上述代码，这里我给大家展示一下头文件中的内容：
代码语言：javascript代码运行次数：0运行复制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的顶点来依次获取顶点序列， 这里我就不再多加赘述，作简单的了解即可，以吃苹果这个工程为例：
代码语言：javascript代码运行次数：0运行复制graph LR
A[买苹果]--->B[洗苹果]--->C[吃苹果]
B--->D[削苹果皮]--->C其拓扑排序与逆拓扑排序分别为：
拓扑排序：买苹果 --> 洗苹果 --> 削苹果皮 --> 吃苹果逆拓扑排序：吃苹果 --> 削苹果皮 --> 洗苹果 --> 买苹果结语通过本文的系统学习，相信大家已经对拓扑排序的核心概念和实现方法有了扎实的理解。让我们简单回顾一下本文的关键知识点：
📚 本文核心内容总结
AOV网与DAG图的密切关系：AOV网建立在有向无环图（DAG图）基础上，用顶点表示活动，用有向边清晰定义活动间的依赖关系，其无环特性确保了工程不会陷入死循环。
拓扑排序的算法精髓：通过不断选择入度为0的顶点，逐步构建满足所有前置条件的活动序列，既确定了执行顺序，又能有效检测图中的环路。
实践与应用价值：
邻接矩阵实现：时间复杂度O(V²)
邻接表实现：优化至O(V + E)
空间复杂度稳定在O(V)
🔜 下篇预告：关键路径分析
虽然拓扑排序解决了"执行顺序"的问题，但实际工程管理中我们更关心："完成整个工程的最短时间是多少？哪些任务是影响工期的关键环节？"
这就是我们下一篇要深入探讨的关键路径（Critical Path）分析。通过关键路径方法，您将能够：
⏰ 精确计算工程的最短完成时间 🔍 识别关键任务（任何延迟都会影响总工期） 📊 优化资源分配，提高工程效率期待在下一篇文章中与您继续探索图论的实用价值！