在工程实践中,一个工程往往由若干个子项目组成,这些子项目中往往有两种关系。
1. 先后关系,即必须在一个子项目完成后,才能开始实施另一个子项目。
2. 子项目间无关系,即两个子项目可以同时进行,互不影响。
为了保证总项目的顺利进行,必须要对这些子项目进行一定的先后顺序规化,为了解决这类问题,我们可以采用拓扑排序的方法。
工程或者某种流程可以分为若干个小的工程或阶段,这些小的工程或阶段就称为活动。如果以图中的顶点来表示活动,有向边表示活动之间的优先关系,这种用顶点表示的活动有向图称为AVO网。
假设计算机专业的课程存在下表所示的关系。
如上表所示,那么课程之间的先后关系可用如下AOV网表示。
若在有向图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是图的弧的数目。