有向无环图及其应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数据结构,7.5 有向无环图及其应用,有向无环图（directed acyline graph，DAG）：,不存在由有向边构成的有向环。,（1）AOV网,如果在图中，用顶点表示活动，弧表示活动间的先后关系，则称这样的DAG图为,AOV网,（Acivity On Vertex network）,10/4/2026,1,（2）AOE网,如果在带权的有向图中，用顶点表示事件，用有向边表示活动，边上的权表示活动持续的时间，这种带权的有向图称为,AOE网,（Activity On Edge Network）,10/4/2026,2,7.5.1 拓扑排序,AOV网,如果在图中，用顶点表示活动，弧表示活动间的先后关系，则称这样的DAG图为,AOV网,（Acivity On Vertex network）。,10/4/2026,3,10/4/2026,4,在AOV网中几个概念：,（1）直接前趋与直接后继：,若存在弧，则称顶点i是顶点j的,直接前趋,，称顶点j是顶点i的,直接后继,；,（2）前趋与后继：,若存在从顶点i到顶点j的一条有向路径，则称i是j的,前趋,，称j是i的,后继,。,（3）拓扑排序：,是指构造AOV网中顶点的一个线性序列，使得AOV网中所包含的所有趋继关系都得以满足，即前趋顶点在线性序列中总是排在后继顶点之前。,2.拓扑排序,10/4/2026,5,关键活动：关键路径上的活动都是关键活动。,Vl(i)=minVl(j)-weight()vi,vjE，1in-1（weight()表示上的权）,indegree+;,int indegree;,不存在由有向边构成的有向环。,逆拓扑排序，其方法和步骤与拓扑排序正好形成对偶关系：,vexsp-adjvex.,（3）重复（1）、（2），直至全部顶点输出完毕（称为拓扑排序成功），或者再也找不到没有前趋的顶点（对应于拓扑排序失败，即图中存在有向环）为止。,2）事件vi的最迟发生时间Vl(i),(1)对AOE网进行拓扑排序，按拓扑排序次序依次求出各顶点事件的最早发生时间Ve（若网中有回路，则终止）；,void toposort(ALgraph G)/*对AOV网G进行拓扑排序*/,int top=0,i,k,count=0;,for(i=1;i=G.,（3）重复（1）、（2），直至全部顶点输出完毕（逆拓扑排序成功），或者再也找不到没有后继的顶点（逆拓扑排序失败）为止。,Vl(i)是指在不推迟整个工期的前提下，事件vi允许的最晚发生时间。,拓扑排序的方法和步骤：,（1）在AOV网中选取一个没有前趋（即入度为0）的顶点并输出之；,（2）从AOV网中删除该顶点以及从该顶点发出的所有有向边（可以用有向边射入的顶点入度减1实现）；,（3）重复（1）、（2），直至全部顶点输出完毕（称为拓扑排序成功），或者再也找不到没有前趋的顶点（对应于拓扑排序失败，即图中存在有向环）为止。,10/4/2026,6,逆拓扑排序，其方法和步骤与拓扑排序正好形成对偶关系：,（1）在AOV网中选取一个没有后继（即出度为0）的顶点并输出之。,（2）从AOV网中删除该顶点以及射向该顶点的所有有向边（可以用有向边发出的顶点的出度减1实现）。,（3）重复（1）、（2），直至全部顶点输出完毕（逆拓扑排序成功），或者再也找不到没有后继的顶点（逆拓扑排序失败）为止。,10/4/2026,7,#define MAXVER 21,typedef struct listnode,int adjvex;,struct listnode*next;,listnode;,typedef struct,int indegree;,listnode*first;,headnode;,typedef struct,10/4/2026,8,关键活动:若Ae(k)=A l(k)，则活动ak称为关键活动。,如果在带权的有向图中，用顶点表示事件，用有向边表示活动，边上的权表示活动持续的时间，这种带权的有向图称为AOE网（Activity On Edge Network）。,2）事件vi的最迟发生时间Vl(i),indegree+;,(3)根据Ve和Vl的值，求出各个活动ak的最早开始时间Ae(k)和最迟开始时间A l(k)，,listnode*first;,不存在由有向边构成的有向环。,不存在由有向边构成的有向环。,在AOV网中几个概念：,while(p!=NULL),while(p!=NULL),for(i=1;i=G.,关键活动：关键路径上的活动都是关键活动。,（2）从AOV网中删除该顶点以及从该顶点发出的所有有向边（可以用有向边射入的顶点入度减1实现）；,逆拓扑排序，其方法和步骤与拓扑排序正好形成对偶关系：,p=G.,int top=0,i,k,count=0;,（2）哪些活动是影响工程进度的关键活动？,headnode vexsMAXVER;,int vexnum,arcnum;,ALgraph;,void toposort(ALgraph G),/*对AOV网G进行拓扑排序*/,int stackMAXVER,int top=0,i,k,count=0;,listnode*p;,10/4/2026,9,for(i=1;i=G.vexnum;i+),/*假定G中各顶点入度未知，先求各顶点入度*/,G.vexsi.indegree=0;,for(i=1;iadjvex.indegree+;,p=p-next;,/*while*/,/*for*/,10/4/2026,10,1.AOE网,如果在带权的有向图中，用顶点表示事件，用有向边表示活动，边上的权表示活动持续的时间，这种带权的有向图称为,AOE网,（Activity On Edge Network）。,7.5.2 关键路径,10/4/2026,11,10/4/2026,12,我们感兴趣的问题是：,（1）完成整个工程至少需要多少时间？,（2）哪些活动是影响工程进度的关键活动？,关键路径（Critical Path）:,在AOE网中，称从源点到汇点路径长度最长的路径为,关键路径,（Critical Path）。,(1)关键路径可能不止一条，,(2)所有关键路径长度必然相等。,2.关键路径,10/4/2026,13,关键活动：,关键路径上的活动都是,关键活动,。,（1）关键路径上的各项活动能按期或提前完成，则整个工程则能按期或提前完成。,（2）如果关键活动拖延了时间，整个工程的工期必定拖延。,10/4/2026,14,1）事件v,j,的最早发生时间Ve(j),是从源点到顶点v,j,的最长路径长度，这个时间也是所有从v,j,出发的有向边表示的活动的最早发生时间。,根据AOE网性质，只有进入v,j,的所有活动都结束时，v,j,事件才能发生；而活动的最早结束时间为Ve(i)+weight()。,事件v,j,的最早发生时间为：,10/4/2026,15,Ve(j)=0 j=1（源点编号指定为1）,Ve(j)=maxVe(i)+weight()v,i,v,j,E，2,j,n（weight()表示上的权）,10/4/2026,16,2）事件vi的最迟发生时间V,l,(i),V,l,(i)是指在不推迟整个工期的前提下，事件vi允许的最晚发生时间。,vi的最晚发生时间不得迟于其后继事件vj的最晚发生时间减去活动的持续时间。,事件的最迟发生时间为：,10/4/2026,17,Vl(i)=Ve(i)i=n（汇点编号指定为n）,Vl(i)=minVl(j)-weight()v,i,v,j,E，1,i,n-1（weight()表示上的权）,10/4/2026,18,3）活动ak=的最早开始时间Ae(k),只有事件vi发生了，活动ak才能开始。因此活动ak的最早开始时间等于事件vi的最早发生时间：Ae(k)=Ve(i),4）活动ak=的最迟开始时间A,l,(k),活动ak的最迟开始时间A,l,(k)等于V,l,(j)的最晚发生时间减去ak的持续时间：,A,l,(k)=V,l,(j)-weight(),10/4/2026,19,关键活动:,若Ae(k)=A,l,(k),，则活动ak称为,关键活动,。,时间余量:,A l,(k)Ae(k),表示完成活动ak的时间余量，它表示不延误工期的前提下活动ak可以延迟的时间。,10/4/2026,20,求关键路径的方法与步骤如下：,(1)对AOE网进行拓扑排序，按拓扑排序次序依次求出各顶点事件的最早发生时间Ve（若网中有回路，则终止）；,(2)按拓扑序列的逆序依次求出各顶点事件的最迟发生时间V,l,；,(3)根据Ve和Vl,的值，求出各个活动,ak的最早开始时间Ae(k)和最迟开始时间A l,(k),，,若Ae(k)=A l,(k),，则ak是关键活动。,10/4/2026,21,