美文网首页
数据结构与算法(十四)：图的应用-拓扑排序/关键路径

数据结构与算法(十四)：图的应用-拓扑排序/关键路径

作者: 顶级蜗牛 | 来源:发表于2023-12-10 13:36 被阅读0次

    相关文献：
    数据结构与算法(一)：基础理论
    数据结构与算法(二)：线性表的实现
    数据结构与算法(三)：线性表算法设计练习
    数据结构与算法(四)：斐波那契数列
    数据结构与算法(五)：LRU
    数据结构与算法(六)：栈
    数据结构与算法(七)：栈/队列的算法解题思想
    数据结构与算法(八)：队列
    数据结构与算法(九)：树形结构/二叉树/线索化二叉树
    数据结构与算法(十)：哈夫曼树
    数据结构与算法(十一)：图形结构
    数据结构与算法(十二)：图的应用-最小生成树-Prim/Kruskal
    数据结构与算法(十三)：图的应用-最短路径-Dijkstra/Floyd
    数据结构与算法(十四)：图的应用-拓扑排序/关键路径

    一、拓扑排序

    1.简介

    有⼀个表示⼯程的有向图中，⽤顶点表示活动，⽤弧表示活动之间的优先关系，这样有向图为顶点表示活动的⽹。我们称为AOV⽹(Activity On Vertex Network)。

    • 无回路(无回环)；
    • 活动之间有先后关系(不带权重)；
    • 拓扑排序只是一种选择策略，并不是唯一答案；

    注意：不是所有的图都能拓扑排序

    所谓拓扑排序,其实就是对⼀个有向图构造拓扑序列的过程。
    构造过程拓扑序列会产⽣2个结果:
    1.如果此⽹中的全部顶点被输出，则说明它不存在环(回路)的AOV⽹;
    2.如果输出的顶点数少了，哪怕仅少了⼀个，也说明这个⽹存在环(回路)，不是AOV⽹

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

    2.拓扑排序算法解析

    给定图进行拓扑排序的时候，我们基本上是无法确定这图是否能够完整地进行拓扑排序的，我们只需要进行一边排序就行了，根据结果去判断这图能不能行（进行拓扑排序之后，按照一定的顺序去输出了全部的顶点则可以进行拓扑排序啦）。

    • 问题一：AOV ⽹图的存储问题?

    在设计算法的时候涉及到一些删除操作，选用邻接表去存储更加方便。

    • 问题二：如何知道网图中起点是哪个顶点？

    需要对每个顶点进行判断，入度为0的顶点可作为出发点。

    • 问题三：邻接表的结构设计？

    in: 入度 (有几条边指向该顶点)
    data：数据
    firstedge：边表 (该顶点所指向的顶点 - 链表)

    邻接表的结构

    算法基本思路:
    从AOV⽹中选择⼀个⼊度in=0的顶点输出，然后从删去此顶点，并删除以此顶点为尾的弧。继续重复此步骤，直到输出全部顶点或AOV⽹中不存在⼊度为0的顶点为⽌。

    需要借助⼀个数据结构栈。来帮助我们解决避免每次查找时，都要去遍历AOV图中的顶点表查找有没有⼊度为0的顶点。

    1. 创建⼀个栈(stack),⽤来存储⼊度in为0 的顶点序号;
    2. 遍历AOV图中顶点表,判断⼊度为0的顶点全部⼊栈;

    举例算法过程：

    第一次分析

    第二次分析

    第三次分析

    第四次分析

    ... ...

    下面用算法去实现这个过程。

    3.拓扑排序算法实现
    • 邻接矩阵结构
    #include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 14
#define INFINITYC 65535

/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*邻接矩阵结构 */
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网图
    /*1.构成AOV网图*/
