关键路径

介绍：

对于关键路径的详细介绍看王道P234页，对于里面事件最早/最晚发生时间，活动的最早/最晚开始时间的概念要清晰，计算要清晰，能够手动模拟关键路径的计算

算法

//使用邻接表来创建AOE网
int CreatUN_AOE(ALGraph* G){
        ArcNode* r[MAX_VERTEX_NUM];     //用作访问标记，用来定位
        ArcNode* p;                     //需要插入的结点
        printf("Please input the num of vex and arc:");
        scanf("%d,%d",&(G->vexnum),&(G->arcnum));
        getchar();

        //初始化数据
        printf("Please input the data of vex:\n");
        for (int i = 0; i < G->vexnum; ++i) {
            scanf("%d",&(G->vertices[i].data));
            getchar();
            G->vertices[i].firstarc = NULL;
            r[i] = NULL;
        }

        int v1,v2,info;
        //读取各边，开始制作邻接表
        for (int i = 0; i < G->arcnum; ++i) {
            printf("Please input the trail , head and info:");
            scanf("%d,%d,%d",&v1,&v2,&info);
            getchar();

            //这里的头和尾指的是，弧头的顶点和弧尾的顶点
            int trail = LocateVex_AL(*G,v1);
            int head = LocateVex_AL(*G,v2);

            //判断图中是否含有顶点
            if (head==-1||trail==-1){
                return 0;
            }
            //制作结点
            p = (ArcNode*)malloc(sizeof (ArcNode));
            if (!p){
                exit(0);    //分配内存失败
            }
            p->adjvex = head;
            p->info = info;
            p->nextarc = NULL;
            if (r[trail] == NULL){
                G->vertices[trail].firstarc = p;
            } else{
                r[trail]->nextarc = p;
            }
            r[trail] = p;
        }
        return 1;
}

void OutPutAllGraph_AOE(ALGraph G){
    ArcNode* p;
    for (int i = 0; i < G.vexnum; ++i) {
        printf("%d->",G.vertices[i].data);
        p = G.vertices[i].firstarc;
        while (p){
            printf("%d|%d\t",p->adjvex,p->info);
            p = p->nextarc;
        }
        printf("\n");
    }
}

//初始化栈操作
#define MaxSize 50      //定义栈的深度
typedef struct {
    int data[MaxSize];      //栈数组
    int top;                //栈头
}SqStack;

//初始化
void InitStack(SqStack* S){
    S->top = -1;        //初始化栈顶指针
}

//判断栈是否为空
bool StackEmpty(SqStack S){
    if (S.top == -1){
        return true;
    } else{
        return false;
    }
}

//进栈
bool Push(SqStack* S,int x){
    if (S->top == MaxSize-1){       //栈满
        return false;
    }
    S->data[++S->top] = x;
    return true;
}

//出栈
bool Pop(SqStack* S,int* x){
    if (S->top == -1){
        return false;       //栈空
    }
    *x = S->data[S->top--];
    return true;
}

//读栈顶元素
bool GetTop(SqStack S,int* x){
    if (S.top == -1){
        return false;
    }
    *x = S.data[S.top];
    return true;
}

//获取所有结点的入度情况
void FindInDegree(ALGraph G,int indegree[MAX_VERTEX_NUM]){
    ArcNode* p;
    for (int i = 0; i < G.vexnum; ++i) {
        indegree[i] = 0;        //初始化数组全部为0
    }
    //遍历邻接表，计算所有顶点的入度情况
    for (int i = 0; i < G.vexnum; ++i) {
        p = G.vertices[i].firstarc;         //指向当前顶点的第一个连接顶点
        while (p){
            indegree[p->adjvex]++;          //度数加一
            p = p->nextarc;
        }
    }
}

//定义全局变量
SqStack T;
int ve[MAX_VERTEX_NUM];     //各时间的最早开始时间
int vl[MAX_VERTEX_NUM];     //各时间的最晚开始时间

