拓扑排序

所谓的拓扑排序就是对一个有向图构建拓扑序列的过程
那么什么是拓扑序列呢？设G = (V,E)是一个具有n个顶点的有向图, V中的顶点序列V1,V2,.....,Vn.若满足从顶点Vi到Vj有一条路径,则在顶点序列列Vi 必须在Vj 之前, 则我们将这样的顶点序列称为拓扑序列.
有一个表示工程的有向图中, 用顶点表示活动, 用弧表示活动之间的优先关系,这样有向图为顶点表示活动的网. 我们称为AOV网(Activity On Vertex Network).
构造过程拓扑序列会产生2个结果:
1.如果此⽹中的全部顶点被输出,则说明它不存在环(回路)的AOV网;
2.如果输出的顶点数少了,哪怕仅少了一个,也说明这个⽹存在环(回路),不是AOV网

关键代码如下：

void createALGraph(MGraph G,GraphAdjList *GL){
    int i,j;
    EdgeNode *e;
    
    *GL = (GraphAdjList)malloc(sizeof(graphAdjList));
    (*GL)->numVertexes = G.numVertexes;
    (*GL)->numEdges = G.numEdges;
    
    for (i = 0; i < G.numVertexes; i++) {
        (*GL)->adjList[i].in = 0;
        (*GL)->adjList[i].data = G.vexs[i];
        (*GL)->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 = (*GL)->adjList[i].firstedge;
                (*GL)->adjList[i].firstedge = e;
                (*GL)->adjList[j].in++;
            }
        }
    }
}

int toposort(GraphAdjList GL){
    EdgeNode *e;
    int i,k,gettop,top = 0, count = 0;
    int *stack = (int *)malloc(GL->numVertexes * sizeof(int));
    
    for (i = 0; i < GL->numVertexes; i++) {
        if (0 == GL->adjList[i].in) {
            stack[++top]=i;
        }
    }
    printf("top = %d\n",top);
    
    while (top != 0) {
        gettop = stack[top--];
        printf("%d -> ",GL->adjList[gettop].data);
        count++;
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            k = e->adjvex;
            if (!(--GL->adjList[k].in)) {
                stack[++top] = k;
            }
        }
    }
    printf("\n");
    if (count<GL->numVertexes) {
        return 0;
    }else
    return 1;
}

关键路径

在⼀个表示工程的带权有向图中,⽤顶点表示事件,⽤有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网(Activity On Edge Network)。没有⼊边的顶点称为始点或源点;没有出边的顶点称为终点或汇点;由于⼀个⼯程, 总有一个开始,一个结束.所以正常情况下,AOE网只有一个源点和⼀个汇点.
路径上各个活动所持续的时间之和称为路径长度从源点到汇点具有最⼤的路径叫关键路径
关键代码如下：

void CriticalPath(GraphAdjList GL){
    EdgeNode *e;
    int i,gettop,k,j;
    
    //声明活动最早发生时间和最迟发生时间变量;
    int ete,*lte;
    
    //求得拓扑序列,计算etv数组以及stack2的值
    TopologicalSort(GL);
   
    //打印etv数组(事件最早发生时间)
    printf("etv:\n");
    for(i = 0; i < GL->numVertexes; i++)
        printf("etv[%d] = %d \n",i,etv[i]);
    printf("\n");
    
    //事件最晚发生时间数组
    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;
            }
        }
    }
    
    //打印ltv 数组
    printf("ltv:\n");
    for (i = 0 ; i < GL->numVertexes; i++) {
        printf("ltv[%d] = %d \n",i,ltv[i]);
    }
    
    printf("\n");
    //求解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);
            }
        }
    }
    
}