void CreateMGraph(MGraph *G)/* 构件图 */
{
    int i, j;
    
    /* printf("请输入边数和顶点数:"); */
    G->numEdges=MAXEDGE;
    G->numVertexes=MAXVEX;
    
    /* 初始化图 */
    for (i = 0; i < G->numVertexes; i++)
    {
        G->vexs[i]=i;
    }
    
    /* 初始化图 */
    for (i = 0; i < G->numVertexes; i++)
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            G->arc[i][j]=0;
        }
    }
    
    G->arc[0][4]=1;
    G->arc[0][5]=1;
    G->arc[0][11]=1;
    G->arc[1][2]=1;
    G->arc[1][4]=1;
    G->arc[1][8]=1;
    G->arc[2][5]=1;
    G->arc[2][6]=1;
    G->arc[2][9]=1;
    G->arc[3][2]=1;
    G->arc[3][13]=1;
    G->arc[4][7]=1;
    G->arc[5][8]=1;
    G->arc[5][12]=1;
    G->arc[6][5]=1;
    G->arc[8][7]=1;
    G->arc[9][10]=1;
    G->arc[9][11]=1;
    G->arc[10][13]=1;
    G->arc[12][9]=1;
}
    • 将AOV网图借助邻近矩阵转换成邻接表结构
    /*2.将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++;
                
            }
        }
    }
}
    • 拓扑排序
    /*3.拓扑排序. 若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;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 拓扑排序!\n");
    MGraph G;
    GraphAdjList GL;
    int result;
    CreateMGraph(&G);
    CreateALGraph(G,&GL);
    result=TopologicalSort(GL);
    printf("result:%d",result);
    return 0;
}

    二、关键路径

    1.简介

    在⼀个表示⼯程的带权有向图中，⽤顶点表示事件，⽤有向边表示活动，⽤边上的权值表示活动的持续时间，这种有向图的边表表示活动的⽹，我们称之为 AOE ⽹(Activity On Edge Network)。

    没有⼊边的顶点称为始点或源点;
    没有出边的顶点称为终点或汇点;
    由于⼀个⼯程，总有⼀个开始，⼀个结束，所以正常情况下，AOE⽹只有⼀个源点和⼀个汇点。

    AOE网
    • 路径上各个活动所持续的时间之和称为路径⻓度；
    • 从源点到汇点具有最⼤的路径叫关键路径；
    • 在关键路径上的活动叫关键活动；
    • AOE网就是带权值的AOV网。
    2.关键路径算法解析

    求解过程⼏个核⼼参数：

    • 事件最早发⽣的时间 etv(earliest time of vertex): 即顶点Vk 的最早发⽣时间;
    • 事件最晚发⽣时间 ltv(latest time of vertex): 即顶点Vk 的最晚发⽣时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个⼯期;
    • 活动的最早开⼯时间 ete(earliest time of edge); 即弧Ak 的最早发⽣时间;
    • 活动的最晚开⼯时间 lte(latest time of edge); 即弧Ak 的最晚发⽣时间,也就是不推迟⼯期的最晚开⼯时间。

    算法思路：
    求事件的最早发⽣时间 etv 的过程，就是从头到尾去找拓扑序列的过程。所以在求解关键路径之前，我们需要调⽤⼀次拓扑排序的序列去计算 etv 和拓扑序列列表。

    AOE网
    • etv 的求解

    解释: 找到事件的耗时.例如要完成V3. 需要有V1,V2 .2个条件同时达成.那么V2 需要12⼩时, V1需要8⼩时. 此时需要等待12⼩时,所以需要选择耗时更⻓的为最早发⽣时间。

    求etv的公式
    • ltv 的求解

    事件最晚发⽣时间 ltv (latest time of vertex): 即顶点Vk 的最晚发⽣时间,也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个⼯期。

    ltv的求解

    ... ...

    求ltv的公式

    最终结果：

    • ete和lte 的求解

    活动的最早开⼯时间 ete (earliest time of edge); 即弧Ak 的最早发⽣时间
    活动的最晚开⼯时间 lte (latest time of edge); 即弧Ak 的最晚发⽣时间,也就是不推迟⼯期的最晚开⼯时间

    拓扑序列: 指的是事件在执⾏的顺序
    关键活动: 指的是从开始到结束具有最⼤⻓度的路径叫关键路径,⽽关键路径上的的活动叫做关键活动


    ... ... ...

    关键活动
    3.算法实现

    使用邻接表去存储：

    存储AOE网：

    #include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 30
#define MAXVEX 30
#define INFINITYC 65535

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

/* 邻接矩阵结构 */
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;

