拓扑排序

古城微笑少年丶 2022-03-18 12:35 282阅读 0赞

（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;
    }