拓扑排序 古城微笑少年丶 2022-03-18 12:35 301阅读 0赞 (1)有向无环图 无环的有向图,简称 DAG (Directed Acycline Graph) 图。 有向无环图在工程计划和管理方面的应用:除最简单的情况之外,几乎所有的工程都可分为若干个称作“活动”的子工程,并且这些子工程之间通常受着一定条件的约束,例如:其中某些子工程必须在另一些子工程完成之后才能开始。 对整个工程和系统,人们关心的是两方面的问题: **①工程能否顺利进行; ②完成整个工程所必须的最短时间。** 对应到有向图即为进行拓扑排序和求关键路径。 AOV网: 用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网(Activity On Vertex network)。 例如:排课表 AOV网的特点: ①若从i到j有一条有向路径,则i是j的前驱;j是i的后继。 ②若< i , j >是网中有向边,则i是j的直接前驱;j是i的直接后继。 ③AOV网中不允许有回路,因为如果有回路存在,则表明某项活动以自己为先决条件,显然这是荒谬的。 问题: 问题:如何判别 AOV 网中是否存在回路? 检测 AOV 网中是否存在环方法:对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网必定不存在环。 拓扑排序的方法: ①在有向图中选一个没有前驱的顶点且输出之。 ②从图中删除该顶点和所有以它为尾的弧。 ③重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止。 一个AOV网的拓扑序列不是唯一的! 代码实现: Status TopologicalSort(ALGraph G) //有向图G采用邻接表存储结构。 //若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR. //输出次序按照栈的后进先出原则,删除顶点,输出遍历 { SqStack S; int i, count; int *indegree1 = (int *)malloc(sizeof(int) * G.vexnum); int indegree[12] = {0}; FindInDegree(G, indegree); //求个顶点的入度下标从0开始 InitStack(&S); PrintStack(S); for(i = 0; i < G.vexnum; ++i) if(!indegree[i]) //建0入度顶点栈S push(&S,i); //入度为0者进栈 count = 0; //对输出顶点计数 while (S.base != S.top) { ArcNode* p; pop(&S,&i); VisitFunc(G,i);//第i个输出栈顶元素对应的顶点,也就是最后进来的顶点 ++count; //输出i号顶点并计数 for(p = G.vertices[i].firstarc; p; p = p->nextarc) { //通过循环遍历第i个顶点的表结点,将表结点中入度都减1 int k = p->adjvex; //对i号顶点的每个邻接点的入度减1 if(!(--indegree[k])) push(&S,k); //若入度减为0,则入栈 }//for }//while if(count < G.vexnum) { printf("\n该有向图有回路!\n"); return ERROR; //该有向图有回路 } else { printf("\n该有向图没有回路!\n"); return OK; } } 关键路径 把工程计划表示为有向图,用顶点表示事件,弧表示活动,弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。称这种有向图为边表示活动的网,简称为 AOE网 (Activity On Edge)。 例如: 设一个工程有11项活动,9个事件。 事件v\_1——表示整个工程开始(源点) 事件v\_9——表示整个工程结束(汇点) 对AOE网,我们关心两个问题: ①完成整项工程至少需要多少时间? ②哪些活动是影响工程进度的关键? 关键路径——路径长度最长的路径。 路径长度——路径上各活动持续时间之和。 v\_i——表示事件v\_i的最早发生时间。假设开始点是v\_1,从v\_1到〖v�i〗的最长路径长度。ⅇ(ⅈ)——表示活动a\_i的最早发生时间。 l(ⅈ)——表示活动a\_i最迟发生时间。在不推迟整个工程完成的前提下,活动a\_i最迟必须开始进行的时间。 l(ⅈ)-ⅇ(ⅈ)意味着完成活动a\_i的时间余量。 我们把l(ⅈ)=ⅇ(ⅈ)的活动叫做关键活动。显然,关键路径上的所有活动都是关键活动,因此提前完成非关键活动并不能加快工程进度。 例如上图中网,从从v\_1到v\_9的最长路径是(v\_1,v\_2,v\_5,v\_8,ν\_9 ),路径长度是18,即ν\_9的最迟发生时间是18。而活动a\_6的最早开始时间是5,最迟开始时间是8,这意味着:如果a\_6推迟3天或者延迟3天完成,都不会影响整个工程的完成。因此,分析关键路径的目的是辨别哪些是关键活动,以便争取提高关键活动的工效,缩短整个工期。 由上面介绍可知:辨别关键活动是要找l(ⅈ)=ⅇ(ⅈ)的活动。为了求ⅇ(ⅈ)和l(ⅈ),首先应求得事件的最早发生时间vⅇ(j)和最迟发生时间vl(j)。如果活动a\_i由弧〈j,k〉表示,其持续时间记为dut(〈j,k〉),则有如下关系: ⅇ(ⅈ)= vⅇ(j) l(ⅈ)=vl(k)-dut(〈j,k〉) 求vⅇ(j)和vl(j)需分两步进行: 第一步:从vⅇ(0)=0开始向前递推 vⅇ(j)=Max\{vⅇ(i)+dut(〈j,k〉)\} 〈i,j〉∈T,j=1,2,…,n-1 其中,T是所有以第j个顶点为头的弧的集合。 第二步:从vl(n-1)=vⅇ(n-1)起向后递推 vl(i)=Min\{vl(j)-dut(〈i,j〉)\} 〈i,j〉∈S,i=n-2,…,0 其中,S是所有以第i个顶点为尾的弧的集合。 下面我们以上图AOE网为例,先求每个事件v\_i的最早发生时间,再逆向求每个事件对应的最晚发生时间。再求每个活动的最早发生时间和最晚发生时间,如下面表格: 在活动的统计表中,活动的最早发生时间和最晚发生时间相等的,就是关键活动 关键路径的讨论: ①若网中有几条关键路径,则需加快同时在几条关键路径上的关键活动。 如:a11、a10、a8、a7。 ②如果一个活动处于所有的关键路径上,则提高这个活动的速度,就能缩短整个工程的完成时间。如:a1、a4。 ③处于所有关键路径上的活动完成时间不能缩短太多,否则会使原关键路径变成非关键路径。这时必须重新寻找关键路径。如:a1由6天变成3天,就会改变关键路径。 关键路径算法实现: int CriticalPath(ALGraph G) { //因为G是有向网,输出G的各项关键活动 SqStack T; int i, j; ArcNode* p; int k , dut; if(!TopologicalOrder(G,T)) return 0; int vl[VexNum]; for (i = 0; i < VexNum; i++) vl[i] = ve[VexNum - 1]; //初始化顶点事件的最迟发生时间 while (T.base != T.top) //按拓扑逆序求各顶点的vl值 { for(pop(&T, &j), p = G.vertices[j].firstarc; p; p = p->nextarc) { k = p->adjvex; dut = *(p->info); //dut<j, k> if(vl[k] - dut < vl[j]) vl[j] = vl[k] - dut; }//for }//while for(j = 0; j < G.vexnum; ++j) //求ee,el和关键活动 { for (p = G.vertices[j].firstarc; p; p = p->nextarc) { int ee, el; char tag; k = p->adjvex; dut = *(p->info); ee = ve[j]; el = vl[k] - dut; tag = (ee == el) ? '*' : ' '; PrintCriticalActivity(G,j,k,dut,ee,el,tag); } } return 1; }
相关 拓扑排序 拓扑排序是一张AOV网(Activity Of Vertex NetWork),并且是无环的网! 概念: 设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列V1,V 墨蓝/ 2022年08月05日 13:11/ 0 赞/ 39 阅读
相关 拓扑排序 什么是拓扑排序? 在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序 冷不防/ 2022年06月09日 05:57/ 0 赞/ 235 阅读
相关 拓扑排序 In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski 悠悠/ 2022年06月08日 06:19/ 0 赞/ 31 阅读
相关 拓扑排序 原文地址:[http://blog.csdn.net/lisonglisonglisong/article/details/45543451][http_blog.csdn.n 曾经终败给现在/ 2022年04月22日 13:00/ 0 赞/ 31 阅读
相关 拓扑排序 拓 扑 排 序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就 小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 258 阅读
相关 拓扑排序 (1)有向无环图 无环的有向图,简称 DAG (Directed Acycline Graph) 图。 有向无环图在工程计划和管理方面的应用:除最简单的情况之外,几 古城微笑少年丶/ 2022年03月18日 12:35/ 0 赞/ 302 阅读
相关 拓扑排序 拓扑排序: 拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的 反 淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 358 阅读
相关 拓扑排序 拓扑排序 题目做的烦,题解写着玩 [POJ 2762 Going from u to v or from v to u?][POJ 2762 Going from 谁借莪1个温暖的怀抱¢/ 2021年12月20日 16:11/ 0 赞/ 299 阅读
相关 拓扑排序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程 野性酷女/ 2021年09月19日 05:04/ 0 赞/ 466 阅读
相关 拓扑排序 作用:判断是否存在环 1.数组模拟队列 include <iostream> include <vector> include <cst 喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 534 阅读
还没有评论,来说两句吧...