/* **************************** */

/* 关于AOE网图的存储代码段-Begin */
//1.完成AOE网图关于邻接矩阵的存储
void CreateMGraph(MGraph *G)/* 构件图 */
{
    int i, j;
    /* printf("请输入边数和顶点数:"); */
    G->numEdges=13;
    G->numVertexes=10;

    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        G->vexs[i]=i;
    }

    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j]=INFINITYC;
        }
    }

    G->arc[0][1]=3;
    G->arc[0][2]=4;
    G->arc[1][3]=5;
    G->arc[1][4]=6;
    G->arc[2][3]=8;
    G->arc[2][5]=7;
    G->arc[3][4]=3;
    G->arc[4][6]=9;
    G->arc[4][7]=4;
    G->arc[5][7]=6;
    G->arc[6][9]=2;
    G->arc[7][8]=5;
    G->arc[8][9]=3;

}

    将邻接矩阵转化成邻接表：

    //2.将邻近矩阵转化成邻接表
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]!=0 && G.arc[i][j]<INFINITYC)
            {
                e=(EdgeNode *)malloc(sizeof(EdgeNode));
                //邻接序号为j
                e->adjvex=j;
                e->weight=G.arc[i][j];
                //将当前顶点上的指向的结点指针赋值给e
                e->next=(*GL)->adjList[i].firstedge;
                //将当前顶点的指针指向e
                (*GL)->adjList[i].firstedge=e;
                (*GL)->adjList[j].in++;

            }
        }
    }
}

    关键路径的求解也是需要进行拓扑排序
    关键路径是拓扑排序结果中的其中一种

    //拓扑排序
Status TopologicalSort(GraphAdjList GL){

    //若GL无回路,则输出拓扑排序序列且返回状态OK, 否则返回状态ERROR;
    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++) {
        //printf("%d %d\n",i,GL->adjList[i].in);
        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;
        
        //例如gettop为V0 ,那么与V0相连接的结点就有etv[1] = 3; etv[2] = 4;
        //例如gettop为V1 ,那么与V1连接的结点就有etv[4]= 3+6=9; etv[3] = 8;
        //例如gettop为V2 ,那么与V2连接的结点就有etv[5]= 4+7=11; etv[3] = 12;
        //例如gettop为V3 ,那么与V3连接的结点就有etv[4]= 12+3=15;
        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值
            //printf("etv[gettop]+e->weight = %d\n",etv[gettop]+e->weight);
            //printf("etv[%d] = %d\n",k,etv[k]);
            if ((etv[gettop] + e->weight) > etv[k]) {
                etv[k] = etv[gettop] + e->weight;
            }
        }

    }
    printf("\n");
    
    //打印etv(事件最早发生时间数组)
//    for (i = 0; i < GL->numVertexes; i++) {
//        printf("etv[%d] = %d\n",i,etv[i]);
//    }
//    printf("\n");
    
    if(count < GL->numVertexes)
        return ERROR;
    else
        return OK;
    return OK;
}

//求关键路径, 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);
            }
        }
    }
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 关键路径的求解!\n");
    MGraph G;
    GraphAdjList GL;
    CreateMGraph(&G);
    CreateALGraph(G,&GL);
    
    //拓扑排序
    //TopologicalSort(GL);
    
    //关键路径
    CriticalPath(GL);

    return 0;
}

    相关文章

      网友评论

          本文标题：数据结构与算法(十四)：图的应用-拓扑排序/关键路径

          本文链接：https://www.haomeiwen.com/subject/kkdgwdtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|数据结构与算法(十四)：图的应用-拓扑排序/关键路径|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！