AOE网

【有向无环图】活动在边上的网（Vctivity On edge network），常用来模拟施工流图，进而管理工程的工期
【例子】此图来源于《数据结构高分笔记》

AOE的应用（AOE的相关概念）

AOE常用来模拟施工流图，进而管理工程的工期，例如在工程中哪些工作要先做；为了控制工期，哪个工作在哪个时间点必须开始

【先来理解一下“最早”、“最迟”、“关键”】工程：考数学。工期：8:30-11:30

• 【最早发生时间】8:30开始考试，你可以先睡一觉，再起来写；但是你最早开始答题的时间也只能是8:30
• 【最迟发生时间】11:30要交卷，你预估最后一大题要花30min时间，那么你开始做最后一大题的最迟时间是11:00，要不就来不及咯
• 【剩余时间】你预留了30min给最后一大题，那么11:00开始做最后一题做就好了；结果你太聪明，9:00就做到了最后一题；这时有2个小时的空余时间，即是剩余时间，它反应的也是一种松弛度
• 【关键活动或关键事件】剩余时间为0的事件或活动就称之为“关键”，因为做完它前面的事情，这件事情就必须要开始，没有耽搁的余地 | 概念 | 解释 | 举例 | | —- | —- | —- | | | | | | 事件k的最早发生时间ve(k) | ve即vertex earliest
  【图中表现为】源点到顶点k的最长路径 | 若事件4要发生，事件4的上游0、1、2都要先发生
  【即】事件4的最早发生时间ve(4)=0到4的最长路径=7 | | 活动z的最早发生时间ee(z) | ee即edges earliest
  ve是说顶点的最早发生时间，ee是说边的最早发生时间 | 【解释】a7、a8的最早发生时间，即是事件4的最早发生时间，如ee(a7)=ee(a8)=ve(4)=7
  【算法】ee(z)=ve(k)
  顶点k是边z的头顶点
  【例】边a3的头顶点是1：ee(a3)=ve(1)=3 | | 关键路径 | 从源点到汇点，图中最长的路径称为关键路径
  【现实意义】整个工期所完成的最短时间 | 【即0->10的最长路径】a1->a4->a8->a12->a13->a14
  【关键路径的时间即为此工程完成的最短时间】a1+a4+a8+a12+a13+a14=28 | | 关键活动 | 关键路径上的活动
  【现实意义】若想要最短时间完成这项工程，这些活动的上游完成后，不能休息，要立刻开始！ | a1、a4、a8、a12、a13、a14 | | 事件k的最迟发生时间vl(k) | vl即vertex latest
  在不推迟工期的前提下，事件k最迟发生时间 | 1. 根据关键路径得到工程结束的最短时间为28天
  2. 事件7距离完成需要17天（7-10有两条路，取时间大的：①7->9->10的时间要10天，②7->8->9->10要17天）
  3. 那么，事件7最迟要在第11天开始！不然28天就完不成了！
  【即】vl(7)=28-17=11 | | 活动的最迟发生时间el(z) | el即edges latest
  在不推迟工期的前提下，活动z最迟发生的时间 | 【解释】a8的最迟发生时间=vl(7)-a8的权重=vl(7)-4=7
  【算法】el(z)=vl(k)-z
  顶点k是边z的尾顶点
  【例】边a14的尾顶点是10：el(a14)=vl(10)-a14=28-6=22 |

原理：求关键活动和关键路径

【要注意区分】ve、vl与ee、el的区别

1. ve、vl针对的是顶点而言，顶点代表的是事件
2. ee、el针对的是边而言，边代表的是活动

求ve、vl（顶点）

| | vl(vertex latest) | 顶点的最迟发生时间，即事件的最迟发生时间 | ①求出逆拓扑有序序列；②汇点的vl=ve=28
；③按逆拓扑序列从尾到头计算vl=｛vl(j)-<k,j>｝的最小值
（j为k的下一个结点） |

【拓扑有序序列】0 1 2 3 4 5 6 7 8 9 10，按此顺序求ve
【逆拓扑有序序列】10 9 6 8 5 7 3 4 1 2 0，按此顺序求vl

求ee、el（边）

例子	ee和el

求关键路径，关键活动

手算举例

C语言实现

【方法一】关键路径即是图中最长的一条（可修改Dijkstra、Floyd算法求）
1.用拓扑排序获得图的源点v和汇点w
2.计算v到w之间的最长路径

【方法二】求ve、vl、ee和el的算法，时间复杂度O(n+e)

