408数据结构-图的应用3-有向无环图、拓扑排序 自学知识点整理

前置知识：表达式，图的遍历

有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称 $DAG$图 。
（图片来自王道考研408数据结构2025）
由王道考研-咸鱼学长的讲解方法（视频传送门），这一类题目有一个通解，具体步骤如下：

• $Step1$：把各个操作数不重复地排成一排。
• $Step2$：标出各个运算符的生效顺序（同级别之间任意）。
• $Step3$：按顺序加入运算符，注意“分层”。（若某个运算符的执行要基于另一个运算符和操作数的执行结果来进行，则前一个运算符在后一个的“上一层”）
• $Step4$：从底层向上逐层检查，看同层的运算符是否可以“合体”。

检查完毕后，得出的表达式的$DAG$图就是顶点数最小的。

注意：在表达式的有向无环图表示中，不可能出现重复的操作数顶点。

拓扑排序

$AOV$网：若用$DAG$图表示一个工程，其顶点表示活动，用有向边$<V_i,V_j>$表示活动$V_i$必须先于活动$V_j$进行这样一种关系，则将这种有向图称为顶点表示活动的网络，简称 $AOV$网。在$AOV$网中，活动$V_i$是活动$V_j$的直接前驱，$V_j$是$V_i$的直接后继，这种前驱和后继关系具有传递性，且任何活动$V_i$不能以它自己作为自己的前驱或后继。
拓扑排序：在图论中，由一个$DAG$图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

1. 每个顶点出现且仅出现一次。
2. 若顶点$A$在序列中排在顶点$B$的前面，则在图中不存在从$B$到$A$的路径。
   或定义为：拓扑排序是对有向无环图的一种排序，它使得若存在一条从顶点$A$到顶点$B$的路径，则在排序中$B$出现在$A$的后面。每个$AOV$网都有一个或多个拓扑排序序列。

简而言之，拓扑排序就是这样的一种排序：如果顶点$A$到顶点$B$有路，$B$到$A$没有，那么$A$排$B$前面。由此可见，入度为$0$的顶点在拓扑排序序列里一定是在最前面的。

对一个$AOV$网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：
① 从$AOV$网中选择一个没有前驱（入度为$0$）的顶点并输出。
② 从网中删除该顶点和所有以它为起点的有向边。
③ 重复①和②直到当前的$AOV$网为空或者当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。（那就不是$DAG$图了）

下图是王道书上的实例，读者可以看看，加以理解。
（图片来自王道考研408数据结构2025）

知识点回顾：图的存储与基本操作

对图采用邻接表存储表示如下：

