图的应用-拓扑排序与关键路径求解

AOV网

在一个表示工程的有向图中，用极点表示活动，用弧表示活动之间的优先联系，这样有向图为极点表示活动的网，咱们称为 AOV 网。

假如此网中的悉数极点被输出，则阐明它不存在环（回路的）AOV 网；假如输出的极点不全，则阐明存在环（回路）AOV 网;

拓扑排序

在 AOV 网中，若不存在回路，则一切活动可排列成一个线性序列，使得每个活动的一切前驱活动都排在该活动的前面，咱们把此序列叫做拓扑序列。由AOV 网构造拓扑序列的进程叫做拓扑排序。

AOV 网的拓扑序列不是仅有的，满足上述定义的任一线性序列都称作它的拓扑序列。

执行进程

1. 从 AOV 网中选择一个入度为 0 的极点输出；
2. 删去此极点，并删去以此极点为尾的弧
3. 继续重复此进程。

代码分析

创立一个数据结构栈，来帮助咱们解决避免每次查找时都要去遍历 AOV 网中的极点表查找有没有入度为0的极点.

1. 创立一个栈，用来存储入度 in 为0的极点序号；
2. 遍历 AOV 图中极点表，判别入度 in为 0 的极点悉数入栈；
3. 遍历 stack 栈，输出栈顶
4. 循环针对栈顶极点 VkV_kVk​ 对应的弧链表进行遍历
5. 找到极点 VkV_kVk​ 链接的其他极点，并将其入度减一，将 VkV_kVk​ 删去

代码完成

极点结构

//边表结点
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;

拓扑排序完成

int TopologicalSort(GraphAdjList GL) {
    EdgeNode *e;
    int i, k, gettop;
    int top = 0;
    int count = 0;
    int *stack = (int *)malloc(GL->numVertexes * sizeof(int));
    //遍历邻接表->极点表
    for (int i = 0; i < GL->numVertexes; i++) {
        if (GL->adjlist[i].in == 0) {
            stack[++top] = i;
        }
    }
    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->adj_vex_index;
            if (!(--GL->adjlist[k].in)) {
                stack[++top] = k;
            }
        }
    }
    printf("\n");
    if (count == GL->numVertexes) {
        return 1;
    }
    return 0;
}

要害途径

相关词汇

1. 事情最早产生时刻： 极点 VkV_kVk​ 的最早产生时刻（便是从头到尾进行拓扑排序的进程）
2. 事情最晚产生时刻： 极点 VkV_kVk​ 的最晚产生时刻
3. 活动的最早开工时刻： 弧 AkA_kAk​ 的最早产生时刻
4. 活动的最晚开工时刻： 弧 AkA_kAk​ 的最晚产生时刻
5. 途径上各个活动所持续的时刻之和称为途径长度
6. 从源点到汇点具有最大的途径叫要害途径
7. 从要害途径上的活动叫要害活动

进程

1. 求事情最早产生时刻 etv，从开始极点v0v_0v0​ 出发，令 $etv[0]=0$，按拓扑有序序列求其他各极点的可能最早产生时刻 etv 值，etv[k]=max(etv[i]+len<Vi,vk>)etv[k]= max(etv[i] + len<V_i,v_k>)etv[k]=max(etv[i]+len<Vi​,vk​>)

   假如得到的拓朴有序序列中极点的个数小于网中极点个数 n，则阐明网中有环，不能求出要害途径，算法结束。

2. 求事情最晚产生时刻 ltv，从完成极点 VkV_kVk​出发，令 $ltv[k]=etv[k]$ ，按逆拓扑有序求其他各极点的答应的最晚产生时刻 ltv 值，ltv[k]=min(ltv[i]−len<Vk,vi>)ltv[k]= min(ltv[i] – len<V_k,v_i>)ltv[k]=min(ltv[i]−len<Vk​,vi​>)

3. 求解活动的最早开工时刻 ete，活动的最晚开工时刻 lte 并且判别 lte 与 ete 是否持平，持平则是要害活动;

要害途径代码完成

求事情最早产生时刻etv

int TopologicalSort(GraphAdjList GL){
    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++) {
        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;
        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值
            if ((etv[gettop] + e->weight) > etv[k]) {
                etv[k] = etv[gettop] + e->weight;
            }
        }
    }
    printf("\n");
    if(count < GL->numVertexes)
        return 0;
    else
        return 1;
    return 1;
}

求要害途径

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);
            }
        }
    }
}