拓扑排序&关键路径的求解

一、拓扑排序

算法基本思想：从AOV网中选择一个入度为0的顶点输出，然后从删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或AOV网中不存在入度为0的顶点为止。
在实现这个算法的过程中，我们需要借助一个 数据结构栈，来帮助我们解决避免每次查找时，都要去遍历AOV图中的顶点表查找有没有入度为0的顶点
1、创建一个栈，用来存储入度in为0的顶点序号
2、遍历AOV图中顶点表，判断入度为0的顶点全部入栈

邻接矩阵结构

typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

邻接表结构

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

构成AOV网

void CreateMGraph(MGraph *G)/* 构件图 */

将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));
                //邻接序号为j
                e->adjvex=j;
                // 将当前顶点上的指向的结点指针赋值给e
                e->next=(*GL)->adjList[i].firstedge;
                //将当前顶点的指针指向e
                (*GL)->adjList[i].firstedge=e;
                (*GL)->adjList[j].in++;
                
            }
        }
    }
}

拓扑排序. 若AOV网图无回路则输出拓扑排序的序列并且返回状态值1,若存在回路则返回状态值0

拓扑排序:解决的是一个工程能否顺序进行的问题

Status TopologicalSort(GraphAdjList GL){
    
    EdgeNode *e;
    int i,k,gettop;
    //用于栈指针下标
    int top=0;
    //用于统计输出顶点的个数
    int count=0;
    
    //建栈将入度为0的顶点入栈(目的:为了避免每次查找时都要遍历顶点表查找有没有入度为0的顶点)
    int *stack=(int *)malloc(GL->numVertexes * sizeof(int) );
    
    //1.遍历邻接表-顶点表,将入度in为0的顶点入栈
    /*参考图1> 此时stack栈中应该成为0,1,3.即V0,V1,V3的顶点入度为0*/
    for(i = 0; i<GL->numVertexes; i++)
        //将入度为0的顶点入栈
        if(0 == GL->adjList[i].in)
            stack[++top]=i;
    printf("top = %d\n",top);
    
    //2.循环栈结构(当栈中有元素则循环继续)
    while(top!=0)
    {
        //出栈
        gettop=stack[top--];
        printf("%d -> ",GL->adjList[gettop].data);
        
        //输出顶点，并计数
        count++;
        
        //遍历与栈顶相连接的弧
        for(e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            //获取与gettop连接的顶点
            k=e->adjvex;
            
            //1.将与gettop连接的顶点入度减1;
            //2.判断如果当前减1后为0,则入栈
            if( !(--GL->adjList[k].in) )
                //将k入栈到stack中,并且top加1;
                stack[++top]=k;
        }
    }
    
    /*思考:3 -> 1 -> 2 -> 6 -> 0 -> 4 -> 5 -> 8 -> 7 -> 12 -> 9 -> 10 ->13 -> 11
     这并不是唯一的拓扑排序结果.
     分析算法:将入度为0的顶点入栈的时间复杂度为O(n), 而之后的while 循环,每个顶点进一次栈,并且出一次栈. 入度减1, 则共执行了e次. 那么整个算法的时间复杂度为O(n+e)*/
    
    printf("\n");
    
    //判断是否把所有的顶点都输出. 则表示找到了拓扑排序;
    if(count < GL->numVertexes)
        return ERROR;
    else
        return OK;
}

二、关键路径的求解

/* 关于AOE网图的存储代码段-End! /
int etv,ltv; / 事件最早发生时间和最迟发生时间数组，全局变量 /
int stack2; / 用于存储拓扑序列的栈 /
int top2; / 用于stack2的指针/

求关键路径, GL为有向网,则输出G的各项关键活动;

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