您好、欢迎来到现金彩票网!
当前位置:欢乐棋牌 > 边集合 >

66-7 有向无环图及应用(修改版)ppt

发布时间:2019-07-18 03:17 来源:未知 编辑:admin

  登录成功,如需使用密码登录,请先进入【个人中心】-【账号管理】-【设置密码】完成设置

  简介:本文档为《6.6-7 有向无环图及应用(修改版)ppt》,可适用于自然科学领域

  *若权利人发现爱问平台上用户上传内容侵犯了其作品的信息网络传播权等合法权益时,请按照平台侵权处理要求书面通知爱问!

  爱问共享资料拥有大量关于6.6-7 有向无环图及应用(修改版).ppt的实用类文档资料,所有文档由知名合作机构以及专业作者提供,线上总资料超过两个亿,保证满足您的需求。

  拓扑排序用顶点边表示活动的网络简称AOV网络(ActivityOnVertices)顶点:一个工程中的活动(Activity)边:活动的顶点间的优先关系(Relation)要解决的问题是:将各个顶点(代表各个活动)排列成一个线性有序的序列使得AOV网络中所有应存在的前驱和后继关系都能得到满足。课程代号课程名先修课程C高等数学C程序设计基础C离散数学C,CC数据结构C,CC高级语言程序设计CC编译方法C,CC操作系统C,CC普通物理CC计算机原理C可以用有向图表示一个工程。在这种有向图中用顶点表示活动。有向边Vi,Vj表示:Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。在AOV网络中如果活动Vi必须在活动Vj之前进行则存在有向边Vi,VjAOV网络中不能出现有向回路即有向环。在AOV网络中如果出现了有向环则意味着某项活动应以自己作为先决条件。因此对给定的AOV网络必须先判断它是否存在有向环。一、什么是拓扑排序将各个顶点(代表各个活动)排列成一个线性有序的序列使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。例如对学生选课工程图进行拓扑排序得到的拓扑有序序列为C,C,C,C,C,C,C,C,C或C,C,C,C,C,C,C,C,C例如对学生选课工程图进行拓扑排序得到的拓扑有序序列为C,C,C,C,C,C,C,C,C或C,C,C,C,C,C,C,C,C二、进行拓扑排序的方法首先建立(n个顶点的)AOV网。()在AOV网络中选一个没有直接前驱的顶点(入度为的顶点),并输出之()从图中删去该顶点,同时删去所有它发出的边重复()和()直到全部顶点均已输出拓扑有序序列形成拓扑排序完成若图中还有未输出的顶点但已跳出处理循环。这说明图中存在环。vvvvv三、拓扑排序的过程有向无环图vvvvvvv()输出顶点v()输出顶点v()输出顶点v()输出顶点v()输出顶点v()输出顶点vvvvvv三、拓扑排序的过程有向无环图vvvvvvv()输出顶点v()输出顶点v()输出顶点v()输出顶点v()输出顶点v()输出顶点v四、存储结构(邻接表)vvvvvvidvexfirstdataarcvvvvvvadjvexnextarctypedefstructarcnode{intadjvexarcnode*nextarc}*pointer表结点structnode{charvexdataintid顶点的入度pointerfirstarc}dig一组头结点在邻接表的头结点中增设了一个数据项id记录该顶点的入度。入度为零的顶点即无前驱的顶点。在拓扑排序算法中使用一个存放入度为零的顶点的链式栈供选择和输出无前驱的顶点。只要出现入度为零的顶点就将它加入栈中。五、拓扑排序算法思想:()建立入度为零的顶点栈()当入度为零的顶点栈不空时,重复执行:()从顶点栈中退出一个顶点,并输出之()从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一()如果边的终顶点入度减至,则该顶点进入度为零的顶点栈()如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。将顶点i进栈时执行以下指针的修改:digiid=toptop=itop指向新栈顶i,原栈顶元素放在idi中退栈操作可以写成:j=toptop=digtopid位于栈顶的顶点的位置记于j,top退到次栈顶六、拓扑排序的算法voidtoposort(){inistack(s)置空栈for(i=i=ni)if(digiid==)push(si)入度为零的顶点栈count=count为计数器,计输出顶点数while(!stackempty(s)){j=pop(s)printf(digjvexdata)countq=digjfirstarcq指示以vj为尾的第一条弧结点while(q){k=qadjvex顶点vk为vj的直接后继digkidif(digkid==)push(s,k)新的入度为零的顶点入栈q=qnextarc}}if(countn)error(“该图中存在回路”)}分析此拓扑排序算法可知如果AOV网络有n个顶点e条边在拓扑排序的过程中搜索入度为零的顶点建立链式栈所需要的时间是O(n)。在正常的情况下有向图有n个顶点每个顶点进一次栈出一次栈共输出n次。顶点入度减一的运算共执行了e次。所以总的时间复杂度为O(ne)。关键路径用边表示活动的网络简称AOE网络(ActivityOnEdges)边:一个工程中的活动(Activity)边上权值:活动持续时间(Duration)顶点:事件(Event)要解决的问题是:()完成整个工程至少需要多少时间(假设网络中没有环)()为缩短完成工程所需的时间,应当加快哪些活动完成整个工程所需的时间取决于从源点到汇点的最长路径长度即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。定义几个与计算关键活动有关的量:()事件Vj的最早可能开始时间Ve(j)从源点V到顶点Vj的最长路径长度。()事件Vi的最迟允许开始时间Vli在保证汇点Vn在Ven时刻完成的前提下事件Vi的允许的最迟开始时间。Ve()=Ve(j)=max{Ve(i)i,j的权}Vl(n)=Ve(n)Vl(i)=min{Vl(j)i,j的权}a=a=a=a=a=a=a=a=a=a=VeVl关键路径:小结一、熟悉图的各种存储结构(了解实际问题与采取何种存储和算法有密切联系)二、掌握遍历图的递归和非递归算法并应用图的遍历算法求解各种简单路径问题三、理解教科书中讨论的各种图的算法。四、掌握构造最小生成树的方法求拓扑排序的方法求解关键路径的方法求解最短路径的Dijkstra方法。图是一种比树更复杂的、非线性的数据结构一个图由顶点集合(是非空有限集合)和边集合(可以是空集合)组成。图的存储表示有邻接矩阵、邻接表、邻接多重表和十字链表等。以前两种最常用。图的邻接矩阵元素个数与顶点有关非零元素个数与边有关图的邻接表既与顶点个数n有关又与边数有关。对图可以进行深度优先遍历和广度优先遍历。图有许多应用采用prim算法、Kruskal算法、Floyd算法、Dijkstra算法、拓扑排序算法和求关键路径算法可以解决实际应用问题。

  施工合同亦称“工程合同”或“包工合同”。指发包方 (建设单位) 和承包方 (施工单位) 为完成商定的建筑安装工程施工任务,明确相互之间权利、义务关系的书面协议。对于我们日常接触比较多,且需求量比较大的施工合同,这些模板也许能够帮到你。

http://vuagiamgia.com/bianjihe/331.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有