408数据结构-图的应用3-有向无环图、拓扑排序 自学知识点整理
前置知识：表达式，图的遍历
有向无环图描述表达式
有向无环图：若一个有向图中不存在环，则称为有向无环图，简称 D A G DAG DAG图 。
（图片来自王道考研408数据结构2025）
由王道考研-咸鱼学长的讲解方法（视频传送门），这一类题目有一个通解，具体步骤如下：
- S t e p 1 Step\ 1 Step 1：把各个操作数不重复地排成一排。
- S t e p 2 Step\ 2 Step 2：标出各个运算符的生效顺序（同级别之间任意）。
- S t e p 3 Step\ 3 Step 3：按顺序加入运算符，注意“分层”。（若某个运算符的执行要基于另一个运算符和操作数的执行结果来进行，则前一个运算符在后一个的“上一层”）
-
S
t
e
p
4
Step\ 4
Step 4：从底层向上逐层检查，看同层的运算符是否可以“合体”。
检查完毕后，得出的表达式的 D A G DAG DAG图就是顶点数最小的。
注意：在表达式的有向无环图表示中，不可能出现重复的操作数顶点。
拓扑排序
A O V AOV AOV网：若用 D A G DAG DAG图表示一个工程，其顶点表示活动，用有向边 表示活动 V i V_i Vi必须先于活动 V j V_j Vj进行这样一种关系，则将这种有向图称为顶点表示活动的网络，简称 A O V AOV AOV网。在 A O V AOV AOV网中，活动 V i V_i Vi是活动 V j V_j Vj的直接前驱， V j V_j Vj是 V i V_i Vi的直接后继，这种前驱和后继关系具有传递性，且任何活动 V i V_i Vi不能以它自己作为自己的前驱或后继。
拓扑排序：在图论中，由一个 D A G DAG DAG图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
- 每个顶点出现且仅出现一次。
- 若顶点
A
A
A在序列中排在顶点
B
B
B的前面，则在图中不存在从
B
B
B到
A
A
A的路径。
或定义为：拓扑排序是对有向无环图的一种排序，它使得若存在一条从顶点 A A A到顶点 B B B的路径，则在排序中 B B B出现在 A A A的后面。每个 A O V AOV AOV网都有一个或多个拓扑排序序列。
简而言之，拓扑排序就是这样的一种排序：如果顶点 A A A到顶点 B B B有路， B B B到 A A A没有，那么 A A A排 B B B前面。由此可见，入度为 0 0 0的顶点在拓扑排序序列里一定是在最前面的。
对一个 A O V AOV AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：
① 从 A O V AOV AOV网中选择一个没有前驱（入度为 0 0 0）的顶点并输出。
② 从网中删除该顶点和所有以它为起点的有向边。
③ 重复①和②直到当前的 A O V AOV AOV网为空或者当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。（那就不是 D A G DAG 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 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 //当栈不空时 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对采用不同存储方式存储的图，拓扑排序的时间复杂度也不同。采用邻接表存储时，拓扑排序的时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)，采用邻接矩阵存储时，拓扑排序的时间复杂度为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)。
用拓扑排序算法处理 A O V AOV AOV网时，应注意以下问题：
- 入度为 0 0 0的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
- 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
- 由于 A O V AOV AOV网中各顶点的地位平等，每个顶点的编号是人为的，因此可以按拓扑排序的结果重新编号，生成的 A O V AOV AOV网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。
D F S DFS DFS实现拓扑排序的思想
知识点回顾：图的遍历
对于一个有向无环图 G G G，其任意结点 u , v u,v u,v，它们之间的关系必然满足下列三种之一。
- 若 u u u是 v v v的祖先，则在调用 D F S DFS DFS访问 u u u之前，必然已经对 v v v进行过 D F S DFS DFS访问，即 v v v的 D F S DFS DFS访问顺序先于 u u u。从而可考虑在 D F S DFS DFS函数中设置一个时间标记，在 D F S DFS DFS调用结束时，对各顶点即使。因此，祖先的结束时间必然大于子孙的结束时间。
- 若 u u u是 v v v的子孙，则 v v v为 u u u的祖先，按1中的思路， v v v的结束时间大于 u u u的结束时间。
- 若 u u u和 v v v没有路径关系，则 u u u和 v v 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 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】【模板】拓扑排序 / 家谱树 解题报告
我在这篇题解里写了三种拓扑排序的三种做法，分别是邻接表实现，邻接矩阵实现，邻接表 D F S DFS DFS实现，感兴趣的读者可以阅读一下。
逆拓扑排序
对一个 A O V AOV AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序：
① 从 A O V AOV AOV网中选择一个没有后继（出度为 0 0 0）的顶点并输出。
② 从网中删除该顶点和所有以它为终点的有向边。
③ 重复①和②直到当前的 A O V AOV AOV网为空，或者当前网中不存在无后继的顶点为止。后一种情况说明图中存在环。
由逆拓扑排序序列的性质，易知，当图采用邻接表表示法存储时，时间复杂度较高。因为每次删除一个顶点，都需要遍历整个邻接表寻找以这个顶点为终点的边。
（扩展知识：逆邻接表——一种边表保存以顶点表中的点为终点的边的图的存储方式）
用邻接矩阵表示的代码实现如下：（我根据拓扑排序改的，不知道对不对，如有不对请斧正）
inline bool ReverTopoSort() { int Sta[N], top = 0, count = 0;//静态数组模拟栈 memset(Sta, 0, sizeof(Sta)); int i; for (i = 1; i //当栈不为空时 i = Sta[top--];//弹出栈顶元素 print[++count] = i;//输出 for (int j = 1; j //如果有一条j到i的边 A[j][i] = false, outdegree[j]--;//删除之，使顶点j的出度减1 if (!outdegree[j])Sta[++top] = j;//如果顶点j的出度为0则入栈 } } if (count
