一、AOV网

AOV网（Activity On Vertex NetWork）用顶点表示活动，边表示活动（顶点）发生的先后关系。AOV网的边不设权值，若存在边<a,b>则表示活动a必须发生在活动b之前。

若网中所有活动均可以排出先后顺序（任两个活动之间均确定先后顺序），则称网是拓扑有序的，这个顺序称为网上一个全序。

在AOV网上建立全序的过程称为拓扑排序的过程，这个算法并不复杂：

在网中选择一个入度为0的顶点输出

在图中删除该顶点及所有以该顶点为尾的边

重复上述过程，直至所有边均被输出。

若图中无入度为0的点未输出，则图中必有环。

AVO图的存储问题

我们根据上面的算法思路可以判断出在拓扑的过程中，会经常的查找及删除，我们发现这时候我们用邻接表的存储会更方便！

AVO图的数据结构设计

/* 邻接表结构****************** */
//边表结点
typedef struct EdgeNode
{
    //邻接点域，存储该顶点对应的下标
    int adjvex;
    //用于存储权值，对于非网图可以不需要
    int weight;
    //链域，指向下一个邻接点
    struct EdgeNode *next;
}EdgeNode;

//顶点表结点
typedef struct VertexNode
{
    //顶点入度
    int in;
    //顶点域，存储顶点信息
    int data;
    //边表头指针
    EdgeNode *firstedge;
}VertexNode, AdjList[MAXVEX];

//图结构
typedef struct
{
    AdjList adjList;
    //图中当前顶点数和边数
    int numVertexes,numEdges;
}graphAdjList,*GraphAdjList;

拓扑排序算法实现分析

我们要遍历入度为0的顶点，然后把入度为0的顶点的指向的各顶点入度减一，如果减一后变为0，我们也需要进行处理，这里我们可以借助一个数据结构栈，用来存储入度为0的顶点，每次出栈的时候，去处理出栈的顶点的数据，如果处理后有新的入度为0的顶点则继续入栈，最后记录出栈的元素个数是否与图的顶点个数相同。
拓补排序算法如下：

/*3.拓扑排序. 若AOV网图无回路则输出拓扑排序的序列并且返回状态值1,若存在回路则返回状态值0*/
/*拓扑排序:解决的是一个工程能否顺序进行的问题!*/
Status TopologicalSort(GraphAdjList GL){
    
    EdgeNode *e;
    int i,k,gettop;
    //用于栈指针下标
    int top=0;
    //用于统计输出顶点的个数
    int count=0;
    
    //建栈将入度为0的顶点入栈(目的:为了避免每次查找时都要遍历顶点表查找有没有入度为0的顶点)
    int *stack=(int *)malloc(GL->numVertexes * sizeof(int) );
    
    //1.遍历邻接表-顶点表,将入度in为0的顶点入栈
    /*参考图1> 此时stack栈中应该成为0,1,3.即V0,V1,V3的顶点入度为0*/
    for(i = 0; i<GL->numVertexes; I++)
        //将入度为0的顶点入栈
        if(0 == GL->adjList[i].in)
            stack[++top]=I;
    printf("top = %d\n",top);
    
    //2.循环栈结构(当栈中有元素则循环继续)
    while(top!=0)
    {
        //出栈
        gettop=stack[top--];
        printf("%d -> ",GL->adjList[gettop].data);
        
        //输出顶点，并计数
        count++;
        
        //遍历与栈顶相连接的弧
        for(e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            //获取与gettop连接的顶点
            k=e->adjvex;
            
            //1.将与gettop连接的顶点入度减1;
            //2.判断如果当前减1后为0,则入栈
            if( !(--GL->adjList[k].in) )
                //将k入栈到stack中,并且top加1;
                stack[++top]=k;
        }
    }
    
    /*思考:3 -> 1 -> 2 -> 6 -> 0 -> 4 -> 5 -> 8 -> 7 -> 12 -> 9 -> 10 ->13 -> 11
     这并不是唯一的拓扑排序结果.
     分析算法:将入度为0的顶点入栈的时间复杂度为O(n), 而之后的while 循环,每个顶点进一次栈,并且出一次栈. 入度减1, 则共执行了e次. 那么整个算法的时间复杂度为O(n+e)*/
    
    printf("\n");
    
    //判断是否把所有的顶点都输出. 则表示找到了拓扑排序;
    if(count < GL->numVertexes)
        return ERROR;
    else
        return OK;
}

二、AOE网

