《有向无环图及应用》PPT课件

《有向无环图及应用》PPT课件

ID:45470120

大小:403.34 KB

页数:20页

时间:2019-11-13

《有向无环图及应用》PPT课件_第1页
《有向无环图及应用》PPT课件_第2页
《有向无环图及应用》PPT课件_第3页
《有向无环图及应用》PPT课件_第4页
《有向无环图及应用》PPT课件_第5页
资源描述:

《《有向无环图及应用》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、7.5有向无环图及应用7.5.1拓扑排序——用顶点边表示活动的网络,简称AOV网络(ActivityOnVertices)顶点:一个工程中的活动(Activity)边:活动的顶点间的优先关系(Relation)要解决的问题是:将各个顶点(代表各个活动)排列成一个线性有序的序列,使得AOV网络中所有应存在的前驱和后继关系都能得到满足。课程代号课程名先修课程C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1

2、C9计算机原理C8可以用有向图表示一个工程。在这种有向图中,用顶点表示活动。有向边表示:Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。在AOV网络中,如果活动Vi必须在活动Vj之前进行,则存在有向边,AOV网络中不能出现有向回路,即有向环。在AOV网络中如果出现了有向环,则意味着某项活动应以自己作为先决条件。因此,对给定的AOV网络,必须先判断它是否存在有向环。一、什么是拓扑排序将各个顶点(代表各个活动)排列成一个线性有

3、序的序列,使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6二、进行拓扑排序的方法首先建立(n个顶点的)AOV网。(1)

4、在AOV网络中选一个没有直接前驱的顶点(入度为0的顶点),并输出之;(2)从图中删去该顶点,同时删去所有它发出的边;重复(1)和(2),直到全部顶点均已输出,拓扑有序序列形成,拓扑排序完成;若图中还有未输出的顶点,但已跳出处理循环。这说明图中存在环。v1v5v4v3v6三、拓扑排序的过程有向无环图v2v1v5v4v3v6v2(1)输出顶点v6(2)输出顶点v1(3)输出顶点v3(4)输出顶点v4(5)输出顶点v2(6)输出顶点v5v1v5v4v3v6三、拓扑排序的过程有向无环图v2v1v5v4v3v6v2(

5、1)输出顶点v6(2)输出顶点v1(3)输出顶点v3(4)输出顶点v4(5)输出顶点v2(6)输出顶点v5四、存储结构(邻接表)v1v2v3v4v5v612345602123043552054idvexfirstdataarcv1v5v4v3v6v22adjvexnextarctypedefstructarcnode{intadjvex;arcnode*nextarc;}*pointer;//表结点structnode{charvexdata;intid;//顶点的入度pointerfirstar

6、c;}dig[100];//一组头结点在邻接表的头结点中增设了一个数据项id,记录该顶点的入度。入度为零的顶点即无前驱的顶点。在拓扑排序算法中,使用一个存放入度为零的顶点的链式栈,供选择和输出无前驱的顶点。只要出现入度为零的顶点,就将它加入栈中。五、拓扑排序算法思想:(1)建立入度为零的顶点栈;(2)当入度为零的顶点栈不空时,重复执行:(2)-1从顶点栈中退出一个顶点,并输出之;(2)-2从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;(2)-3如果边的终顶点入度减至0,则该顶点进入度为零的顶点

7、栈;(3)如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。将顶点i进栈时,执行以下指针的修改:dig[i].id=top;top=i;//top指向新栈顶i,原栈顶元素放在id[i]中退栈操作可以写成:j=top;top=dig[top].id;//位于栈顶的顶点的位置记于j,top退到次栈顶六、拓扑排序的算法voidtoposort(){inistack(s);//置空栈for(i=1;i<=n;++i)if(dig[i].id==0)push(s.i);//入度为零的顶点栈count=

8、0;//count为计数器,计输出顶点数while(!stackempty(s)){j=pop(s);printf(dig[j].vexdata);count++;q=dig[j].firstarc;//q指示以vj为尾的第一条弧结点while(q){k=q->adjvex;//顶点vk为vj的直接后继dig[k].id--;if(dig[k].id==0)push(s,k);//新的入度为零的顶点入栈q=q->

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。