数据结构与算法－拓扑排序

在工程实践中，一个工程往往由若干个子项目组成，这些子项目中往往有两种关系。

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是图的弧的数目。