AOE网(Activity On Edge Network)是边表示活动的网，AOE网是带权有向无环图。边代表活动，顶点代表 所有指向它的边所代表的活动 均已完成 这一事件。由于整个工程只有一个起点和一个终点，网中只有一个入度为0的点（源点）和一个出度为0的点（汇点）。
如下图为制造一辆汽车的AOV网和AOE网

关键词：

1、路径上各个活动所持续的时间之和称为路径长度。
2、从源点到汇点具有最大的路径叫关键路径。
3、在关键路径上的活动叫关键活动。

关键路径求解的几个核心参数：

1、事件最早发生时间etv(earliest time of vertex): 即顶点Vk 的最早发⽣生时间;
2、事件最晚发⽣生时间ltv(latest time of vertex): 即顶点Vk 的最晚发⽣生时间,也就
是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个⼯工期;
3、活动的最早开⼯工时间ete
(earliest time of edge); 即弧Ak 的最早发⽣生时间;
4、活动的最晚开⼯工时间 lte(latest time of edge); 即弧Ak 的最晚发⽣生时间,也就
是不不推迟⼯工期的最晚开⼯工时间；

etv的求解：

事件I的最早发生事件其实就是事件I之前的所有事件都完成的最早事件。
如下图：

如图可知;事件V1的最早发生事件等于弧a0的值即etv[1]=3;
事件V2的最早发生事件等于弧a1的值即etv[2]=4;
事件V3的最早发生时间是要等V1和V2都完成，由于V1完成等于etv[1]+a2等于8，
V2完成等于etv[2]+a4等于12，所以etv[3] = max(3+5,4+8)=12。
由此我们可以推出etv的算法公式；

存储解析

