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

这篇具有很好参考价值的文章主要介绍了有向无环图的应用—描述表达式、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(克鲁斯卡尔)算法。

有向无环图描述表达式,数据结构,算法,数据结构,图论文章来源地址https://www.toymoban.com/news/detail-524713.html

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

到了这里,关于有向无环图的应用—描述表达式、AOV网、AOE网的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 有向无环图——AOV网(拓扑排序)

    有向无环图: 无环的有向图,简称 DAG 图(Directed Acycline Graph) 有向无环图常用来描述一个工程或系统的进行过程。(通常吧计划、施工、生产、程序流程等当成是一个工程) 一个工程可以分为若干个 子工程,只要完成了这些子工程(活动),就可以导致整个工程的完成 AOV网

    2024年02月11日
    浏览(83)
  • 【数据结构】有向无环图(AOE-网)的关键路径(C语言)

    把用顶点表示事件,用弧表示活动,弧的权值表示活动所需要的时间的有向无环图称为 边表示活动的网 ,简称 AOE-网 。 在AOE-网中存在唯一的、入度为0的顶点,称为 源点 ;存在唯一的、出度为0的顶点,称为 汇点 。从源点到汇点的最长路径长度即为完成整个工程任务所需的

    2024年02月07日
    浏览(42)
  • 【海量数据挖掘/数据分析】之 贝叶斯信念网络(贝叶斯信念网络、有向无环图、贝叶斯公式、贝叶斯信念网络计算实例)

    目录 【海量数据挖掘/数据分析】之 贝叶斯信念网络(贝叶斯信念网络、有向无环图、贝叶斯公式、贝叶斯信念网络计算实例) 一、贝叶斯信念网络 1 . 属性关联 : 贝叶斯信念网络 允许数据集样本属性 之间存在依赖关系 ; 2 . 贝叶斯信念网络 表示方法 : 二、概率图模型 : 马尔

    2024年02月12日
    浏览(51)
  • 从零构建深度学习推理框架-7 计算图的表达式

    表达式就是一个计算过程,类似于如下: 用图形来表达就是这样的。 但是在PNNX的表达式(Experssion Layer)中不是这个样子,而是以一种抽象得方式,替换掉输入张量改为@1,@2等等 所以上面的计算图也就变成了 我们是希望把这个抽象的表达式变回到一个方便后端执行的计算过程

    2024年02月13日
    浏览(33)
  • 【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS)

    有向图(Directed Graph),也被称为有向图形或方向图,是一种图的类型。在有向图中,图中的边具有方向,从一个顶点指向另一个顶点。 在有向图中,每个顶点表示一个实体,而有向边则表示实体之间的关系或连接。这种有方向性的边表明了连接的起点和终点之间的单向关系

    2024年02月09日
    浏览(47)
  • 正则表达式应用场景

    数据验证应该是正则表达式最常见的场景了,经常用于用户的输入是否符合所需的条件。数据验证可确保输入或导入的数据准确、一致,并符合预定义的规则。 验证手机号: 验证邮箱: 验证密码(要求:至少包含一个数字,一个字母,一个特殊字符,长度在8~18之间): 验

    2024年02月08日
    浏览(44)
  • 正则表达式应用

    正则匹配以{开头,以}结尾 正则匹配以[开头,以]结尾 校验数字的表达式 数字: ^[0-9]*$ n位的数字: ^d{n}$ 至少n位的数字: ^d{n,}$ m-n位的数字: ^d{m,n}$ 零和非零开头的数字: ^(0|[1-9][0-9]*)$ 非零开头的最多带两位小数的数字: ^([1-9][0-9]*)+(.[0-9]{1,2})?$ 带1-2位小数的正数或负

    2024年02月11日
    浏览(41)
  • 02_正则表达式的应用

    理解正则表达式概述 掌握Js的正则对象Regexp 掌握正则表达式的常见用法 完成页面注册的手机号码校验 1. 正则表达式概述 官方文档:正则表达式 - JavaScript | MDN 正则表达式在线测试 1.1 正则表达式的定义 介绍:正则表达式是用于匹配字符串中字符组合的模式。在 JavaScript 中,

    2024年01月24日
    浏览(38)
  • 中缀表达式求值(栈的应用)

    AcWing算法基础课-3302.表达式求值 给定一个表达式,其中运算符仅包含 +,-,*,/ (加 减 乘 整除),可能包含括号,请你求出表达式的最终值。 注意: 数据保证给定的表达式合法。 题目保证符号 - 只作为减号出现,不会作为负号出现,例如, -1+2 , (2+2)*(-(1+1)+2) 之类表达式均不

    2024年02月05日
    浏览(54)
  • 关于正则表达式中?=、?!、?<=、?<!、?:的理解与应用

    (?=pattern) :正向先行断言,表示匹配位置后面必须紧跟着满足 pattern 的字符串,但不包括这个字符串在匹配结果中。 (?!pattern) :负向先行断言,表示匹配位置后面不能紧跟着满足 pattern 的字符串,也不包括这个字符串在匹配结果中。 (?=pattern) :正向后行断言,表示匹配位置

    2024年02月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包