《数据结构有向无环图及其应用学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构有向无环图及其应用学习教案.pptx（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1数据结构数据结构(sh j ji u)有向无环图及其应有向无环图及其应用用第一页，共36页。一、定义一、定义(dngy)一个无环的有向图称为有向无环图，简写(jinxi)为DAG（directed acycline graph）。与有向二叉树相比，有向无环图是更一般的特殊有向图。实例(shl)：有向树有向无环图有向图 教材179页给出了有向无环图的一个简单应用：用有向无环图描述算术表达式。第1页/共36页第二页，共36页。二、拓扑二、拓扑(tu p)排序排序1.引例(yn l)：现有计算机课程 12门，如下表所示：课程编号课程名称先修课程c1程序设计基础无c2离散数学c1c3数据结构c
2、1,c2c4汇编语言c1c5语言的设计和分析c3,c4c6计算机组成原理c11c7编译原理c5,c3c8操作系统c3,c6c9高等数学无c10线性代数c9c11普通物理c9c12数值分析c9,c10,c1c1c9c4c2c12c10c11c3c5c6c7c8第2页/共36页第三页，共36页。二、拓扑二、拓扑(tu p)排序排序c1c9c4c2c12c10c11c3c5c6c7c82.拓扑(tu p)排序：偏序是指集合中仅有部分元素(yun s)可比较大小(或先后)；全序是指集合中所有元素(yun s)均可比较大小（或先后）。第3页/共36页第四页，共36页。二、拓扑二、拓扑(tu p)排序排序
3、c1c9c4c2c12c10c11c3c5c6c7c82.拓扑(tu p)排序：拓扑(tu p)排序是指将一个偏序关系转化为全序关系的过程的特殊操作。第4页/共36页第五页，共36页。二、拓扑二、拓扑(tu p)排序排序c1c9c4c2c12c10c11c3c5c6c7c83.方法(fngf)：在有向图中选择一个没有前驱（即入度为0）的顶点(dngdin)并输出之。在有向图中删除刚刚输出的顶点及所有以该顶点为尾的弧。图中若不再有入度为 0的顶点，则结束；否则转。第5页/共36页第六页，共36页。二、拓扑二、拓扑(tu p)排序排序c1c9c4c2c12c10c11c3c5c6c7c83.方法(
4、fngf)：c1拓扑(tu p)序列：c2 c3c4c5 c7c9c10c11c6 c12c8第6页/共36页第七页，共36页。二、拓扑二、拓扑(tu p)排序排序3.方法(fngf)：c1拓扑(tu p)序列：c2c3c4c5c7c9c10c11c6 c12c8注意1：从某种意义下来说，拓扑排序的结果是不唯一的。注意2：这种以顶点表示活动的有向无环图称为活动在顶点的网，简称AOV(Activity On Vertex Network)网。第7页/共36页第八页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明(shumng)：为了使说明(shumng)过程简单起见，我们以下图为例：
5、v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3 v44G.vertices4v5G.vertices5v643datafirstarcadjvexnextarc另外增设(zn sh)一个存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 5第8页/共36页第九页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了(wi le)使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0 v1321G
6、.vertices1 v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个(y)存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 5求求indegree一维数组初值的程序：一维数组初值的程序：FindInDegree(ALGraph G,indegree0.G.vexnum-1 for(i=0;iadjvex;+indegreek;p=p-nextarc;/FindInDegree第9页/共36页第十页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为
7、了(wi le)使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0 v1321G.vertices1v2G.vertices2v341G.vertices3 v44G.vertices4v5G.vertices5v643另外(ln wi)增设一个存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 5拓扑排序算法思想：拓扑排序算法思想：设一个栈设一个栈S，入度为，入度为0的顶点的序号的顶点的序号进栈。如进栈。如0，5 进栈。进栈。count=0(打印顶点个打印顶点个数计数器数计数器)。当栈当栈S不空时，
8、出栈一个元素并打不空时，出栈一个元素并打印相应顶点；印相应顶点；count加加1。该顶点的所有邻接点的入度减该顶点的所有邻接点的入度减1，减，减1后入度为后入度为0的顶点的序号进栈。的顶点的序号进栈。重复第二步，直至栈空时转重复第二步，直至栈空时转。若若count=G.vexnum,则拓扑排序成则拓扑排序成功；否则图中必有环路，拓扑排序失败。功；否则图中必有环路，拓扑排序失败。第10页/共36页第十一页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明(shumng)：为了使说明(shumng)过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v
9、1321G.vertices1 v2G.vertices2v341G.vertices3v44G.vertices4 v5G.vertices5v643另外增设(zn sh)一个存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 550s第11页/共36页第十二页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明(shumng)：为了使说明(shumng)过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1 v2G.vertices2 v341G.vertices3v
10、44G.vertices4v5G.vertices5v643另外(ln wi)增设一个存放各顶点的入度值的一维数组indegree:indegree0.5021230 0 1 2 3 4 50s5打印G.vertices5.data4号和3号顶点的入度分别减 1第12页/共36页第十三页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了使说明过程(guchng)简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0 v1321G.vertices1v2G.vertices2v341G.vertices3 v44G.vertices4v5G.vert
11、ices5v643另外增设一个存放(cnfng)各顶点的入度值的一维数组indegree:indegree0.5021120 0 1 2 3 4 50s第13页/共36页第十四页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了使说明过程简单起见，我们(w men)以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1 v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放(cnfng)各顶点的入度值的一维数组indegree:indegree0.50
12、21120 0 1 2 3 4 5 s0打印G.vertices0.data3号、2号、1号顶点的入度分别减 1第14页/共36页第十五页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了(wi le)使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3 v44G.vertices4v5G.vertices5v643另外增设一个(y)存放各顶点的入度值的一维数组indegree:indegree0.5010020 0 1 2 3 4 523s第15页
13、/共36页第十六页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了(wi le)使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0 v1321G.vertices1v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设一个存放(cnfng)各顶点的入度值的一维数组indegree:indegree0.5010020 0 1 2 3 4 523s第16页/共36页第十七页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法(sun f)说明：为了使说明过程简单
14、起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2 v341G.vertices3v44G.vertices4v5G.vertices5v643另外(ln wi)增设一个存放各顶点的入度值的一维数组indegree:indegree0.5010020 0 1 2 3 4 5 3s2打印G.vertices2.data4号、1号顶点的入度分别减 1第17页/共36页第十八页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了使说明过程简单(jindn)起见，我们以下图为例：v10v21v32v4
15、3v65v54G.vertices0v1321G.vertices1v2G.vertices2 v341G.vertices3v44G.vertices4v5G.vertices5 v643另外增设一个(y)存放各顶点的入度值的一维数组indegree:indegree0.5000010 0 1 2 3 4 513s第18页/共36页第十九页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了使说明过程简单(jindn)起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertic
16、es3v44G.vertices4 v5G.vertices5v643另外(ln wi)增设一个存放各顶点的入度值的一维数组indegree:indegree0.5000010 0 1 2 3 4 5 3s1打印G.vertices1.data第19页/共36页第二十页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了(wi le)使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1 v2G.vertices2v341G.vertices3v44G.vertices4v5G.vertices5v643另外
17、增设(zn sh)一个存放各顶点的入度值的一维数组indegree:indegree0.5000010 0 1 2 3 4 5 3s第20页/共36页第二十一页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了(wi le)使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1v2G.vertices2v341G.vertices3 v44G.vertices4v5G.vertices5v643另外增设一个存放(cnfng)各顶点的入度值的一维数组indegree:indegree0.5000010 0 1
18、 2 3 4 5 s3打印G.vertices3.data4号顶点的入度减 1第21页/共36页第二十二页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了使说明过程(guchng)简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0 v1321G.vertices1 v2G.vertices2 v341G.vertices3v44G.vertices4v5G.vertices5v643另外增设(zn sh)一个存放各顶点的入度值的一维数组indegree:indegree0.5000000 0 1 2 3 4 5 4s第22页/共36页第二十三
19、页，共36页。二、拓扑二、拓扑(tu p)排序排序4.算法说明：为了(wi le)使说明过程简单起见，我们以下图为例：v10v21v32v43v65v54G.vertices0v1321G.vertices1 v2G.vertices2v341G.vertices3v44G.vertices4 v5G.vertices5v643另外增设(zn sh)一个存放各顶点的入度值的一维数组indegree:indegree0.5000000 0 1 2 3 4 5 s4打印G.vertices4.data最后输出的拓扑序列为：v6v1v3v2v4v5第23页/共36页第二十四页，共36页。二、拓扑二、
20、拓扑(tu p)排序排序4.程序(chngx)：Status TopologicalSort(ALGraph)FindIndegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;+i)if (!indegreei)Push(S,i);/入度为0的顶点(dngdin)的序号进栈 count=0;while(!StackEmpty(S)Pop(S,i);couti nextarc)第24页/共36页第二十五页，共36页。Status TopologicalSort(ALGraph)FindIndegree(G,indegree);InitStack(S)
21、;for(i=0;iG.vexnum;+i)if (!indegreei)Push(S,i);/入度为0的顶点(dngdin)的序号进栈 count=0;while(!StackEmpty(S)Pop(S,i);couti nextarc)k=p-adjvex;-indegreek;if(!(indegreek)Push(S,k);第25页/共36页第二十六页，共36页。Status TopologicalSort(ALGraph)FindIndegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;+i)if (!indegreei)Push(S,i
22、);/入度为0的顶点(dngdin)的序号进栈 count=0;while(!StackEmpty(S)Pop(S,i);couti nextarc)k=p-adjvex;-indegreek;if(!(indegreek)Push(S,k);/while if (count=G.vexnum)return OK;else return ERROR;/TopologicalSort第26页/共36页第二十七页，共36页。Status TopologicalSort(ALGraph)FindIndegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;+
23、i)if (!indegreei)Push(S,i);/入度为0的顶点(dngdin)的序号进栈 count=0;while(!StackEmpty(S)Pop(S,i);couti nextarc)k=p-adjvex;-indegreek;if(!(indegreek)Push(S,k);/while if (count=G.vexnum)return OK;else return ERROR;/TopologicalSort第27页/共36页第二十八页，共36页。三、关键三、关键(gunjin)路径路径1.实例(shl)：v10v21v32v43v54v65v76v87v98a1=6a4
24、=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4顶点vi表示(biosh)事件；弧既描述事件之间的依赖关系，又表示某种活动ai的持续时间；从“起点”(v1)开始到“终点”(v9)的最长路径称为关键路径；每个活动ai都有一个最早开始时间e(i)和一个最迟开始时间l(i)；例如：对于a5，有：e(5)=4；l(5)=6关键路径上的活动ai称为关键活动，一定满足：e(i)=l(i)；每个事件v也有一个最早开始时间ve(k)和一个最迟开始时间vl(k);例如：对于事件v3，有：ve(2)=4；vl(2)=6第28页/共36页第二十九页，共36页。三、关键三、关键(gun
25、jin)路径路径1.实例(shl)：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4活动ai和它所依附的顶点(dngdin)的关系：设有：jkai=dut()则有：1.e(i)=ve(j)2.l(i)=vl(k)-dut()即：活动 ai的最早开始时间等于事件 j的最早开始时间；活动ai的最迟开始时间等于事件 k的最迟开始时间减活动 ai的持续时间。第29页/共36页第三十页，共36页。三、关键三、关键(gunjin)路径路径1.实例(shl)：v10v21v32v43v54v65v76v87v9
26、8a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4求关键(gunjin)路径的算法思想：1）设ve(0)=0；按拓扑顺序利用如下公式依次求其余各顶点j(j=1,2,.n-1)的ve(j):2）设vl(n-1)=ve(n-1)；按拓扑逆顺序利用如下公式依次求其余各顶点j(j=n-2,.,2,1,0)的vl(j):ijdut()vl(i)=Minvl(j)-dut()jve(j)=Maxve(i)+dut()i第30页/共36页第三十一页，共36页。三、关键三、关键(gunjin)路径路径1.实例(shl)：v10v21v32v43v54v65v76v8
27、7v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=4例如：求上例各顶点(dngdin)的最早开始时间和最迟开始时间：i012345678备注备注顶点顶点vv1v2v3v4v5v6v7v8v9最早发生时间最早发生时间ve(i)最迟发生时间最迟发生时间vl(i)0645771614181814161078660第31页/共36页第三十二页，共36页。三、关键三、关键(gunjin)路径路径1.实例(shl)：v10v21v32v43v54v65v76v87v98a1=6a4=1a2=4a3=5a5=1a6=2a7=9a11=4a10=2a8=7a9=
28、4例如：求上例各顶点(dngdin)的最早开始时间和最迟开始时间：i012345678备注备注顶点顶点vv1v2v3v4v5v6v7v8v9最早发生时间最早发生时间ve(i)最迟发生时间最迟发生时间vl(i)0645771614181814161078660其中：v1,v2,v5,v7,v8,v9为关键活动。第32页/共36页第三十三页，共36页。作业(zuy)：1.试分析下面有向图的矩阵存储结构(jigu)和邻接表存储结构(jigu)：abcd12342.试编写(binxi)函数，求在无向图的邻接表类的对象G中各顶点 vi的度。3.试编写函数，在无向图的邻接表类的对象G中判断两个顶点 vi和vj之间是否存在一条从 vi到vj的路径（提示：利用深度或广度优先遍历函数）。第33页/共36页第三十四页，共36页。作业(zuy)：4.自己任意设计画出一个 AOV网（即画出一个有向无环图，要求(yoqi)有8个以上的顶点），然后试着写出它的一个拓扑序列。5.自己任意设计画出一个 AOE网（即画出一个有向无环图，且边上有权值，要求(yoqi)有10个以上的顶点），然后试着写出各顶点的最早开始时间和最迟开始时间，并写出该图的若干条关键路径。第34页/共36页第三十五页，共36页。End第35页/共36页第三十六页，共36页。