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(v2)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)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)网络

  • 一般用于安排项目的工序
  • aja_j(活动)指向顶点vjv_j(事件)表示活动到此结束
    • 顶点vjv_j(事件)中通常包含三种信息
      • 事件编号jj
      • 最早完成时间(Earliest)
        • 对于AOE网中的任意一个事件来说,从源点到该点的最长路径代表着该事件的最早发生时间
      • 最晚完成时间(Latest)
        • 表示在不推迟整个工期的前提下,事件允许的最晚发生时间
  • 有向边iji_j(活动)通常包括两种信息
    • 活动持续时间C<i,j>C<i,j>
    • 活动机动时间D<i,j>Latest(j)Earliest(j)C<i,j>D<i,j>:Latest(j)-Earliest(j)-C<i,j>
      • 事件jj的最晚开始时间-事件jj的最早开始时间-活动iji_j持续时间,取其中最早的那一个

关键路径

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

  • 整个项目(活动n)的工期:Earliest[n]Earliest[n]
  • 设最开始的活动0工期为Earliest[0]=0Earliest[0]=0
    • 事件j的工期:Earliest[j]=max{Earliest[i]+C<i,j>},(<i,j>E)Earliest[j]=max\{Earliest[i]+C<i,j>\},(<i,j>∈E)
  • 机动时间D<i,j>=Latest[j]Earliest[i]C<i,j>D<i,j>=Latest[j]-Earliest[i]-C<i,j>
    • 事件iji_j的机动时间Latest[i]=min(Latest[j]C<i,j>)Latest[i]=min(Latest[j]-C<i,j>)

关键路径求解步骤

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