int etv,ltv; /* 事件最早发⽣生时间和最迟发⽣生时间数组，全局变量量 /
int stack2; / ⽤用于存储拓拓扑序列列的栈 /
int top2; / ⽤用于stack2的指针/
代码如下：

//拓扑排序
Status TopologicalSort(GraphAdjList GL){

    //若GL无回路,则输出拓扑排序序列且返回状态OK, 否则返回状态ERROR;
    EdgeNode *e;
    int i,k,gettop;
    //栈指针下标;
    int top = 0;
    //用于统计输出的顶点个数.作为拓扑排序是否存在回路的判断依据;
    int count = 0;
    //建栈,将入度in = 0的顶点入栈;
    int *stack = (int *)malloc(GL->numVertexes * sizeof(int));

    //遍历顶点表上入度in �= 0 入栈
    for (i = 0; i < GL->numVertexes;i++) {
        //printf("%d %d\n",i,GL->adjList[i].in);
        if ( 0 == GL->adjList[i].in ) {
            stack[++top] = I;
        }
    }

    //* stack2 的栈指针下标
    top2 = 0;
    //* 初始化拓扑序列栈
    stack2 = (int *)malloc(sizeof(int) * GL->numVertexes);
    //* 事件最早发生时间数组
    etv = (int *)malloc(sizeof(GL->numVertexes * sizeof(int)));
    //* 初始化etv 数组
    for (i = 0 ; i < GL->numVertexes; i++) {
        //初始化
        etv[i] = 0;
    }

    printf("TopologicSort:\t");
    while (top != 0) {
        gettop = stack[top--];
        printf("%d -> ", GL->adjList[gettop].data);
        count++;

        //将弹出的顶点序号压入拓扑排序的栈中;
        stack2[++top2] = gettop;
        
        //例如gettop为V0 ,那么与V0相连接的结点就有etv[1] = 3; etv[2] = 4;
        //例如gettop为V1 ,那么与V1连接的结点就有etv[4]= 3+6=9; etv[3] = 8;
        //例如gettop为V2 ,那么与V2连接的结点就有etv[5]= 4+7=11; etv[3] = 12;
        //例如gettop为V3 ,那么与V3连接的结点就有etv[4]= 12+3=15;
        for(e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            k = e->adjvex;
            
            //将i顶点连接的邻接顶点入度减1,如果入度减一后为0,则入栈
            if(!(--GL->adjList[k].in))
                stack[++top] = k;

            //求各顶点事件的最早发生的时间etv值
            //printf("etv[gettop]+e->weight = %d\n",etv[gettop]+e->weight);
            //printf("etv[%d] = %d\n",k,etv[k]);
            if ((etv[gettop] + e->weight) > etv[k]) {
                etv[k] = etv[gettop] + e->weight;
            }
        }

    }
    printf("\n");
    
    //打印etv(事件最早发生时间数组)
//    for (i = 0; i < GL->numVertexes; i++) {
//        printf("etv[%d] = %d\n",i,etv[I]);
//    }
//    printf("\n");
    
    if(count < GL->numVertexes)
        return ERROR;
    else
        return OK;
    return OK;
}

ltv的求解：

事件最晚发⽣生时间(latest time of vertex): 即顶点Vk 的最晚发⽣生时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个⼯工期;
经过我们上面的求解我们的到的结果如下：

我们将ltv 数组初始化成etv 最后⼀一个事件的时间

开始执行出栈;
1、首先我们出栈gettop=9，由于V9没有弧表,为最后一个顶点,所以Ltv[9]边仍为27.
2、其次我们出栈gettop=8,由于V8有弧表指向V9，所以v8的Ltv[8]应该等于ltv[9]-<V8,V9>的长度。如下图：

3、依次进行出栈操作,当Vi出栈时，Vi的边表的数据个数可能是多个（即指向多个顶点，V8是个个列），所以我们再求解lev[i]时应该取min(ltv[j]-len<i,j>),此时i<顶点个数n-1,j属于所有i能到达的顶点Vj集合。
推导公式如下：

//事件最晚发生时间数组
    ltv = (int *)malloc(sizeof(int) * GL->numVertexes);
   
    //初始化ltv数组
    for (i = 0; i < GL->numVertexes; i++) {
        //初始化ltv数组. 赋值etv最后一个事件的值
        ltv[i] = etv[GL->numVertexes-1];
        //printf("ltv[%d] = %d\n",i,ltv[I]);
    }
    
    //计算ltv(事件最晚发生时间) 出栈求ltv
    while (top2 != 0) {
        
        //出栈(栈顶元素)
        gettop = stack2[top2--];
        
        //找到与栈顶元素连接的顶点; 例如V0是与V1和V2连接
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            //获取与gettop 相连接的顶点
            k = e->adjvex;
            //计算min(ltv[k]-e->weight,ltv[gettop])
            if (ltv[k] - e->weight < ltv[gettop]) {
                //更新ltv 数组
                ltv[gettop] = ltv[k] - e->weight;
            }
        }
    }

活动的最早开⼯工时间ete(earliest time of edge); 即弧Ak 的最早发⽣生时间；

ete 就是表示活动 <Vk, Vj> 的最早开⼯工时间, 是针对这条弧来说的. ⽽而这条弧的弧尾顶点Vk 的事件发⽣生了了, 它才可以发⽣生. 因此ete = etv[k];

活动的最晚开⼯工时间lte(latest time of edge); 即弧Ak 的最晚发⽣生时间；

lte 表示活动<Vk, Vj> 的最晚开⼯工时间, 但此活动再晚也不不能等Vj 事件发⽣生才开始,⽽而是必须在Vj 事件之前发⽣生. 所以lte = ltv[j] - len<Vk, Vj>.

拓拓扑序列列: 指的是事件在执⾏的顺序；

关键活动: 指的是从开始到结束具有最⼤大⻓长度的路路径叫关键路路径,⽽而关键路路径上的的活 动叫做关键活动

所以, 如果判断 ete 与 lte 是否相等,相等就意味着活动之间没有任 何空闲时间.是关键活动. 否则不不是;

求解ete与lte进而求得关键路径的代码如下：

//求解ete,lte 并且判断lte与ete 是否相等.相等则是关键活动;
    //2层循环(遍历顶点表,边表)
    for(j=0; j<GL->numVertexes;j++)
    {
        for (e = GL->adjList[j].firstedge; e; e = e->next) {
            //获取与j连接的顶点;
            k = e->adjvex;
            //ete 就是表示活动 <Vk, Vj> 的最早开工时间, 是针对这条弧来说的.而这条弧的弧尾顶点Vk 的事件发生了, 它才可以发生. 因此ete = etv[k];
            ete = etv[j];
            //lte 表示活动<Vk, Vj> 的最晚开工时间, 但此活动再晚也不能等Vj 事件发生才开始,而是必须在Vj 事件之前发生. 所以lte = ltv[j] - len<Vk, Vj>.
            lte = ltv[k]-e->weight;
            //如果ete == lte 则输出j,k以及权值;
            if (ete == lte) {
                printf("<%d-%d> length:%d\n",GL->adjList[j].data, GL->adjList[k].data, e->weight);
            }
        }
    }