/**
 * AOE关键路径的函数列表,该函数的主要目的是获取最早开始时间ve和逆拓扑排序,逆拓扑用栈来存储，
 * 用来计算最晚开始时间vl
 * @param G
 * @param T
 * @return
 */
int TopologicalSort_AOE(ALGraph G){
    int indegree[G.vexnum];     //统计顶点的入度
    FindInDegree(G,indegree);
    ArcNode* p;

    //建立栈结构，用来拓扑排序
    SqStack S;
    InitStack(&S);
    InitStack(&T);

    //查找度为0的顶点，并作为将其压入栈中，作为起始点
    for (int i = 0; i < G.vexnum; ++i) {
        if (indegree[i]==0){
            Push(&S,i);     //压入的时顶点在顶点数组中的下标
        }
        ve[i] = 0;          //初始化最早时间
    }

    int count = 0;

    while (!StackEmpty(S)){
        int index;
        Pop(&S,&index);
        Push(&T,index);      //用来计算最晚开始时间，所以需要先压入栈
        count++;

        //遍历每个结点，获取拓扑排序
        for (p = G.vertices[index].firstarc;p;p = p->nextarc) {
            int k = p->adjvex;      //顶点所在的下标
            //将顶点的入读减一
            indegree[k]--;
            if (indegree[k]==0){        //入度减一之后如果为0，则押入到栈中
                Push(&S,k);
            }

            //计算最早开始时间,如果边的源点的最长路径加上边上的权值，必要汇点的最长路径要长，则覆盖ve数组中对应的位置
            //那么最终结束的时候，ve数组中存储的就是各顶点的最长路径长度
            if (ve[index]+p->info > ve[k]){
                ve[k] = ve[index]+p->info;
            }
        }
    }
    if (count < G.vexnum){
        return false;           //证明有环
    } else{
        return true;
    }
}

/**
 * 主要是计算事件的最晚发生时间，活动的最早和最晚开始时间，然后活动的最早和最晚开始时间相减即可得到最终的关键活动
 * 关键活动所组成的路径即为关键路径
 * @param G
 */
void CriticalPath(ALGraph G){
    //如果拓扑排序失败则证明有环
    if (!TopologicalSort_AOE(G)){
        return;
    }

    //初始化最晚开始时间
    for (int i = 0; i < G.vexnum; ++i) {
        vl[i] = ve[G.vexnum-1];     //使最晚开始时间全部为最中汇点的最早开始时间
    }

    //生成事件最晚发生时间
    int start,end;      //start表示起始点，end表示指向点
    ArcNode* p;
    while (!StackEmpty(T)){
        Pop(&T,&start);
        for (p = G.vertices[start].firstarc;p;p=p->nextarc) {
            end = p->adjvex;      //start点指向的点
            //出事情况下，vl数组中每个单元都是整个图的最终汇点的ve，如果每个边的汇点减去边的权值比源点小，就保存小的
            if (vl[end]-p->info < vl[start]){
                vl[start] = vl[end] - p->info;
            }
        }
    }

    //循环求各边的最早开时间和最晚开始时间
    int k;
    for (int i = 0; i < G.vexnum; ++i) {
        for (ArcNode* t = G.vertices[i].firstarc;t;t=t->nextarc) {
            k = t->adjvex;
            //各活动的最早开时间与各顶点的最早开始时间一样
            int e = ve[i];
            //各活动的最晚开始时间等于各顶点的最晚开始时间减去权值
            int l = vl[k] - t->info;
            //判断是否相等，若相等则表明为关键活动，用*表示
            char tag = (e==l)?'*':' ';
            //分别表示线段的起始点，终点，边上的权值，边上活动的最早开始时间，最晚开始时间，是否是关键活动
            printf("%d %d %d %d %d %c\n",G.vertices[i].data,G.vertices[k].data,t->info,e,l,tag);
        }
    }

}

使用邻接表来表示图