数据结构：拓扑排序

拓扑排序是一种对有向无环图（DAG）中的节点进行排序的算法。拓扑排序在实际应用中具有重要意义，可以帮助我们解决诸如任务调度、依赖关系分析等问题。同时，拓扑排序也可以用来检测有向图是否存在环路，如果图中存在环路，则无法进行拓扑排序。拓扑排序是一种常用且有效的图算法，对于理解和处理有向无环图具有重要意义。

一、基本概念

1.1、DAG图

一个无回路的有向图称作有向无环图（Directed Acyclic Graph），简称DAG图。

有向无环图是描述工程实施过程的有效工具。通常把计划、施工、生产等环节都看作一个工程。除了很小的工程外，一般的工程都可分为若干个称做活动（Activity）的子工程，而这些子工程之间，通常有着一定条件的约束，如某些子工程完成后，另一些子工程才能开始。

例如，一个软件专业的学生必须学习一系列基本课程，其中有些课程是基础课，独立于其他课程，如《高等数学》；有些课程则必须学完其先修课程才能开始，如学习《数据结构》之前必须先学完《程序设计基础》和《离散数学》。这些先决条件定义了课程之间的优先关系，这个关系可以用有向图表示，如下图所示。图中顶点表示课程，有向弧表示先决条件。若课程i是课程j的先决条件，则图中有弧<i, j>。

1.2、AOV网

AOV网，是指以顶点表示活动的网（Activity On Vertex Network）。它是一个特殊的有向无环图，用顶点表示活动、用弧表示活动间的优先关系。在AOV网中，若从顶点 $v_i$ 到顶点 $v_j$ 有一条有向路径，则 $v_i$ 是 $v_j$ 的前驱； $v_j$ 是 $v_i$ 的后继。若 $<v_i , v_j>$ 是网中的一条弧，则 $v_i$ 是 $v_j$ 的直接前驱， $v_j$ 是 $v_i$ 的直接后继。

在AOV网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。显然，这是荒谬的。若设计出这样的流程图，工程便无法进行；而对程序的数据流图来说，则表明存在一个死循环。因此，对给定的AOV网应首先判定网中是否存在环。检测的办法是对有向图的顶点进行拓扑排序，若网中所有顶点都在它的拓扑有序序列中，则该AOV网中必定不存在环。

1.3、拓扑排序

所谓拓扑排序，就是将AOV网中的所有顶点排成一个线性序列，该序列满足：若在AOV网中从顶点 $v_i$ 到顶点 $v_j$ 有一条路径，则在该线性序列中的顶点 $v_i$ 必定在顶点 $v_j$ 之前。例如，在前面的表示课程间优先关系的有向图中，有如下两个拓扑有序序列（当然，对此图也可构造出其他的拓扑有序序列）：

v_1,v_2,v_3,v_4,v_5,v_7,v_9,v_{10},v_{11},v_6,v_{12},v_8

v_9,v_{10},v_{11},v_6,v_1,v_{12},v_4,v_2,v_3,v_5,v_7,v_8

学生必须按照拓扑有序的顺序来安排学习计划，这样才能保证学习任一门课程时其先修课程已经学过。

二、拓扑排序的过程

那么如何进行拓扑排序呢？拓扑排序的过程如下：

在有向图中选一个无前驱的顶点且输出它。
从图中删除该顶点和所有以它为尾的弧。
重复第一步和第二步，直至不存在无前驱的顶点。
若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列即为一个拓扑序列。

例如，下图所示的有向图G：

在该图中，顶点 $v_1$ 和 $v_6$ 没有前驱，则可任选一个。假设先输出 $v_6$ ，在删除 $v_6$ 及弧 $<v_6, v_4>$ ， $<v_6, v_5>$ 之后，只有顶点 $v_1$ 没有前驱，则输出 $v_1$ 且删去 $v_1$ 及弧 $<v_1, v_2>$ 、 $<v_1, v_3>$ 和 $<v_1, v_4>$ ，之后 $v_3$ 和 $v_4$ 都没有前驱。依次类推，可从中任选一个继续进行。最后得到该有向图的拓扑有序序列为

v_6, v_1, v_4, v_3, v_2, v_5

三、拓扑排序的实现

拓扑排序可采用邻接表作为有向图的存储结构。算法实现要引入以下辅助数据结构：

一维数组indegree[i]：存放各顶点入度，没有前驱的顶点就是入度为零的顶点。删除顶点及以它为尾的弧的操作，可不必真正对图的存储结构进行改变，可用弧头顶点的入度减1的办法来实现。
栈S：暂存所有入度为零的顶点，这样可以避免重复扫描数组indegree检测入度为0的顶点，提高算法的效率。
一维数组topo[i]：记录拓扑序列的顶点序号。

拓扑排序的算法步骤为：

求出各顶点的入度存入数组indegree[i]中，并将入度为0的顶点入栈。
只要栈不为空，就重复以下操作：
- 栈顶顶点 $v_i$ 出栈并保存在拓扑序列数组topo中；
- 对顶点 $v_i$ 的每个邻接点 $v_k$ 的入度减一，如果 $v_k$ 的入度变为0，则将 $v_k$ 入栈。
如果输出顶点个数少于AOV网的顶点个数，则网中存在有向环，无法进行拓扑排序，否则拓扑排序成功。

拓扑排序算法的C语言描述如下：

// 对采用邻接表作为存储结构的有向图G进行拓扑排序
// 若G无回路，则生成G的一个拓扑序列topo[]并返回OK，否则返回ERROR
Status TopologicalSort(ALGraph G, int topo[]) {
    // 求出各顶点的入度存入数组indegree中
    FindInDegree(G, indegree);
    // 栈S初始化为空
    InitStack(S);
    // 入度为0者进栈
    for(i=0;i<G.vexnum;++i)
        if(!indegree[i]) Push(S,i);

    // 对输入顶点计数，初始为0
    m=0;
    // 栈S非空
    while(!StackEmpty(S)) {
        // 栈顶顶点vi出栈
        Pop(S,i);
        // 将vi保存在拓扑序列数组topo中
        topo[m]=i;
        // p指向vi的第一个邻接点
        p=G.vertices[i].firstarc;
        while(p!=NULL) {
            // vk为vi的邻接点
            k=p->adjvex;
            // vi的每个邻接点的入度减1
            --indegree[k];
            // 若入度减为0，则入栈
            if(indegree[k]==0) Push(S,k);
            // p指向顶点vi的下一个邻接顶点
            p=p->nextarc;
        }
        // 对输出顶点计数
        ++m;
    }

    // 输出的顶点个数少于图中顶点个数返回ERROR，否则返回OK
    if(m<G.vexnum) return ERROR;
    else return OK;
}