(二)算法实现 下面是具体的C++程序。 long TopoSort(TGrphNode g, long, long *resu) ∥对图g求拓朴序列,存入sesu(结点编号),n为图结点数目。 ∥返回所求得的结点数。若返回值小于n,则表示未能完全拓扑排序 long*S, top, k,1; TGrphEdge *p s= new long+1I top=0 k=0 for(=0; K=n; 1++) if(gi]. in Degree==otop++, s[top]F=i;)
11 (二）算法实现 下面是具体的C++程序。 long TopoSort(TGrphNode *g, long n, long *resu) { //对图g求拓朴序列，存入sesu(结点编号)，n为图结点数目。 //返回所求得的结点数。若返回值小于n，则表示未能完全拓扑排序。 long *s, top, k, i; TGrphEdge *p; s = new long[n+1]; top=0; k=0; for (i=0; i<=n; i++) if (g[i].inDegree == 0) {top++;s[top]=i; }
(二)算法实现 while(top>0) -stop]; top resu[k]i; k++ p=gi]. firstOutEdge while(p!=NULL p->edgeEndldx gi in Degree-- if (gli] in Degree=0) top++; s[top]=i; 3 p=p->next )//while (p!= delete s return k 时间复杂度为O(n+m) 12
12 (二）算法实现 while (top>0) { i=s[top]; top--; resu[k]=i; k++; p=g[i].firstOutEdge; while ( p!=NULL ) { i=p->edgeEndIdx; g[i].inDegree--; if (g[i].inDegree==0) { top++;s[top]=i;} p=p->next; } //while (p!=… } delete [] s; return k; } 时间复杂度为O(n+m)
§6.7AOE网与关键路径 求关键路径是对边加权的有向图的一种操作。 AOE网与AOV网类似,也是一种被赋予了抽象语义的有 向图,是许多实际问题的模型。 13
13 §6.7 AOE网与关键路径 • 求关键路径是对边加权的有向图的一种操作。 • AOE网与AOV网类似，也是一种被赋予了抽象语义的有 向图，是许多实际问题的模型
§6.7.1AOE网与关键路径的概念 (一)AOE网 如果将有向图的结点与边按下列所述赋予抽象意义 则该种有向图就称为AOE网( Activity on edge network) 边(弧):代表活动(操作); 边权:代表活动的持续时间。记边a=<i,j的权为len(a)或 len(i, j) 结点:代表事件(状态)。它表示它的各入边代表的活动均已完 成,而它的出边代表的活动可以开始 AOE网中没有入边的结点称为始点,没有出边的结点 称为终点
14 §6.7.1 AOE网与关键路径的概念 (一）AOE网 • 如果将有向图的结点与边按下列所述赋予抽象意义， 则该种有向图就称为AOE网(Activity On Edge network) – 边（弧）：代表活动（操作）； – 边权：代表活动的持续时间。记边ak =<i, j>的权为len(ak )或 len(i,j)； –结点：代表事件（状态）。它表示它的各入边代表的活动均已完 成，而它的出边代表的活动可以开始。 • AOE网中没有入边的结点称为始点，没有出边的结点 称为终点
AOE一般用来描述工程进度,结点表示工程进展中的状态,边表示子任务。图 6-1就是一个AOE网,它可以看作是一个具有11项子任务和9个状态的假想工程的 进度图 事件含义 1开工 v2活动a完成,活动a4可以开始 v3活动a2完成,活动a5可以开始 al=6(2a4-1a7=9/7a10=2V4活动a3完成,活动a6可以开始 a2=459a87N9V5活动a4与a5完成,活动a7和a8可开始 all=4 v6活动a6完成,活动a9可以开始 3=5 6=2 a9=4 v7活动a7完成,活动a10可以开始 v8活动a8完成,活动al可以开始 v9活动a10和a1成,整个工程完成 图AOE网举例 15
15 AOE一般用来描述工程进度，结点表示工程进展中的状态，边表示子任务。图 6-1就是一个AOE网，它可以看作是一个具有11项子任务和9个状态的假想工程的 进度图 a7=9 a9=4 a6=2 a2=4 a5=1 a1=6 a8=7 a3=5 a4=1 a10=2 a11=4 v1 v2 v3 v4 v5 v6 v7 v8 v9 事件 含义 v1 开工 v2 活动a1完成，活动a4可以开始 v3 活动a2完成，活动a5可以开始 v4 活动a3完成，活动a6可以开始 v5 活动a4与a5完成，活动a7和a8可开始 , v6 活动a6完成，活动a9可以开始 v7 活动a7完成，活动a10可以开始 v8 活动a8完成，活动a11可以开始 v9 活动a10和a11完成，整个工程完成 图 - AOE网举例