#define MaxVertexNum 1007
typedef struct ArcNode {
	int adjvex;
	struct ArcNode* nextarc;
}ArcNode, * ArcList;
typedef struct VNode {
	int data;
	ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct {
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

预定义、预处理和基本操作函数如下：

int indegree[MaxVertexNum], print[MaxVertexNum];
//记录各点入度，记录拓扑排序序列

inline void Init(ALGraph& G) {//预处理
	for (int i = 1; i <= G.vexnum; ++i) {
		ArcList h = (ArcList)malloc(sizeof(ArcList));
		h->adjvex = 0;
		h->nextarc = NULL;
		G.vertices[i].data = 0;
		G.vertices[i].firstarc = h;
	}
	memset(indegree, 0, sizeof(indegree));
	memset(print, 0, sizeof(print));
	return;
}

inline void AG_Insert(ALGraph& G, int i, int j) {//头插法加入边
	ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
	p->adjvex = j;
	ArcNode* head = G.vertices[i].firstarc;
	ArcNode* tail = G.vertices[i].firstarc->nextarc;
	p->nextarc = tail;
	head->nextarc = p;
	return;
}

知识点回顾：栈和队列的基本概念

拓扑排序算法的实现如下：和王道书上的不同，我用了静态数组模拟栈的做法。

inline bool Topologicalsort(ALGraph G) {
	int Sta[MaxVertexNum], top = 0, count = 0;
	//用静态数组模拟栈，top为栈顶指针，count为拓扑序列数组下表
	memset(Sta, 0, sizeof(Sta));
	int i;
	for (i = 1; i <= G.vexnum; ++i)
		if (!indegree[i])Sta[++top] = i;//将初始入度为0的顶点进栈
	while (top) {//当栈不空时
		i = Sta[top--];//栈顶元素出栈
		print[++count] = i;//输出顶点i
		for (ArcNode* p = G.vertices[i].firstarc; p != NULL; p = p->nextarc) {
			//将所有i指向的顶点入度减1，并将入度减为0的顶点压入栈Sta中
			int v = p->adjvex;
			if (!v)continue;
			if (!(--indegree[v]))
				Sta[++top] = v;//度为0则入栈
			p->adjvex = 0;
		}
	}
	if (count < G.vexnum)return false;//排序失败，图中存在回路
	else return true;//拓扑排序成功
}

对采用不同存储方式存储的图，拓扑排序的时间复杂度也不同。采用邻接表存储时，拓扑排序的时间复杂度为$O(|V|+|E|)$，采用邻接矩阵存储时，拓扑排序的时间复杂度为$O(|V{|}^2)$。

用拓扑排序算法处理$AOV$网时，应注意以下问题：

1. 入度为$0$的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
2. 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
3. 由于$AOV$网中各顶点的地位平等，每个顶点的编号是人为的，因此可以按拓扑排序的结果重新编号，生成的$AOV$网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

$DFS$实现拓扑排序的思想

知识点回顾：图的遍历

对于一个有向无环图$G$，其任意结点$u,v$，它们之间的关系必然满足下列三种之一。

1. 若$u$是$v$的祖先，则在调用$DFS$访问$u$之前，必然已经对$v$进行过$DFS$访问，即$v$的$DFS$访问顺序先于$u$。从而可考虑在$DFS$函数中设置一个时间标记，在$DFS$调用结束时，对各顶点即使。因此，祖先的结束时间必然大于子孙的结束时间。
2. 若$u$是$v$的子孙，则$v$为$u$的祖先，按1中的思路，$v$的结束时间大于$u$的结束时间。
3. 若$u$和$v$没有路径关系，则$u$和$v$在拓扑序列的关系任意。

于是按结束时间从大到小排列，就可以得到一个拓扑排序序列。
代码实现如下：

int tim, finishtime[MaxVertexNum];
bool visited[MaxVertexNum];//访问标记数组

inline void DFSTravere(ALGraph G) {
	memset(visited, false, sizeof(visited));//初始化
	memset(finishtime, 0, sizeof(finishtime));
	tim = 0;
	for (int i = 1; i <= G.vexnum; ++i)//从第一个顶点开始深搜
		if (!visited[i])DFS(G, i);
	return;
}

inline void DFS(ALGraph G, int v) {
	visited[v] = true;
	for (ArcNode* p = G.vertices[v].firstarc->nextarc; p != NULL; p = p->nextarc) {
		int w = p->adjvex;//依次遍历当前顶点的邻边未访问的顶点
		if (!visited[w])DFS(G, w);
	}
	finishtime[v] = ++tim;//搜索深度越深，tim值越小
	//如果要输出逆拓扑排序序列，只需把这一行改为输出v即可
	return;
}

完整代码可以看我的Github：传送门

例题链接：【洛谷B3644】【模板】拓扑排序 / 家谱树 解题报告

我在这篇题解里写了三种拓扑排序的三种做法，分别是邻接表实现，邻接矩阵实现，邻接表$DFS$实现，感兴趣的读者可以阅读一下。

逆拓扑排序

对一个$AOV$网，如果采用下列步骤进行排序，则称之为逆拓扑排序：
① 从$AOV$网中选择一个没有后继（出度为$0$）的顶点并输出。
② 从网中删除该顶点和所有以它为终点的有向边。
③ 重复①和②直到当前的$AOV$网为空，或者当前网中不存在无后继的顶点为止。后一种情况说明图中存在环。

由逆拓扑排序序列的性质，易知，当图采用邻接表表示法存储时，时间复杂度较高。因为每次删除一个顶点，都需要遍历整个邻接表寻找以这个顶点为终点的边。
（扩展知识：逆邻接表——一种边表保存以顶点表中的点为终点的边的图的存储方式）
用邻接矩阵表示的代码实现如下：（我根据拓扑排序改的，不知道对不对，如有不对请斧正）

inline bool ReverTopoSort() {
	int Sta[N], top = 0, count = 0;//静态数组模拟栈
	memset(Sta, 0, sizeof(Sta));
	int i;
	for (i = 1; i <= n; ++i)
		if (!outdegree[i])Sta[++top] = i;//出度为0的点入栈
	while (top) {//当栈不为空时
		i = Sta[top--];//弹出栈顶元素
		print[++count] = i;//输出
		for (int j = 1; j <= n; ++j)
			if (A[j][i]) {//如果有一条j到i的边
				A[j][i] = false, outdegree[j]--;//删除之，使顶点j的出度减1
				if (!outdegree[j])Sta[++top] = j;//如果顶点j的出度为0则入栈
			}
	}
	if (count < n)return false;//有环
	else return true;
}

深度优先搜索（$DFS$）算法输出逆拓扑排序序列则非常简单，只需把最后一行改为直接输出$v$即可（详见前面的代码）。但是判环操作还需加上额外的条件，感兴趣的读者可以自行思考。（我就是懒得想了

对有向无环图描述表达式，408初试一般考查手推，而拓扑排序则会考察代码相关的综合题，需要结合例题深入理解相关知识点。
以上。