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

作者: _涼城 | 来源:发表于2020-05-12 21:53 被阅读0次

图的应用-拓扑排序与关键路径求解
拓扑排序和关键路径求值
拓扑排序&关键路径的求解
图的最短路径和拓扑排序
数据结构_图（1_图的概述）
数据结构基础学习之（图）
图的应用(拓扑排序和关键路径问题)
拓扑排序+关键路径
强连通分量和Kosaraju算法
Graph-一般算法

拓扑排序

AOV网

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样有向图为顶点表示活动的网，我们称为AOV网。
如果此网中的全部顶点被输出，则说明它不存在环（回路的）AOV网；如果输出的顶点不全，则说明存在环（回路）AOV网
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列。由AOV网构造拓扑序列的过程叫做拓扑排序。
AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

执行步骤

从AOV网中选择一个入度为0的顶点输出；
删去此顶点，并删除以此顶点为尾的弧
继续重复此步骤。

代码分析

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

创建一个栈，用来存储入度in为0的顶点序号；
遍历AOV图中顶点表，判断入度为0的顶点全部入栈；
遍历stack 栈，输出栈顶
循环针对栈顶顶点 $V_k$ 对应的弧链表进行遍历
找到顶点 $V_k$ 链接的其他顶点，并将其入度减一，将 $V_k$ 删除

代码实现

顶点结构

入度	数据域	边表头指针
in	data	EdgeNode

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

关键路径

步骤

求事件最早发生时间etv，从开始顶点 $v_0$ 出发，令 etv[0] = 0，按拓扑有序序列求其余各顶点的可能最早发生时间etv值， $etv[k]= max(etv[i] + len<V_i,v_k>)$
如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。
求事件最晚发生时间ltv，从完成顶点 $V_k$ 出发，令ltv[k] = etv[k] ，按逆拓扑有序求其余各顶点的允许的最晚发生时间ltv值, $ltv[k]= min(ltv[i] - len<V_k,v_i>)$
求解活动的最早开工时间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);
             }
         }
     }
     
 }