有向无环图的应用—描述表达式、AOV网、AOE网

目录

一、有向无环图描述表达式

二、拓扑排序

相关概念?

实现方法?

算法代码?

补充

三、关键路径

相关概念?

算法步骤?

补充?

四、总结图的应用我们都学了什么

---

一、有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图。?

对于一个表达式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e),我们可以用下面这个二叉树表示：

但是一些公共子式(c+d)、b和(c+d)*e重复出现，我们可以用有向无环图实现对相同子式的共享，从而节省存储空间，如下图所示：

解题方法

问题：给出一个表达式，请用DAG图描述它。

方法：

1. 先把各个操作数不重复地排成一排。
2. 标出各个运算符的生效顺序。(同时进行的运算符先后顺序无所谓)
3. 按顺序加入运算符，注意同时进行的运算符在同一层。
4. 从底向上逐层检查同层的运算符是否可以合并。

---

有向无环图也是描述一项工程或系统的进行过程的有效工具。几乎所以工程都可以分为若干个称作活动的子工程。而这些子工程之间。通常其中某些子工程的开始必须在另一些子工程完成之后，这就要求是有向的，而一个子工程不能在作为另一个子工程的前驱条件的同时另一个工程的前驱条件也是这一个工程，这就要求是无环的。下面解决两个相关的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间，对应于有向图，即分别为进行拓扑排序和求关键路径的操作。那么因此如果我们接下来给出的操作失败了，说明它是有环的。?

二、拓扑排序

相关概念?

AOV网：若用DAG图表示一个工程，其顶点代表活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行的这样一种关系，则将这样的有向无环图称为顶点表示活动的网络，记为AOV网。

拓扑排序：是对DAG图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

实现方法?

1. 从AOV网中选择一个没有前驱的顶点(入度为0)并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复①和②直到当前的AOV网为空或者当前网中不存在无前驱的顶点为止。后一种情况说明拓扑排序失败，该有向图就不是一个AOV网，该有向网中存在环。

• 使用一个栈(或队列或线性表)，只要能保存入度为0的顶点就行，进行这些顶点活动的顺序不重要，这体现了拓扑排序序列可能具有多个的特点。

算法代码?

采用邻接表存储时间复杂度为O(|V|+|E|)，采用邻接矩阵存储时间复杂度为O(|V^2|)。

bool TopologicalSort(Graph G)
{
    InitStack(s);//初始化栈
    for(int i=0;i<G.vexnum;i++)//先将所以入度为0的顶点入栈
    {
        if(indegree[i]==0) 
            push(s,i);
    }    
        int count=0;//用于计数当前已经输出的顶点
        while(!IsEmpty(s))
        {
            Pop(s,i);//栈不为空时出栈
            print[count++]=i;//拓扑排序序列
            for(p=G.vertices[i].firstarc;p==NULL;=p->nextarc)
            {
                v=p->adjvex;//循环所有i指向的顶点
                if(!(--indegree[v]))//并将入度减1后判断入度是否为0
                    push(s,v);
            }
        }
        if(count<G.vexnum)//判断拓扑排序是否成功
            return false;
        else
            return ture;   
}
    

补充

? ? 逆拓扑排序：

1. 从AOV网中选择一个没有后继的顶点(出度为0)并输出。
2. 从网中删除该顶点和所有以它为终点的有向边。
3. 重复①和②直到当前的AOV网为空或者当前网中不存在无后继的顶点为止。后一种情况说明拓扑排序失败，该有向图就不是一个AOV网，该有向网中存在回路。

? ? 其它问题

• 对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；
• 若一个有向图具有拓扑排序序列，则它的邻接矩阵不一定为三角矩阵，示例：

• 若一个有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为三角矩阵(有序表明我们人为地编号了，那么一定可以为三角矩阵)
• 有向无环图一定可以转化为一个上三角或者下三角矩阵，可能需要调整顶点的编号，对图进行拓扑排序，按照拓扑排序序列，重新调整各个顶点的编号。可以确保，所有的弧都是从小编号顶点指向大编号顶点的。
• 如 拓扑排序序列为 0 1 2 4 6 7 5 3 调整编号为? 0 1 2 3 4 5 6 7
• 若有向图的拓扑排序有序序列唯一，则图中每个顶点的入度和出度最多为1。←这句话是错的，反例为上图。
• 若有向无环图的拓扑序列唯一，则可唯一确定该图。←这句话是错的，反例为上图还可加上一个弧<1,4>。

三、关键路径

相关概念?

AOE网:在带权DAG图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需要的时间)，称之为用边表示活动的网络，简称AOE网。

AOE网具有以下三个规定：

• 只有在某顶点代表的事情V3发生后，从该顶点出发的各有向边代表的活动a4才能开始。
• 只有在进入某顶点的各有向边代表的活动a1和a3全都结束时，该顶点代表的事情V3才能发生。
• 不同于AOV图，AOE图仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始；也仅存在一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。

从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

1. ?事件的最早发生时间ve(k):它是指从源点V到顶点的最长路径长度。事件的最早发生时间决定了所有从开始的活动能够最早开工的时间。
2. 事件的最迟发生时间vl(k):它是指在不推迟整个工程完成的前提下，即保证它的后继事件Vj在其最迟发生时间vl(k)能够发生时，该事件最迟必须发生的时间。
3. 活动最早开始时间e(i):它是指该活动弧的起点所代表的事件的最早发生时间ve(k)。
4. 活动最迟开始时间l(i)：它是指该活动弧的终点所代表的事件的最迟发生时间与该活动所需的时间之差vl(j)-weight(,)
5. 一个活动的最迟开始时间l(i)与其最早开始时间e(i)的差额d(i)=l(i)-e(i)：它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的前提下，活动可以拖延的时间。l(i)=e(i)的活动为关键活动。

算法步骤?

1. 从源点出发，令ve(源点)=0，按拓扑有序求其余顶点的最早发生时间ve()。
2. 从汇点出发，令vl(汇点)=ve(汇点)，按逆拓扑有序求其余顶点的最迟发生时间vl()。
3. 根据各顶点的ve()值求所有弧的最早开始时间e()。
4. 根据各顶点的vl()值求所有弧的最迟开始时间l()。
5. 求AOE网中所有活动的差额d()，找出所有d()=0的活动构成关键路径。

补充?

• 可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变为非关键活动。
• 网中的关键路径并不一定唯一，对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期。加快那些包括在所有关键路径上的关键活动才能更有效地达到缩短工期的目的。

四、总结图的应用我们都学了什么

辨析点为有向还是无向，带权还是无权(解决带权问题相当于解决无权问题)，是否有回路(没指出就是可以允许有回路)。

• 最小生成树是针对带权连通图。有Prim(普里姆)算法和 Kruskal(克鲁斯卡尔)算法。

• DAG图(有向无环图)描述表达式。
• 拓扑排序是针对AOV网，一种无权有向无环图的应用:工程能否顺利进行。
• 求关键路径是针对AOE网，一种带权有向无环图的应用:估算整个工程完成所必须的最短时间。