拓扑排序和关键路径求值

拓扑排序和关键路径的求值都是对图的应用，严格来说其实是对有向图应用。

我们先来描述一下拓扑排序，拓扑排序就是根据路径的先后顺序，求出路径。这个路径有多种顺序。

拓扑排序简介

设G = (V,E)是一个具有n个顶点的有向图, V中的顶点序列V1,V2,.....,Vn.若满足从顶点Vi
到Vj有一条路径,则在顶点序列Vi 必须在Vj 之前, 则我们称这样的顶点序列成为拓扑序列

所谓拓扑排序,其实就是对一个有向图构造拓扑序列的过程. 构造过程拓扑序列会产生2个结果:
如果此网中的全部顶点被输出,则说明它不存在环(回路)的AOV网;
如果输出的顶点数少了,哪怕仅少了一个,也说明这个网存在环(回路),不是AOV网

比如说：当你要制作一个东西时，你需要先制作这个东西的小零件，再去做这个东西，因此，根据有向图的指向，选择没有指向该节点的节点为起点，向它指向的节点，依次排序。

15892513215693.png

例如上面这张图：
你需要将v0，v1，v3三个节点先进行排序，在对其他节点进行排序。

AOV网的定义
有一个表示工程的有向图中, 用顶点表示活动, 用弧表示活动之间的优先关系,这样 有向图为顶点表示活动的网. 我们称为AOV网(Activity On Vertex Network).

AOV图的存储问题

下标 in data firstedge adjves next adjves next. adjves next
0 0 v0 11 5 5 4 4 ^
1 0 v1 8 4 4 2 2 ^
2 2 v2 9 6 6 5 5 ^
3 0 v3 13 2 2 ^
4 2 v4 7 ^
5 3 v5 12 8 8 ^
6 1 v6 5 ^
7 2 v7
8 2 v8 7 ^
9 2 v9 11 10 10 ^
10 1 v10 13 ^
11 2 v11
12 1 v12 9 ^
13 2 v13

上面的一些数据，就是利用邻接表的思想去存储AOV图，利用栈将in的值为0的入栈，将与之相连的节点的in减1，若in为0，继续将顶点入栈，依次类推

代码
下面的代码利用连接矩阵转换邻接表，在进行拓扑排序，根据我上面写的一个数据表，可以很好的理解图的结构。

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 14
#define INFINITYC 65535

//邻接矩阵结构
typedef struct {
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
}MGraph;

//邻接表结构
//边表节点
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;

//1、构成AOV网图
void CreateMGraph(MGraph *G){
    
    int i,j;
    
    G->numVertexes = MAXVEX;
    G->numEdges = MAXEDGE;
    
    //初始化图
    for (i = 0; i<G->numVertexes; i++) {
        G->vexs[i] = i;
    }
    
    for (i = 0; i<G->numVertexes; i++) {
        for (j = 0; j<G->numVertexes; j++) {
            G->arc[i][j] = 0;
        }
    }
    
    G->arc[0][4]=1;
    G->arc[0][5]=1;
    G->arc[0][11]=1;
    G->arc[1][2]=1;
    G->arc[1][4]=1;
    G->arc[1][8]=1;
    G->arc[2][5]=1;
    G->arc[2][6]=1;
    G->arc[2][9]=1;
    G->arc[3][2]=1;
    G->arc[3][13]=1;
    G->arc[4][7]=1;
    G->arc[5][8]=1;
    G->arc[5][12]=1;
    G->arc[6][5]=1;
    G->arc[8][7]=1;
    G->arc[9][10]=1;
    G->arc[9][11]=1;
    G->arc[10][13]=1;
    G->arc[12][9]=1;
}

