数据结构（拓扑排序和关键路径）

hanyujianke

2020-05-11

关注关注

拓扑排序

拓扑序列：

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

拓扑排序

对一个无环有向图（AOV网）构造拓扑序列的过程

方法

从AOV网中选择一个没有前驱的顶点（该顶点的入度为0）并输出它
从网中删去该顶点，并且删去从该点发出的全部有向边
重复上述两步，直到剩余网中不再存在没有前驱的顶点为止

因为要删除点和边，所以用邻接表较为方便

#define MAXVEX 10

//边表结点声明
typedef struct EdgeNode{
    int adjvex;
    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;

//拓扑排序算法
//若GL无回路，则会输入拓扑排序序列并返回OK,否则返回ERROE
Status TopoLogicalSort(GraphAdjList GL){
    EdgeNode *e;
    int i,k,gettop;
    int top=0;//用于栈指针下标索引
    int count=0;//用于统计输出顶点的个数
    int *stact;//用于存储入度为0的顶点

    stact=(int *)malloc(GL->numVertexes*sizeof(int));

    for(i=0;i<GL->numVertexes;i++){
        if(0==GL->adjList[i].in){
            stack[++top]=i;//将度为0的顶点下标入栈
        }
    }

    while(0!=top){
        gettop=stact[top--];//出栈
        printf("%d -> ",GL->adjList[gettop].data);
        count++;
        for(e=GL->adjList[gettop].firstedge;e=e->next){
            k=e->adjvex;
            //注意：下边这个if条件是分析整个程序的要点
            //将k号顶点邻接顶的入度-1；因为他的前序已经删除
            //接着判断-1后入度为是否为0，如果为0则也入栈
            if(!(--GL->adjList[k].in)){
                stack[++top]=k;
            }
        }
    }
    if(count<GL->numVertexes){//如果count小于顶点数，说明存在环
        return ERROR;
    }else{
        return OK;
    }
}

关键路径

AOE网

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网。把没入度的顶点称为始点或源点，没有出度的顶点称为终点或汇点

关键路径就是决定整个工程时间的路径；因为工程中有些步骤要在一些步骤完成的基础上才能进行，而有些则不需要，这种没有制约的步骤就可以同时进行，而决定整个整个工程时间的就是这种相互制约的步骤的最长时间和

思路

正向求处事件的最早发生时间，和反向求出事件最晚发生时间；然后根据事件的etv、ltv求出活动的ete和lte；【ete==lte的活动，为关键活动，关键活动组成的路径是关键路径】

注：etv和ltv是针对事件的，ete和lte是针对活动的；并且根据etv、ltv和活动需要的时间是可以求出活动ete和lte的；【活动：etv就是弧尾顶点事件的最早发生时间；lte就是弧头顶底事件ltv（最晚时间）-活动所需时间】

etv：事件最早发生的时间，就是顶点的最早发生时间
ltv：事件最晚发生时间，每个顶点对应事件最晚要开始的时间（超过此时间就会影响工程正常进度）【求得etv后根据活动所需时间反向：etv（最早时间）-活动所需时间（这里虽然看似和lte求法相似（一个用最早发生时间减，一个用最晚时间减），但要考虑当这个顶点事件有多条出度时会求出多个ltv，这时就要取那个最小的，而lte就不会有这种顾忌）】
ete：活动最早开工时间，弧的最早发生时间
lte：活动的最晚发生时间

拓扑排序关键路径数据结构