typedef struct ArcNode{
    int adjvext;
    int w;
    struct ArcNode *nextarc;
}ArcNode;
typedef struct{
    char data;
    int cnt; //记录该结点的入度
    ArcNode *firstarc;
}VNode;
typedef struct{
    VNode vers[MAXSIZE];
    int vernum, arcnum;
}ALGraph;
// 计算每个结点的入度
void CntVNodeInDegree(ALGraph &G) {
    for (int v=0; v<G.vernum; v++) {
        for (ArcNode *p=G.vers[v].firstarc; p; p=p->next) {
            int w = p->adjvex; //边v->w
            G.vers[w].cnt++;   //w的入度+1
        }
    }
};
// 拓扑排序：order[]为拓扑有序序列，返回1表示图为有向无环图
int TopSort(ALGraph &G, int order[]) {
    int stack[MAXSIZE], top=-1; //存放入度为0的顶点
    int v,w,n;
    // 将图中入度为0的顶点入栈
    for (i=0; i<G.vernum; ++i)
        if (G.vers[i].cnt==0) stack[++top] = i;
    n=0; //已删除n个顶点
    while(top!=-1) { //还有入度为0的顶点
        v = stack[top—-]; //出栈
        //删除此顶点
        order[n] = v; n++;
        for (ArcNode *p=G.vers[v].firstarc; p; p=p->next) {
            w = p->adjvex;
            —-(G.vers[w].cnt);
            if (G.vers[w].cnt==0) stack[++top]=w;
        }
    }
    if (n==G.vernum) return 1;
    else return 0;
}
// 关键路径
int CriticalPath(ALGraph &G, int **map) {
    // map[G.vernum][G.vernum]为G的邻接矩阵；map[v][w]=1表示v->w为关键活动。初始值为INF，表示不是关键活动
    int topo[G.vernum];
    int ve[G.vernum] = {0}, vl[G.vernum] = {0};
    int v, w;
    ArcNode *p;
    // 拓扑排序：检查是否为有向无环图，并获得拓扑序列存到topo[]中
    if (TopSort(G, topo)==0 ) return 0;
    // 计算每个顶点的ve：ve[]初始值为0，ve[w]=Max{ve[v] + vw的边权重}
    for (i=0; i<G.vernum; i++) ve[i]=0; //ve[]初始值为0
    for (i=0; i<G.vernum; i++) {        //遍历拓扑有序序列
        v = topo[i];                    //得到拓扑有序序列的顶点
        // 计算它的下一个顶点：v->w
        for (p=G.vers[v].firstarc; p; p=p->next) {
            w = p->adjvex;                 //它的邻边v->w
            if (ve[w] < ve[v]+p->w)     //ve(尾) ve(头)+边。取最大值
                ve[w] = ve[v]+p->w;        //ve(尾)=ve(头)+边
        }
    }
    // 计算每个顶点的vl：vl[]初始值为ve[汇点]，vl[w]=min{vl[v] - vw边的权重}
    v = topo[G.vernum-1]; //汇点
    for (i=0; i<G.vernum; ++i) vl[i]=ve[v]; //vl[]初始值为ve[汇点]
    for (i=G.vernum-1; i>=0; i—-) {            //从后往前遍历拓扑有序序列
        v = topo[i];                        //拓扑有序序列的顶点
        // 计算它的下一个顶点：v->w
        for (p=G.vers[v].firstarc; p; p=p->next) {
             w = p->adjvex;                 //它的邻边v->w
             if (vl[v] > vl[w]-p->w)         //vl(头) vl(尾)-边。取最小值
                 vl[v] = vl[w]-p->w;        //vl(头)=vl(尾)-边
        }
    }
    // 求关键活动
    int ee, el; //当前活动的ee、el
    for (i=G.vernum-1; i>=0; i—-) { //从右往左遍历拓扑有序序列
        v = topo[i];
        for (p=G.vers[v].firstarc; p; p=p->nextarc) {    //遍历该顶点的边
            w = p->adjvex;        //它的邻边v->w
            ee = ve[v];            //ee(vw)=ve(v)
            el = vl[w]-p->w;    //el(vw)=vl(尾)-边
            if (ee==el) {        //为关键活动
                printf(“(%c->%c)\t”, G.vers[v].data, G.vers[w].data);
                map[v][w] = 1; //v-w边为关键活动
            }
        }
    }
    return 1;
}
void PrintAllCriticalPath(ALGraph &G, int **map, int start, int end) {
    static char path[MAXSIZE] = {‘\0’};
    static int index = 0;
    // 关键路径不只一条，打印出所有的关键路径
    path[index++] = G.vers[start].data;
    if (start==end) {
        path[index] = ‘\0’;
        printf(“%s\n”, path);
    } else {
        for (ArcNode *p=G.vers[start].firstarc; p; p=p->nextarc) {
            int w = p->adjvex;
            if (map[start][w]==1) {
                PrintAllCriticalPath(G, map, w, end);
            }
        }
    }
    index—-;
}