//将AOV网图借助邻接矩阵转换成邻接表
void CreateALGraph(MGraph G,GraphAdjList *L){
    int i,j;
    EdgeNode *e;
    
    //创建图
    *L = (GraphAdjList)malloc(sizeof(graphAdjList));
    //对图中的顶点数，弧数赋值
    (*L)->numEdges = G.numEdges;
    (*L)->numVertexes = G.numVertexes;
    
    for (i = 0; i<G.numVertexes; i++) {
        (*L)->adjList[i].in = 0;
        (*L)->adjList[i].data = G.vexs[i];
        (*L)->adjList[i].firstedge = NULL;
    }
    
    //建立边表
for (i = 0; i<G.numVertexes; i++) {
    for (j = 0; j<G.numVertexes; j++) {
        if(G.arc[i][j] == 1){
            //创建空表节点
            e = (EdgeNode *)malloc(sizeof(EdgeNode));
            e->adjvex = j;
            e->next = (*L)->adjList[i].firstedge;
            (*L)->adjList[i].firstedge = e;
            (*L)->adjList[j].in++;
        }
    }
    }
}

//拓扑排序
int ToplogicalSort(GraphAdjList L){
    EdgeNode *e;
    int i,k,gettop;
    //用于栈指针下标
    int top = 0;
    //用于统计输出顶点个数
    int count = 0;
    //建栈将入度为0的顶点入栈（目的：为了避免每次查找时，都要遍历顶点查找有没有入度为0的顶点）
    int *stack = (int *)malloc(L->numVertexes * sizeof(int));
    //遍历邻接表-顶点表，将入度in为0的顶点入栈
    for(i = 0;i<L->numVertexes;i++)
        if(L->adjList[i].in == 0)
            stack[++top] = i;
    printf("top = %d\n",top);
    
    while (top!=0) {
        //出栈
        gettop = stack[top--];
        printf("%d -> ",L->adjList[gettop].data);
        
        //输出顶点，并计数
        count++;
        
        //遍历与栈顶点相连的弧
        for (e = L->adjList[gettop].firstedge; e; e = e->next) {
            //获取与gettop连接的顶点
            k = e->adjvex;
            
            //1、将与gettop连接的顶点入度减1
            //2、判断如果当前减1后为0，则入栈
            if(!(--L->adjList[k].in))
                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 < L->numVertexes)
        return ERROR;
    else
        return OK;
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("拓扑排序!\n");
    MGraph G;
    GraphAdjList L;
    int result;
    CreateMGraph(&G);
    CreateALGraph(G, &L);
    result = ToplogicalSort(L);
    printf("result : %d\n",result);
    return 0;
}



输出结果：

拓扑排序!
top = 3
3 -> 1 -> 2 -> 6 -> 0 -> 4 -> 5 -> 8 -> 7 -> 12 -> 9 -> 10 -> 13 -> 11 -> 
result : 1
Program ended with exit code: 0

接下来我们来描述一下图的关键路径求解

求关键路径，其实就是有向图的弧带有权重值，根据到达的路径的权重值最大的，得到整个路径的值。
例如一个经典的问题，一个人早上起来，要洗脸刷牙，要煮饭，而煮饭的时间很长，做其他事的时间很短，若要使时间利用率高，你是不是会先将饭放在哪里煮，然后自己去做别的事，这个关键路径求解也是这样。
而关键路径问题还需要考虑先后问题，因此，可以很好的理解，做一件事之前，需要先做其他两件事，而这两件事可以同时一起做，只有两件事都做完了，才能做那件事情，因此，你花的最少时间，就是之前两件事中需要花的时间最多的。

AOE网的介绍

在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动 的持续时间,这种有向图的边表表示活动的网,我们称之为AOE 网(Activity On Edge Network)

没有入边的顶点称为始点或源点; 没有出边的顶点称为终点或汇点;
由于一个工程, 总有一个开始,一个结束.所以正常情况下,AOE网只有一个源点和一个汇点.

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

关键路径求解的核心参数
事件最早发生的时间etv(earliest time of vertex): 即顶点Vk 的最早发生时间;
事件最晚发生时间ltv(latest time of vertex): 即顶点Vk 的最晚发生时间,也就
是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期;
活动的最早开工时间ete(earliest time of edge); 即弧Ak 的最早发生时间;
活动的最晚开工时间lte(latest time of edge); 即弧Ak 的最晚发生时间,也就
是不推迟工期的最晚开工时间.

AOE网的存储邻接表

15892532344021.png

求事件的最早发生时间etv 的过程,就是从头到尾去找拓扑序列的过 程. 所以在求解关键路径之前,我们需要调用一次拓扑排序的序列去计 算etv 和拓扑序列列表.

事件最晚发生时间 ltv (latest time of vertex): 即顶点Vk 的最晚发生时间,也就是每 个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期;

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

代码：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 30
#define MAXVEX 30
#define INFINITYC 65535

//邻接矩阵结构
typedef struct {
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
}MGraph;

//邻接表结构
//边表节点
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;

//1、构成AOV网图
void CreateMGraph(MGraph *G){
    
    int i,j;
    
    G->numVertexes = 10;
    G->numEdges = 13;
    
    //初始化图
    for (i = 0; i<G->numVertexes; i++) {
        G->vexs[i] = i;
    }
    
    for (i = 0; i<G->numVertexes; i++) {
        for (j = 0; j<G->numVertexes; j++) {
            if(i == j)
                G->arc[i][j] = 0;
            else
                G->arc[i][j] = INFINITYC;
        }
    }
    
    G->arc[0][1]=3;
    G->arc[0][2]=4;
    G->arc[1][3]=5;
    G->arc[1][4]=6;
    G->arc[2][3]=8;
    G->arc[2][5]=7;
    G->arc[3][4]=3;
    G->arc[4][6]=9;
    G->arc[4][7]=4;
    G->arc[5][7]=6;
    G->arc[6][9]=2;
    G->arc[7][8]=5;
    G->arc[8][9]=3;
}

//将AOV网图借助邻接矩阵转换成邻接表
void CreateALGraph(MGraph G,GraphAdjList *L){
    int i,j;
    EdgeNode *e;
    
    //创建图
    *L = (GraphAdjList)malloc(sizeof(graphAdjList));
    //对图中的顶点数，弧数赋值
    (*L)->numEdges = G.numEdges;
    (*L)->numVertexes = G.numVertexes;
    
    for (i = 0; i<G.numVertexes; i++) {
        (*L)->adjList[i].in = 0;
        (*L)->adjList[i].data = G.vexs[i];
        //将边表置为空表
        (*L)->adjList[i].firstedge = NULL;
    }
    
    //建立边表
    for (i = 0; i<G.numVertexes; i++) {
        for (j = 0; j<G.numVertexes; j++) {
            if(G.arc[i][j] !=0 && G.arc[i][j] <INFINITYC){
                //创建空表节点
                e = (EdgeNode *)malloc(sizeof(EdgeNode));
                e->adjvex = j;
                e->weight = G.arc[i][j];
                //将当前顶点上的指向的结点指针赋值给e
                e->next = (*L)->adjList[i].firstedge;
                //将当前顶点的指针指向e
                (*L)->adjList[i].firstedge = e;
                (*L)->adjList[j].in++;
            }
        }
    }
}

/*关于AOV网图的存储代码段*/
int *etv,*ltv;//事件最早发生时间和最迟发生时间数组，全局变量
int *stack2;//用于存储拓扑排序的栈
int top2;//用于stack2的指针

//拓扑排序
//拓扑排序
int ToplogicalSort(GraphAdjList L){
    //若GL无回路,则输出拓扑排序序列且返回状态OK, 否则返回状态ERROR;
    EdgeNode *e;
    int i,k,gettop;
    //用于栈指针下标
    int top = 0;
    //用于统计输出顶点个数
    int count = 0;
    //建栈将入度为0的顶点入栈（目的：为了避免每次查找时，都要遍历顶点查找有没有入度为0的顶点）
    int *stack = (int *)malloc(L->numVertexes * sizeof(int));
    //遍历邻接表-顶点表，将入度in为0的顶点入栈
    for(i = 0;i<L->numVertexes;i++)
    {
        if(L->adjList[i].in == 0){
            stack[++top] = i;
        }
    }
    //stack2的栈指针下标
    top2 = 0;
    //初始化拓扑排序列栈
    stack2 = (int *)malloc(L->numVertexes * sizeof(int));
    //事件最早发生时间数组
    etv = (int *)malloc(sizeof(L->numVertexes*sizeof(int)));
    //初始化etv数组
    for (i = 0; i<L->numVertexes; i++) {
        etv[i] = 0;
    }
    
    
    
    while (top!=0) {
        //出栈
        gettop = stack[top--];
        printf("%d -> ",L->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 = L->adjList[gettop].firstedge; e; e = e->next) {
            //获取与gettop连接的顶点
            k = e->adjvex;
            
            //1、将与gettop连接的顶点入度减1
            //2、判断如果当前减1后为0，则入栈
            if(!(--L->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;
            }
        }
    }
    /*思考: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 < L->numVertexes)
        return ERROR;
    else
        return OK;
}

//求关键路径，L为有向网，则输出G的各项关键活动
void CriticalPath(GraphAdjList L){
    EdgeNode *e;
    int i,gettop,k,j;
    
    //声明活动最早发生时间和最迟发生时间
    int ete,lte;
    //求得拓扑序列,计算etv数组以及stack2的值
    ToplogicalSort(L);
    //打印etv数组(事件最早发生时间)
    printf("etv:\n");
    for (i = 0; i<L->numVertexes; i++) {
        printf("etv[%d] = %d\n",i,etv[i]);
    }
    printf("\n");
    //事件最晚发生时间数组
    ltv = (int *)malloc(sizeof(int)*L->numVertexes);
    //初始化ltv数组
    for(i = 0;i<L->numVertexes;i++){
        //初始化ltv数组. 赋值etv最后一个事件的值
        ltv[i] = etv[L->numVertexes-1];
    }
    //计算ltv(事件最晚发生时间) 出栈求ltv
    while (top2!=0) {
        //出栈(栈顶元素)
        gettop = stack2[top2--];
        //找到与栈顶元素连接的顶点；
        for (e = L->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;
        }
    }
    //打印ltv 数组
    printf("ltv:\n");
    for (i = 0; i<L->numVertexes; i++) {
        printf("ltv[%d] = %d \n",i,ltv[i]);
    }
    printf("\n");
    //求解ete,lte 并且判断lte与ete 是否相等.相等则是关键活动;
    //2层循环(遍历顶点表,边表)
    for (j = 0; j<L->numVertexes; j++) {
        for (e = L->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",L->adjList[j].data,L->adjList[k].data,e->weight);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("关键路径求解!\n");
    MGraph G;
    GraphAdjList L;
    CreateMGraph(&G);
    CreateALGraph(G, &L);
    
    CriticalPath(L);
    return 0;
}


输出结果:
关键路径求解!
0 -> 1 -> 2 -> 3 -> 4 -> 6 -> 5 -> 7 -> 8 -> 9 -> 
etv:
etv[0] = 0
etv[1] = 3
etv[2] = 4
etv[3] = 12
etv[4] = 15
etv[5] = 11
etv[6] = 24
etv[7] = 19
etv[8] = 24
etv[9] = 27

ltv:
ltv[0] = 0 
ltv[1] = 7 
ltv[2] = 4 
ltv[3] = 12 
ltv[4] = 15 
ltv[5] = 13 
ltv[6] = 25 
ltv[7] = 19 
ltv[8] = 24 
ltv[9] = 27 

<0-2> length:4
<2-3> length:8
<3-4> length:3
<4-7> length:4
<7-8> length:5
<8-9> length:3
Program ended with exit code: 0

拓扑排序的时间复杂度: O(n+e);
初始化ltv时间复杂度:O(n);
计算ltv的时间复杂度:O(n+e);
计算ete/lte时间复杂度: O(n+e);
所以最终求得关键路径的时间复杂度为: O(n+e)