拓扑排序-蒲公英云

（1）有向无环图

无环的有向图，简称 DAG (Directed Acycline Graph) 图。

有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几乎所有的工程都可分为若干个称作“活动”的子工程，并且这些子工程之间通常受着一定条件的约束，例如：其中某些子工程必须在另一些子工程完成之后才能开始。
对整个工程和系统，人们关心的是两方面的问题：
①工程能否顺利进行；
②完成整个工程所必须的最短时间。
对应到有向图即为进行拓扑排序和求关键路径。
AOV网：
用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网(Activity On Vertex network)。
例如：排课表

AOV网的特点：
①若从i到j有一条有向路径，则i是j的前驱；j是i的后继。
②若< i , j >是网中有向边，则i是j的直接前驱；j是i的直接后继。
③AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

问题：
问题：如何判别 AOV 网中是否存在回路？
检测 AOV 网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

拓扑排序的方法：
①在有向图中选一个没有前驱的顶点且输出之。
②从图中删除该顶点和所有以它为尾的弧。
③重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。

一个AOV网的拓扑序列不是唯一的！
代码实现：

Status TopologicalSort(ALGraph G)
    //有向图G采用邻接表存储结构。
    //若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR.
    //输出次序按照栈的后进先出原则，删除顶点，输出遍历
{
    SqStack S;
    int i, count;
    int *indegree1 = (int *)malloc(sizeof(int) * G.vexnum);
    int indegree[12] = {0};
    FindInDegree(G, indegree);    //求个顶点的入度下标从0开始
    InitStack(&S);
    PrintStack(S);
    for(i = 0; i < G.vexnum; ++i)
        if(!indegree[i])        //建0入度顶点栈S
            push(&S,i);        //入度为0者进栈
    count = 0;                //对输出顶点计数
    while (S.base != S.top)
    {
        ArcNode* p;
        pop(&S,&i);
        VisitFunc(G,i);//第i个输出栈顶元素对应的顶点，也就是最后进来的顶点    
        ++count;          //输出i号顶点并计数
        for(p = G.vertices[i].firstarc; p; p = p->nextarc)
        {    //通过循环遍历第i个顶点的表结点，将表结点中入度都减1
            int k = p->adjvex;    //对i号顶点的每个邻接点的入度减1
            if(!(--indegree[k]))
                push(&S,k);        //若入度减为0，则入栈
        }//for
    }//while
    if(count < G.vexnum)
    {
        printf("\n该有向图有回路!\n");
        return ERROR;    //该有向图有回路
    }
    else
    {
        printf("\n该有向图没有回路!\n");
        return OK;
    }
}

关键路径

把工程计划表示为有向图，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。称这种有向图为边表示活动的网，简称为 AOE网 (Activity On Edge)。
例如：
设一个工程有11项活动，9个事件。
事件v_1——表示整个工程开始（源点）
事件v_9——表示整个工程结束（汇点）

对AOE网，我们关心两个问题：
①完成整项工程至少需要多少时间？
②哪些活动是影响工程进度的关键？
关键路径——路径长度最长的路径。
路径长度——路径上各活动持续时间之和。
v_i——表示事件v_i的最早发生时间。假设开始点是v_1，从v_1到〖v�i〗的最长路径长度。ⅇ(ⅈ)——表示活动a_i的最早发生时间。
l(ⅈ)——表示活动a_i最迟发生时间。在不推迟整个工程完成的前提下，活动a_i最迟必须开始进行的时间。
l(ⅈ)-ⅇ(ⅈ)意味着完成活动a_i的时间余量。
我们把l(ⅈ)=ⅇ(ⅈ)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程进度。
例如上图中网，从从v_1到v_9的最长路径是(v_1,v_2,v_5,v_8,ν_9 )，路径长度是18，即ν_9的最迟发生时间是18。而活动a_6的最早开始时间是5，最迟开始时间是8，这意味着：如果a_6推迟3天或者延迟3天完成，都不会影响整个工程的完成。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。
由上面介绍可知：辨别关键活动是要找l(ⅈ)=ⅇ(ⅈ)的活动。为了求ⅇ(ⅈ)和l(ⅈ)，首先应求得事件的最早发生时间vⅇ(j)和最迟发生时间vl(j)。如果活动a_i由弧〈j,k〉表示，其持续时间记为dut(〈j,k〉),则有如下关系：
ⅇ(ⅈ)= vⅇ(j)
l(ⅈ)=vl(k)-dut(〈j,k〉)
求vⅇ(j)和vl(j)需分两步进行：
第一步：从vⅇ(0)=0开始向前递推
vⅇ(j)=Max{vⅇ(i)+dut(〈j,k〉)} 〈i,j〉∈T,j=1,2,…,n-1
其中，T是所有以第j个顶点为头的弧的集合。
第二步：从vl(n-1)=vⅇ(n-1)起向后递推
vl(i)=Min{vl(j)-dut(〈i,j〉)} 〈i,j〉∈S,i=n-2,…,0
其中，S是所有以第i个顶点为尾的弧的集合。
下面我们以上图AOE网为例，先求每个事件v_i的最早发生时间，再逆向求每个事件对应的最晚发生时间。再求每个活动的最早发生时间和最晚发生时间，如下面表格：

在活动的统计表中，活动的最早发生时间和最晚发生时间相等的，就是关键活动

关键路径的讨论：

①若网中有几条关键路径，则需加快同时在几条关键路径上的关键活动。如：a11、a10、a8、a7。
②如果一个活动处于所有的关键路径上，则提高这个活动的速度，就能缩短整个工程的完成时间。如：a1、a4。
③处于所有关键路径上的活动完成时间不能缩短太多，否则会使原关键路径变成非关键路径。这时必须重新寻找关键路径。如：a1由6天变成3天，就会改变关键路径。

关键路径算法实现：

int CriticalPath(ALGraph G)
{    //因为G是有向网，输出G的各项关键活动
    SqStack T;
    int i, j;    ArcNode* p;
    int k , dut;
    if(!TopologicalOrder(G,T))
        return 0;
    int vl[VexNum];
    for (i = 0; i < VexNum; i++)
        vl[i] = ve[VexNum - 1];        //初始化顶点事件的最迟发生时间
    while (T.base != T.top)            //按拓扑逆序求各顶点的vl值
    {
        for(pop(&T, &j), p = G.vertices[j].firstarc; p; p = p->nextarc)
        {
            k = p->adjvex;    dut = *(p->info);    //dut<j, k>
            if(vl[k] - dut < vl[j])
                vl[j] = vl[k] - dut;
        }//for
    }//while
    for(j = 0; j < G.vexnum; ++j)    //求ee,el和关键活动
    {
        for (p = G.vertices[j].firstarc; p; p = p->nextarc)
        {
            int ee, el;        char tag;
            k = p->adjvex;    dut = *(p->info);
            ee = ve[j];    el = vl[k] - dut;
            tag = (ee == el) ? '*' : ' ';
            PrintCriticalActivity(G,j,k,dut,ee,el,tag);
        }
    }
    return 1;
}