chap10(03)

null第十章（03）图第十章（03）图杨震 计算机科学与技术学院10.5 有向无环图的应用BUPT SCSTBUPT10.5 有向无环图的应用1、何为有向无环图（DAG 图） [实例]BEFGLFGBEFGLFGBEFGLFG有向树DAG图有向图（含环）[用途]：描述工程项目或系统进行的工具 AOV 网络：定义顶点为活动，有向边的指向表示活动执行的次序。 AOE网络：定义顶点为事件，单位是时刻。有向边定义为活动，它的权值定义为活动进行所需要的时间。ABAB10nullBUPT SCSTBUPT2 拓扑排序 [问题目标] 当一个任务可以划分问若干个子任务/子活动/子事件，其中的任何子任务可能又以另外的一些子任务作为先决条件时，如何排定子任务的执行顺序，达到整体任务的完成。 [示例] 1327564课程之间的依赖关系其中，1代表 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 ， 2代表程序设计，3代表离散数 学，4代表汇编程序设计，5代表数据结构，6代表结构程序设计, 7代表编译原理。 1324657AOV网(顶点活动网络)—顶点表示活动，弧表示活动间的优先关系nullBUPT SCSTBUPT2.1 无前趋的顶点优先算法[算法原理] 在一个拓扑序列中，每个顶点必定出现在它的所有前趋顶点之后。 [算法思想] 1. 选择一个入度为0的顶点(无前趋的顶点)，输出它 2. 删去该顶点及其关联的所有出边 重复上述两步，直至图中不再有入度为0的顶点为止。 若所有顶点均被输出，则排序成功， 否则图中存在有向环。 若该有向图不是无环图，则不存在拓扑排序。可以来判断一个有向图是否存在回路。nullBUPT SCSTBUPT[例] v5v3v4v1v2 v5v1v2v3v4v5v1v2v3v4v5v1 v2v3v4v1 v2 v5 v3v4v1 v2 v5 v3 v4有向无环图的拓扑序列不唯一nullBUPT SCSTBUPT[算法（使用邻接矩阵）]13275640 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 01 2 3 4 5 6 7 1 2 3 4 5 6 7算法的执行步骤： 1、找到全为零的第 j 列，输出 j 2、将第 j 行的全部元素置为零 3、找到全为零的第 k 列，输出 k 4、将第 k 行的全部元素置为零 ………………… 反复执行 3、4；直至所有元素输出完毕。 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0。。。。。。nullBUPT SCSTBUPT算法（使用邻接表）1327564算法的执行步骤： 1、用一个数组记录每个结点的入度。将入度为零的结点进栈。 2、将栈中入度为零的结点V输出。 3、根据邻接表找到结点V的所有的邻接结点，并将这些邻接结点的入度减一。如果某一结点的入度变为零，则进栈。 4、反复执行 2、3；直至栈空为止。 ………………… 次序执行结束，如果输出结点数等于图的结点总数，则有向图有环，否则有向图有环。12231234567null45573456nullnullnull6777nullnullnullnull01123456711213indegree1栈nullBUPT SCSTBUPT//邻接表存储 Status Topologicalsort（ ALGraph G） { findinDegree（G，indegree）; Initstack（S）； for （i = 1; i <= G.vexnum; ++i） if （! Indegree [ i ]）Push（S，i）; count = 0; while （！StackEmpty（S）） { Pop（S，i）; Printf（i，vertices[ i ].data）; ++count; for （p=G.vertices[i]. firstarc; p; p=p->nextarc）; { k = p->adjnexr; if （!（- - indegree [ k ]）） Push（S, k）; } } if （count < G.vexnum）return ERROR; else return OK; } // end O(n+e)O(n+e)nullBUPT SCSTBUPT2.2 无后继的顶点优先[算法原理] 在一个拓扑序列中，每个顶点必定出现在它的所有后继顶点之前。 [ 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 一 算法思想] （按逆拓扑次序生成顶点序列） 1. 选择一个出度为0的顶点(无后继的顶点)，输出它 2. 删去该顶点及其关联的所有入边 重复上述两步，直至图中不再有出度为0的顶点为止。 若所有顶点均被输出，则排序成功， 否则图中存在有向环。nullBUPT SCSTBUPT[例] v1v3v2v5v4 v3v1v2v3v4v5v5v2v3v4v1v5 v4v2v1v5 v4 v3 v2v1v5 v4 v3 v2 v1nullBUPT SCSTBUPT[方法二 算法思想] （利用深度优先遍历） 1)访问顶点v，并记录v已被访问 2)依次从v的未访问的邻接点出发，深度优先 拓扑排序图G。 3)输出顶点v（此时v相当于无后继的顶点） [方法二适用范围] 有向无环图 （此算法不能 检测 工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训 出有向环，得到虚假拓扑序列）v1 1) 2) 3)v2 1) 2) 3)v2v1v1v2v3v4v4 1) 2) 3)v4v3 1) 2) 3) v3v4 v2 v3 v1nullBUPT SCSTBUPT3 关键路径 [问题目标] 当一个任务/工程可以划分问若干个子任务/子活动/子工程，其中的任何子任务可能又以另外的一些子任务作为先决条件 整个工程至少需要多少时间 哪些活动是影响进度的关键 AOE网(边活动网络)—顶点表示事件，弧表示活动 [AOE网的性质] 进入Vi的活动都结束， Vi所代表的事件才能发生 顶点Vi所代表的事件发生，从Vi出发的活动才能开始 nullBUPT SCSTBUPT[相关概念和术语] 源点 入度为0的顶点，即工程的开始点 汇点 出度为0的顶点，即工程的完成点 关键路径 从源点到汇点的最长路径 关键路径长度=最短工期 关键活动 关键路径上的活动 关键活动的加快可以缩短工期 [确定关键路径时涉及的几个变量] e(i) :活动ai的最早开始时间 l(i) :活动ai的最迟开始时间 ve(j) :事件vj的最早发生时刻 vl(j) :事件vj的最迟发生时刻aidut()jke(i)=ve(j) l(i)=vl(k)-dut()e(i)=l(i)nullBUPT SCSTBUPT[关键路径的确定] 1) 求事件vj的最早发生时刻ve(j) ve(1)=0 ve(j)=max{ve(i)+dut()} (ij的前驱) [算法思想]：在求拓扑排序的过程中进行。 辅助数据结构: ve(1..n) {n为顶点个数} 1)初值ve[j]=0 1jn 2) 每输出一个无前驱的顶点j后，修正j的所有后继结点k的ve[k]: ve[k]=max{ve[k], ve[j]+dut()}...ji1i2jk1k2...ve[j]nullBUPT SCSTBUPTV1V3V2V5V6V41 3 51 102 2V1V3V2V5V6V41 3 51 12 21222211 3、5、3、 35、567、8正向拓扑排序：000000V1V2V3V4V5V6实例Ve(1)=0 Ve(2)=1 Ve(3)=3 Ve(4)=5 Ve(5)=6 Ve(6)=8nullBUPT SCSTBUPTStatus Topologicalsort（ ALGraph G, Stack &T） { FindinDegree（G，indegree）; // 对各顶点求入度，建立入度为零的栈 S， Initstack（T）；count = 0; ve [ 1 .. G.vexnum] = 0; while （！StackEmpty（S）） { Pop（S，j）;Push（T，j）; ++count; for （p=G.vertices[j]. firstarc; p; p=p->nextarc）; { k = p->adjnexr; if （!（- - indegree [ k ]）） Push（S, k）; if （ve[ j ]+ *（ p->info）> ve[ k ] ） ve[ k ] = ve[ j ] + *（ p->info）; } } } if （count < G.vexnum）return ERROR; else return OK; } // 栈 T 为求事件的最迟发生时间的时候用。nullBUPT SCSTBUPT2) 求事件vj的最迟发生时刻vl(j) vl(n)=ve(n) {保证ve(n)的前提下} vl(j)=min{vl(k)- dut()} (kj的后继) [算法思想]：按逆拓扑序列逐一计算。 辅助数据结构: vl(1..n) {n为顶点个数} 栈s—记录拓扑有序序列 原理：拓扑序列 。。。j 。。。 含j的所有后继 k1jk2...nullBUPT SCSTBUPTV1V3V2V6V41 3 51 12 2216、568逆向拓扑排序：8V1V3V2V5V6V41 3 51 12 22216、4、40、0、03实例V5Vl(1)=0 Vl(2)=3 Vl(3)=4 Vl(4)=5 Vl(5)=6 Vl(6)=8V1V2V3V4V5V6利用逆向拓扑排序算法求事件结点的最迟发生时间的执行步骤： 1、设每个结点的最迟发生时间为汇点的最早发生时间。 2、将栈中的结点V取出。 3、根据逆邻接表找到结点V的所有的起始结点，将结点V的最迟发生时间 - 活动的权值得到的差同起始结点的原最迟发生时间进行比较；如果该值小，则用该值取代原最迟发生时间。 4、反复执行 2、3；直至栈空为止。 nullBUPT SCSTBUPT3) 求活动ai的最早开始时间e(i)和最迟开始时间l(i) 确定关键活动e(i)=l(i) e(i)=ve(j) l(i)=vl(k)-dut() jkainullBUPT SCSTBUPT j 1 2 3 4 5 6 7 8 9 ve(j) 0 6 4 5 7 7 16 14 18 vl(j) 0 6 6 8 7 10 16 14 18 i 1 2 3 4 5 6 7 8 9 10 11 e(i) 0 0 0 6 4 5 7 7 7 16 14 l(i) 0 2 3 6 6 8 7 7 10 16 14 两条关键路径 最短工期：18a1a4a7a8a10a11nullBUPT SCSTBUPT[求关键路径算法步骤] 主数据结构：图—邻接矩阵或邻接表 辅助：ve(1..n), vl(1..n), e(1..m), l(1..m) {n为图的顶点数目；m为图的弧数目} s—存储拓扑排序的顶点序列 (1)输入所有弧的信息，建立AOE网的存储结构 (2)求拓扑排序的顶点序列 每求得一个顶点j，则使j入栈s，并调整j的所有后继的ve值 (3)按栈s的从栈顶到栈底的顺序求顶点的vl值 (4)求每个活动i的e(i)和l(i)值，确定关键路径10.6 最短路径BUPT SCSTBUPT10.6 最短路径1. 概述 [问题对象] 有向网络（可扩展到无向网络） [两个典型问题] 单源最短路径（可扩展到多源问题） 迪杰斯特拉(Dijkstra)算法 每一对顶点间的最短路径 弗洛伊德(Floyd)算法 nullBUPT SCSTBUPT2. 从某个源点到其余各顶点的最短路径 [Dijkstra算法原理] 按路径长度递增次序产生各顶点的最短路径。 [例] 邻接矩阵 12345101003050102060 0 10  30 100  0 50     0  10   20 0 60     0nullBUPT SCSTBUPT 设以顶点1作为源点 34103010012501001030100103010012503410306050103012503410305020609010103012503430502060101030125034305020601010nullBUPT SCSTBUPT[数据结构] 设图中的顶点个数为n 主：邻接矩阵G[n][n] (或者邻接表) 辅： 一维数组S[1..n]：记录相应顶点是否已被确定最短距离 一维数组D[1..n]：记录源点到相应顶点路径长度 一维数组P[1..n]：记录相应顶点的双亲顶点 例中各辅助数据结构初值如下： S： 1 FALSE D： 1 0 P： 1 -1 … 2 10 2 1 3  3 -1 4 30 4 1 n FALSE n 100 n 1 nullBUPT SCSTBUPT[算法步骤]（采用邻接矩阵存储） 设确定v为源点 1)初始化辅助数据结构：(i=1..n) O(n) 1.1) S[i]=FALSE； 1.2) D[i]=G[v][i]； 1.3) 若D[i]不为，则P[i]=v，否则P[i]=-1 2)确定源点自身的最短距离: S[v]=TRUE, D[v]=0 O(1) 3)循环确定其余n-1个顶点到v的最短距离： O(n2) 3.1)找出D中未被确定最短距离的顶点中路径最短的顶点， 设该顶点序号为k，且D[k]=min； 3.2)若min为，退出本算法； 3.3)赋值S[k]=TRUE； nullBUPT SCSTBUPT3.4)调整尚未被确定最短距离的顶点的估算距离：(j=1..n) 若S[j]=FALSE 且 D[j]>D[k]+G[k][j] 则D[j]=D[k]+G[k][j]，P[j]=k 4)依次打印各顶点的最短路径及其距离： O(n2) (i=1..n) 4.1)printf(i，D[i])； 4.2)确定终点i的前趋：pre=P[i] 4.3)若pre=-1，则转4)处理下一顶点 否则printf(pre)，pre=P[pre]，转4.3) O(n2)jkD[k]nullBUPT SCSTBUPTDijkstra 算法的另一种描述 设 V 是该有向图的结点的集合、集合 S 是已求得最短路径的结点的集合, 求 V1 至其余各结点的最短距离。 1、S ＝ { 1 } ；// 结点 V1 最短路径已求得 2、for ( i=2; i<=n; i++ ) 3、 D[i]=c[ 1, i ]；// V1至Vi的边长 4、for ( i=2; i<=n; i++ ) 5、{ 在 V－S 中选择一个结点W；使得 D[w] 最小。将W 加入集合 S 6、 for (每一个在 V－S 中的结点 V) 7、 { D[v]=MIN( D[v],D[w]+C[w,v]) ; 8、 P[ v ] = w; } 9、 } nullBUPT SCSTBUPT3. 每一对顶点之间的最短路径 每次选一个顶点为源点，反复利用Dijstra算法 O(n3) Floyd算法 O(n3) 但算法相对简单 [Floyd算法思想] 利用二维数组A(1..n, 1..n), A[i, j]记录当前vi到vj的最短路径长度，初值A[i, j]=cost[i, j] 集合S记录当前允许的中间顶点，初值S= 依次向S中加入v1、 v2、...、 vn，每加入一个顶点，对A[i, j]进行一次修正：设S={v1, v2,..., vk-1}，加入vk，则A(k) [i, j]=min{A(k-1) [i, j], A(k-1) [i, k]+ A(k-1) [k, j]} A(k) [i, j] 的含义： 允许的中间 顶点的序号最大为k时的 从vi到vj的最短路径长度vivjvkA[i,j]A[i,k]A[k,j]nullBUPT SCSTBUPT[例] 邻接矩阵 12345101003050102060 0 10  30 100  0 50     0  10   20 0 60     0nullBUPT SCSTBUPT A(0)=cost A(1) A(2) 0 10  30 100 0 10  30 100 0 10 60 30 100  0 50    0 50    0 50     0  10   0  10   0  10   20 0 60   20 0 60   20 0 60     0     0     0 path(0)直接路径 path(1) path(2) (1,1) (1,2) ( ) … (1,2,3) {非处以(i,j) 赋初值,处以 ( )赋值} nullBUPT SCSTBUPT A(3) A(4) A(5) 0 10 60 30 70 0 10 50 30 60 0 10 50 30 60  0 50  60  0 50  60  0 50  60   0  10   0  10   0  10   20 0 30   20 0 30   20 0 30     0     0     0 path(3) path(4) path(5) (1,2,3) (12,,3,5) (1,4,3) (1,4,3,5) (1,4,3) (1,4,3,5) (2,3,5) (2,3,5) (2,3,5) (i,j) (4,3,5) (i,j) (4,3,5) (i,j) (4,3,5) nullBUPT SCSTBUPT[数据结构] 设图中的顶点个数为n 主：邻接矩阵cost[1..n][1..n]，注：cost[i,i]=0 辅： A[1..n][1..n]：记录最短路径长度 path[1..n][1..n]：记录最短路径 [算法描述] 算法主要过程 for ( i = 1; i < =n; i++ ) for ( j = 1; j <= n; j++ ) A[ i, j ]=cost[ i, j ]; for ( k = 1; k <= n; k++ ) for ( i = 1; i < =n; i++ ) for ( j = 1; j < =n; j++ ) if ( A[ i, k ] + A[ k, j ] < A[ i, j ] ) A[ i, j ] = A[ i, k ] + A[ k, j ]; nullBUPT SCSTBUPT1.证明对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。 2.已知某图的邻接表如下图所示 （1）．写出此邻接表对应的邻接矩阵； （2）．写出由v1开始的深度优先遍历的序列； （3）．写出由v1开始的深度优先的生成树； （4）．写出由v1开始的广度优先遍历的序列； （5）．写出由v1开始的广度优先的生成树； nullBUPT SCSTBUPT3. 已知一图如下图所示： （1）．写出全部拓扑排序； （2）．以v1为源点,以v8为汇点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径； （3）．求V1结点到各点的最短距离。nullBUPT SCSTBUPT4.已知某图的邻接矩阵为A，即若从i到j有边，则A[i，j]=1，否则A[i，j]=0。试编写一算法求矩阵A的传递闭包C：使得若从i到j有一条或多条路径，则C[i，j]=1，否则C[i，j]=0。 typedef int adjmatrix [ maxvtxnum ] [ maxvtxnum ]; void change（ adjmatrix A, adjmatrix C, int n ）