数据结构与算法－拓扑排序
在工程实践中，一个工程往往由若干个子项目组成，这些子项目中往往有两种关系。
1. 先后关系，即必须在一个子项目完成后，才能开始实施另一个子项目。
2. 子项目间无关系，即两个子项目可以同时进行，互不影响。
为了保证总项目的顺利进行，必须要对这些子项目进行一定的先后顺序规化，为了解决这类问题，我们可以采用拓扑排序的方法。
1. AOV网
工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。如果以图中的顶点来表示活动，有向边表示活动之间的优先关系，这种用顶点表示的活动有向图称为AVO网。
假设计算机专业的课程存在下表所示的关系。
如上表所示，那么课程之间的先后关系可用如下AOV网表示。
2. 拓扑排序
若在有向图G中，从顶点Vi到Vj有一条路径，则在拓扑序列中顶点Vi必须排在Vj之前，在一个有向图中，将所有顶点按这个规则进行拓扑序列的过程称为拓扑排序。完成拓扑排序的前提是AOV网中不允许出现回路。
下面给出有向图拓扑排序的基本步骤。
1. 从有向图中选择一个入度为0的顶点，输出该顶点；
2. 从图中删除该项点及其相关联的弧，调整被删弧的弧头结点的入度，将入度减1；
3. 重复执行上面这两步操作，直到所有入度为0的顶点均被输出，或者图中再也没有入度为0的顶点，拓扑排序完成；
可以证明，任何一个无环的有向图，其全部顶点可以排列成一个拓扑序列。
例1：下图是一个拓扑排序的过程示意图，拓扑序列为C1、C2、C5、C4、C3。
例2：下图是一个有向图及其邻接表，拓扑序列为C0、C1、C3、C2、C4.
第一步：由于C0和C3的度为0，选C0，删除C0及其边e1和e2，调整C1的入度为0，C2的入度为1；
第二步：由于C1和C3的入度为0，选C3，删除C3及边e3，调整C2的入度为0；
第三步：由于C1和C3的入度为0，选C1，删除C1及边e4，调整C4的入度为1；
第四步：由于只C2的入度为0，删除C2及边e5，调整C4的入度为0；
第五步：输入C4，至此拓扑排序完成。
拓扑排序算法实现：
#include <iostream>
using namespace std;
#define N 13
int main(){
// 邻接矩阵
int map[N][N];
// 初始化矩阵的值全部为0表示各个顶点间没有边连接
for (int i = 0; i <= N - 1; i++){
for (int j = 0; j <= N - 1; j++){
map[i][j] = 0;
}
}
// 定义两个变量，用来输入
int a, b;
// 顶点数和边数
int v, l;
cout << "请输入顶点数：";
cin >> v;
cout << "请输入边数：";
cin >> l;
cout << "请输入边：" << endl;
for (int i = 1; i <= l; i++){
cin >> a >> b;
// 表示顶点a指向顶点b的边
map[a][b] = 1;
}
cout << "邻接矩阵如下所示\n"<< endl;
for (int i = 1; i <= N - 1; i++){
for (int j = 1; j <= N - 1; j++){
cout << map[i][j];
}
cout << endl;
}
// 用于计算度数
int k;
// 用于存放入度
int ID[N];
// 计算入度
for (int i = 1; i <= v; i++){
k = 0;
for (int j = 1; j <= v; j++){
// 如果顶点j到顶点i有边，则顶点i的入度+1
if (map[j][i] == 1){
k++;
}
}
ID[i] = k;
}
// 在有向图中选一个没有前驱的顶点并且输出
cout << "拓扑序列： ";
// 最后用来判断是否所有的顶点输出
int count = 0;
while (1){
for (int i = 1; i <= v; i++){
if (ID[i] == 0){
// 输出顶点
cout << i << " ";
count++;
// 从图中删除该顶点和所有以它为尾的弧，即删除所有与它有关的边
// 将此顶点入度设为-1，表示删除
ID[i] = -1;
for (int j = 1; j <= v; j++){
// 如果顶点j与顶点i有边，则删除这条边，并且顶点j的入度-1
if (map[i][j] == 1){
ID[j]--;
}
}
}
}
// 重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止
// 若count == 顶点数，表示所有顶点的入度都为-1，即所有的边均已输出，停止操作
if (count == v){
break;
}
}
return 0;
}拓扑排序算法的时间复杂度为O(n+e)，n是图的顶点个数，e是图的弧的数目。
腾讯云开发者
