AOV网

AOV网：用顶点表示活动的网。

用DAG图(有向无环图)表示一个工程，顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于vj进行

拓扑排序（找到做事的先后顺序）

对有回路的图进行拓扑排序

拓扑排序的实现代码

回顾：入度即为以顶点为终点的边的数目

#include <stdio.h>// 假设已经定义了Graph结构体和相关函数bool TopologicalSort(Graph G) {// 初始化一个栈S，用于存储入度为0的顶点InitStack(S);// 遍历所有顶点，寻找入度为0的顶点并将其压入栈Sfor (int i = 0; i < G.vexnum; i++)if (indegree[i] == 0) // 如果顶点i的入度为0Push(S, i); // 将顶点i压入栈S// 初始化计数器，用于记录已经输出的顶点数int count = 0;// 当栈S不为空时，循环执行以下操作while (!IsEmpty(S)) {// 弹出栈顶元素，并将其赋值给变量iPop(S, i);// 将顶点i记录在输出数组print中，并增加计数器print[count++] = i;// 遍历顶点i的所有邻接顶点for (p = G.vertices[i].firstarc; p; p = p->nextarc) {// 获取顶点i指向的顶点vv = p->adjvex;// 将顶点v的入度减一if (!(--indegree[v]))// 如果顶点v的入度减为0，则将其压入栈SPush(S, v);}}//while循环结束// 如果输出的顶点数小于图中顶点的总数，说明有向图中有回路，拓扑排序失败if (count < G.vexnum)return false;else// 否则，拓扑排序成功return true;
}

代码思路：

通过for循环将所有度为0结点的indgree[]下标压入栈中，并初始化print[]数组，使其所有元素为-1，方便记录，再将count指向第一个print数组元素，任何进行while判断，如果栈不为空，则将栈顶元素i弹出栈并进入print数组，count指向下一个数组元素，再通过for循环遍历图中i的所有邻结点，将其度-1，若度为零则将度为0的indree数组元素压入栈中，重复直到栈中没有元素，若print数组中的元素小于图中顶点总数，则有向图中有回路。

拓扑排序的时间复杂度

逆拓扑排序

#include <stdio.h>// 假设已经定义了Graph结构体和相关函数，以下是逆拓扑排序的代码bool ReverseTopologicalSort(Graph G){// 初始化一个栈S，用于存储出度为0的顶点InitStack(S);// 遍历所有顶点，寻找出度为0的顶点并将其压入栈Sfor (int i = 0; i < G.vexnum; i++)if (outdegree[i] == 0) // 如果顶点i的出度为0Push(S, i); // 将顶点i压入栈S// 初始化计数器，用于记录已经输出的顶点数int count = 0;// 当栈S不为空时，循环执行以下操作while (!IsEmpty(S)) {// 弹出栈顶元素，并将其赋值给变量iPop(S, i);// 将顶点i记录在输出数组print中，并增加计数器print[count++] = i;// 遍历顶点i的所有邻接顶点for (p = G.vertices[i].firstarc; p; p = p->nextarc) {// 获取顶点i指向的顶点vv = p->adjvex;// 将顶点v的出度减一if (!(--outdegree[v]))// 如果顶点v的出度减为0，则将其压入栈SPush(S, v);}}//while循环结束// 如果输出的顶点数小于图中顶点的总数，说明有向图中有回路，逆拓扑排序失败if (count < G.vexnum)return false;else// 否则，逆拓扑排序成功return true;
}

 使用邻接矩阵进行拓扑排序

#include <stdio.h>// 假设已经定义了Graph结构体和相关函数，以下是逆拓扑排序的代码// Graph结构体可能如下定义
typedef struct {int vexnum;       // 顶点数int **arc;        // 邻接矩阵int *outdegree;   // 每个顶点的出度数组
} Graph;bool ReverseTopologicalSort(Graph G) {int stack[G.vexnum]; // 使用数组作为栈，存储出度为0的顶点int top = -1;        // 栈顶指针int count = 0;       // 记录已经输出的顶点数int print[G.vexnum]; // 存储逆拓扑排序的结果int i, j;// 初始化栈和输出数组for (i = 0; i < G.vexnum; i++) {if (G.outdegree[i] == 0) {stack[++top] = i; // 出度为0的顶点入栈}}// 当栈不为空时，执行以下操作while (top != -1) {i = stack[top--]; // 出栈print[count++] = i; // 输出顶点i// 遍历邻接矩阵的第i行for (j = 0; j < G.vexnum; j++) {// 如果顶点i到顶点j有边，则减少顶点j的出度if (G.arc[i][j]) {G.outdegree[j]--;// 如果顶点j的出度变为0，则将其入栈if (G.outdegree[j] == 0) {stack[++top] = j;}}}}// 如果输出的顶点数小于图中顶点的总数，说明有向图中有回路，逆拓扑排序失败if (count < G.vexnum) {return false;} else {// 否则，逆拓扑排序成功return true;}
}

逆拓扑排序的实现（DFS算法）

总结：