AOV(Activity On Vertex)网络

顶点表示活动，边表示活动之间的优先关系

拓扑排序

拓扑序：如果图中从v到w有一条有向路径，则v一定排在W之前，满足此条件的顶点序列成为一个拓扑序

获得一个拓扑序的过程就是拓扑排序
AOV如果有合理的拓扑序，则必定是有向无环图(Directed Acyclic Graph, DAG)
- v必须在w开始之前结束

拓扑排序算法伪代码描述：

void TopSort()
{
    for(cnt=0;cnt<nv;cnt++)
    {
        v=为输出的入度为0的顶点; //O(v)
        if(这样的v不存在)  //如果外循环还没结束就已经找不到入度为0的顶点，则说明剩下的顶点中没有入度为0的顶点，存在回路
        {
            ERROR("图中有回路");
            break;
        }
        输出v，或者记录v的输出序号; 
        for(v的每个邻接点w)
            Indegree[w]--;
    }
}

时间复杂度 $T=O(v^2)$
再此基础上可以进行改进，随时将入度为0的顶点放到一个容器里
改进后算法的伪代码描述(BFS方法)：

void TopSort()
{
    for(图中每个顶点v)
        if(Indegree[v]==0)
            Enqueue(v,Q);
    while(!Empty(Q))
    {
        v=Dequeue(Q);
        输出v，或者记录v的输出序号;cnt++:
        for(v的每个邻接点w)
            if(--Indegree[w]==0)
                Enqueue(w,Q);
    }
    if(cnt!=v)
        ERROR("图中有回路");
}

改进后的算法可以用来检测有向图是否DAG
时间复杂度 $T=O(v+e)$

拓扑排序演示

// 浙江大学mooc数据结构课程
#define MaxVertexNum 100
typedef int Vertex;
typedef int WeightType;
typedef int ElementType;
typedef char DataType;
typedef struct LGNode *PtrToLGNode;
typedef struct AdjVNode *PtrToAdjVNode; 
typedef struct QNode *Queue;
typedef PtrToLGNode LGraph;
struct AdjVNode{
    Vertex AdjV;      
    WeightType Weight;  
    PtrToAdjVNode Next;   
};
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
    DataType Data;           
} AdjList[MaxVertexNum];
struct LGNode{  
    int Nv;  
    int Ne;    
    AdjList G;  
};
struct QNode
{
    struct Node *rear;
    struct Node *front;
};
Queue CreateQueue( int );
void AddQ(Queue, ElementType);
bool IsEmpty(Queue);
ElementType DeleteQ(Queue);
/* 邻接表存储 - 拓扑排序算法 */

bool TopSort( LGraph Graph, Vertex TopOrder[] )
{ /* 对Graph进行拓扑排序,  TopOrder[]顺序存储排序后的顶点下标 */
    int Indegree[MaxVertexNum], cnt;
    Vertex V;
    PtrToAdjVNode W;
    Queue Q = CreateQueue( Graph->Nv );
 
    /* 初始化Indegree[] */
    for (V=0; V<Graph->Nv; V++)
        Indegree[V] = 0;
        
    /* 遍历图，得到Indegree[] */
    for (V=0; V<Graph->Nv; V++)
        for (W=Graph->G[V].FirstEdge; W; W=W->Next)
            Indegree[W->AdjV]++; /* 对有向边<V, W->AdjV>累计终点的入度 */
            
    /* 将所有入度为0的顶点入列 */
    for (V=0; V<Graph->Nv; V++)
        if ( Indegree[V]==0 )
            AddQ(Q, V);
            
    /* 下面进入拓扑排序 */ 
    cnt = 0; 
    while( !IsEmpty(Q) ){
        V = DeleteQ(Q); /* 弹出一个入度为0的顶点 */
        TopOrder[cnt++] = V; /* 将之存为结果序列的下一个元素 */
        /* 对V的每个邻接点W->AdjV */
        for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
            if ( --Indegree[W->AdjV] == 0 )/* 若删除V使得W->AdjV入度为0 */
                AddQ(Q, W->AdjV); /* 则该顶点入列 */ 
    } /* while结束*/
    
    if ( cnt != Graph->Nv )
        return false; /* 说明图中有回路, 返回不成功标志 */ 
    else
        return true;
}

关键路径问题

AOE(Activity On Edge)网络

一般用于安排项目的工序
边 $a_j$ $a_{j}$ (活动)指向顶点 $v_j$ $v_{j}$ (事件)表示活动到此结束
- 顶点 $v_j$ $v_{j}$ (事件)中通常包含三种信息
  - 事件编号 $j$
  - 最早完成时间(Earliest)
    - 对于AOE网中的任意一个事件来说，从源点到该点的最长路径代表着该事件的最早发生时间
  - 最晚完成时间(Latest)
    - 表示在不推迟整个工期的前提下，事件允许的最晚发生时间
有向边 $i_j$ $i_{j}$ (活动)通常包括两种信息
- 活动持续时间 $C<i,j>$
- 活动机动时间 $D<i,j>：Latest(j)-Earliest(j)-C<i,j>$ $D < i, j > ： L a t e s t (j) - E a r l i e s t (j) - C < i, j >$
  - 事件 $j$ 的最晚开始时间-事件 $j$ 的最早开始时间-活动 $i_j$ 持续时间，取其中最早的那一个

关键路径

由绝对不允许延误(机动时间为0)的活动(共n个)组成的路径

整个项目(活动n)的工期： $Earliest[n]$
设最开始的活动0工期为 $Earliest[0]=0$ $E a r l i e s t [0] = 0$
- 事件j的工期： $Earliest[j]=max\{Earliest[i]+C<i,j>\},(<i,j>∈E)$
机动时间 $D<i,j>=Latest[j]-Earliest[i]-C<i,j>$ $D < i, j > = L a t e s t [j] - E a r l i e s t [i] - C < i, j >$
- 事件 $i_j$ 的机动时间 $Latest[i]=min(Latest[j]-C<i,j>)$

关键路径求解步骤

首先求出正向拓扑排序求出顶点的最早开始时间： $ve$ $v e$
- $Earliest[j]=Max\{Earliest[i]+C<i,j>\}$
然后逆向拓扑排序求出顶点的最迟开始时间： $vl$ $v l$
- $Latest[i]=min(Latest[j]-C<i,j>)$
利用ve，vl求出边的最早开始时间ee，最迟开始时间el
- ee=el表示此边为关键路径中的边
- ee,el计算公式：假设 $ak=<i,j>$ $a k = < i, j >$
  - $ee=ve(i)$
  - $el=vl(j)-C<i,j>$