【数据结构】拓扑排序和关键路径 |
您所在的位置:网站首页 › 带优先级的拓扑排序 › 【数据结构】拓扑排序和关键路径 |
拓扑排序和关键路径都是有向无环图的重要应用 拓扑排序 拓扑排序的定义就是从一个集合的偏序关系得到该集合的全序关系。从离散数学中我们可知,假如R是集合X上的偏序关系,则R是自反,反对称和传递的。而全序关系是具有偏序关系特性的同时,对每个 在偏序关系的有向图中加上某些弧成为全序关系,则这个全序关系称为拓扑有序。 用一个偏序的有向图来表示一个流程图,其中顶点表示活动,边则表示的先决条件,也就是活动的优先级,这叫做AOV网(Activity On Vetex Network)。例如学完《离散数学》和《程序设计基础》才能学习《数据结构》,所以用AOV网来表示,如下 ![]() 在AOV网不能出现有向环,因为一个活动的优先级高于它本身的优先级是矛盾的。对一个AOV网判定是否出现这种矛盾,其办法便是拓扑排序,若所有顶点都在这个序列当中,则该AOV网不会存在有向环(假如存在环,则一定有入度不为零的点)。 ![]() 进行拓扑排序的方法为:在图中选择一个没有前驱的顶点删除并将该顶点加入序列(同时删除以该顶点为尾的弧),直到图中没有入度为0的顶点为止。如以下步骤 ![]() 我们用邻接表实现拓扑排序判端是否有环的算法,只需在顶点数组里加入入度的数组,每一步删除入度为0的顶点,并且通过以该点为尾的弧找到以该弧为头的顶点,每个这样的顶点入度都减一,入度为0的顶点通过以栈的形式保存,能避免入度为0的顶点重复检测。 bool TopologicalSort(AlGraph G) { int* stk = (int*)malloc(sizeof(int) * G.vexnum);//用栈来保存入度为0的顶点 int i = 0; for (int v = 0; v < G.vexnum; v++) { if (!G.vertices[v].indgree)stk[i++] = v; }//入度为0的顶点入栈 int count = 0;//通过计数来判断是否所有顶点都加入拓扑有序序列 int temp; while (i) { temp = stk[--i]; count++;//栈中弹出一个入度为0的顶点 for (ArcNode* p = G.vertices[temp].fisrtarc; p ; p=p->nextarc) { if (!(--G.vertices[p->adjvex].indgree))stk[i++] = p->adjvex;//若有一个后继入度减为0则入栈 }//删除这个顶点后,它的每一个后继的入度减一 } if (count < G.vexnum)return false;//若拓扑序列并没有包含图中所有顶点则图中存在环 else return true; }若一个有向图有n个顶点和e条弧,则该算法的时间复杂度为O(n+e)。入度为0的顶点入栈的时间复杂度为O(n)。若有向图无环,则每一个顶点都会入栈一次出栈一次,并且在这一个过程中还要进行该店后继入度减一的操作,它的次数和删除的边数是相等的,所以时间复杂度为O(e)。所以总共的时间复杂度为O(n+e)。 关键路径与AOV网相对应的是AOE网(Activity On Edge),即边表示活动,点表示事件,以该点为头的边表示已完成的活动,以该点为尾的边表示可以开始的活动。例如 ![]()
关键路径下的活动是不会推迟开始或者延迟结束的,它们的所需时间之和正好够整个流程结束,所以它们的最早发生时间和最迟发生时间是相同的,我们记一个活动 为了求得 ![]() 求 求 开始的时间,所以事件最晚发生时间为所有后继减去以该后继为头的活动的时间当中的最小值,因为该值保证了所有以该事件的后继为头的活动的完成。 所以求关键路径的算法描述为:从 代码如下 bool TopologicalOrder(AlGraph G, int* T,int *ev)//先用拓扑排序的方法求出ev数组,所以拓扑排序的过程不再赘述 { int* stk = (int*)malloc(sizeof(int) * G.vexnum); int i = 0,j = 0; for (int v = 0; v < G.vexnum; v++) { if (!G.vertices[v].indgree)stk[i++] = v; } int count = 0; int temp; while (i) { temp = stk[--i]; T[j++] = temp;//记录拓扑序列所用的栈 count++; for (ArcNode* p = G.vertices[temp].fisrtarc; p; p = p->nextarc) { if (ev[p->adjvex] < ev[temp] + p->weight)ev[p->adjvex] = ev[temp] + p->weight;// 求ev数组所用的公式 if (!(--G.vertices[p->adjvex].indgree))stk[i++] = p->adjvex; } } if (count < G.vexnum)return false; else return true; } bool CriticalPath(AlGraph G) { int* ev = (int*)malloc(sizeof(int) * G.vexnum); int* lv = (int*)malloc(sizeof(int) * G.vexnum); int* T = (int*)malloc(sizeof(int) * G.vexnum); for (int v = 0; v < G.vexnum; v++)//初始化ev数组 { ev[v] = 0; } if (!TopologicalOrder(G, T, ev))return false;//若图中存在环则终止 lv[G.vexnum - 1] = ev[G.vexnum - 1];//流程结束的顶点lv等于ev int top = G.vexnum; while (top) { int temp = T[--top];//T出栈顺序则是lv的计算顺序 for (ArcNode* p = G.vertices[temp].fisrtarc ; p; p = p->nextarc) { if (p == G.vertices[temp].fisrtarc)lv[temp] = lv[p->adjvex] - p->weight;//初始化当前顶点的lv if (lv[p->adjvex] - p->weight < lv[temp])lv[temp] = lv[p->adjvex] - p->weight;//根据公式计算lv } } for (int v = 0; v < G.vexnum; v++) { for (ArcNode* p = G.vertices[v].fisrtarc; p; p=p->nextarc) { int e = ev[v]; int l = lv[p->adjvex]-p->weight; if (e == l)printf("%d->%d\n", G.vertices[v].data, G.vertices[p->adjvex].data);//求出关键活动 } } } |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |