数据结构(19)-图之关键路径

作者: xxxxxxxx_123 | 来源:发表于2020-05-17 00:09 被阅读0次

定义

如果我们要获得一个流程图完成的最短时间，就必须要分析它们之间的拓扑关系，并且找到当中最关键的流程，这个流程的时间就是最短时间。所以，图的关键路径一般可用于解决工程完成需要的最短时间。

在一个表示工程的带权值有向图中，用顶点表示事件，用弧表示活动，用弧上的权值表示活动的持续时间，这种有向图被我们称为AOE网(Activity On Edge Network)。我们把AOE网中入度为0的顶点称为源点，出度为0的顶点称之为终点。正常情况下，AOE网只有一个源点，一个终点。

AOE网和AOV网的区别是，AOE网的权值表示活动持续的时间，AOV网的边表示活动之间的制约关系。二者的区别如下图：

aov&aoe.png

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到终点具有最大长度的路径叫做关键路径，在关键路径上的活动称为关键活动。如上图所示，开始->发动机完成->部件集中到位->组装完成就是关键路径，路径长度为5.5。

关键路径算法原理

我们只需要找到所有活动的最早开始时间和最晚开始时间，并且比较他们，如果相等就意味着此活动是关键活动，活动的路径为关键路径，如果不等则不是。所以，我们需要以下辅助参数：

事件的最早发生时间etv(earliest time of vertex)，即顶点 $v_k$ 的最早发生时间
事件的最晚发生时间ltv(latest time of vertex)，即顶点 $v_k$ 的最晚发生时间，超出此时间将会延误整个工期
活动的最早开始时间ete(earliest time of edge)，即弧 $a_k$ 最早发生时间
活动的最晚开始时间lte(latest time of edge)，即弧 $a_k$ 最晚发生时间，超出此时间将会延误整个工期

我们由etv和ltv可以求出ete、lte，然后根据ete[k]和lte[k]来判断弧 $a_k$ 是否是关键活动。求时间的最早发生时间etv的过程，就是我们从头至尾找拓扑序列的过程。因此在求关键路径之前，需要先调用一次拓扑排序来计算etv。下面我们通过一个示例来看看关键路径的计算：

aoce示例.png

首先，实现图的结构：

#define T_MAX_SIZE 100
#define T_ERROR -1
#define T_OK 1
#define MAX_VEX_COUNT 100
#define INT_INFINITY 65535
typedef int TStatus;
// 顶点类型
typedef int VertexType;
// 权值类型
typedef int EdgeType;

typedef struct EdgeNode {
    // 邻接点域 存储邻接点对应的顶点下标
    int adjvex;
    // 权值
    int weight;
    struct EdgeNode *next;
} EdgeNode;

typedef struct VertexNode {
    VertexType data;
    // 指向边表的第一个结点
    EdgeNode *firstEdge;
    // 入度
    int inDegree;
} VertexNode, AdjList[MAX_VEX_COUNT];

typedef struct {
    // 顶点数组
    AdjList adjList;
    int vertexNum, edgeNum;
} AdjListGraph;

typedef struct {
    // 起点下标 终点下标 权值
    int startIndex, endIndex, weight;
} EdgeInfo;

void initEdgeInfos(int edgesNum, int starts[], int ends[], int weights[], EdgeInfo edges[]) {
    for (int i = 0; i < edgesNum; i++) {
        EdgeInfo *eInfo = (EdgeInfo *)malloc(sizeof(EdgeInfo));
        eInfo->startIndex = starts[i];
        eInfo->endIndex = ends[i];
        eInfo->weight = weights[i];
        edges[i] = *eInfo;
    }
}

void initAdjListGraph(AdjListGraph *graph, int vertexNum, int edageNum, VertexType vertexes[], EdgeInfo edges[]) {
    graph->vertexNum = vertexNum;
    graph->edgeNum = edageNum;
    
    // 写入顶点数组 先将firstEdge置为NULL
    for (int i = 0; i < vertexNum; i++) {
        graph->adjList[i].data = vertexes[i];
        graph->adjList[i].firstEdge = NULL;
        graph->adjList[i].inDegree = 0;
    }
    
    EdgeNode *eNode;
    for (int i = 0; i < edageNum; i++) {
        // 先生成边的结尾结点
        eNode = (EdgeNode *)malloc(sizeof(EdgeNode));
        eNode->adjvex = edges[i].endIndex;
        eNode->weight = edges[i].weight;
        // 头插法
        eNode->next = graph->adjList[edges[i].startIndex].firstEdge;
        graph->adjList[edges[i].startIndex].firstEdge = eNode;
        graph->adjList[edges[i].endIndex].inDegree += 1;
    }
}

void printAdjListGraph(AdjListGraph graph) {
    for (int i = 0; i < graph.vertexNum; i++) {
        printf("\n");
        EdgeNode *eNode = graph.adjList[i].firstEdge;
        printf("顶点: %d 入度: %d 边表:", graph.adjList[i].data, graph.adjList[i].inDegree);
        while (eNode) {
            printf("%d->%d(w:%d) ", graph.adjList[i].data, eNode->adjvex, eNode->weight);
            eNode = eNode->next;
        }
    }
    printf("\n");
}

按照拓扑排序的方式对图进行拓扑排序，我们在排序的过程中，即可生成顶点对应的事件最早发生时间数组。

// 事件最早发生时间数组
int *etvs;
// 存储拓扑序列
int *topoStack;
int top2;

TStatus topologicalOrder(AdjListGraph *graph) {
    etvs = (int *)malloc(sizeof(int) * graph->vertexNum);
    int *stack = (int *)malloc(sizeof(int) * graph->vertexNum);
    int top = -1;
    // 将入度为0的顶点入栈
    for (int i = 0; i < graph->vertexNum; i++) {
        if (graph->adjList[i].inDegree == 0) {
            top += 1;
            stack[top] = i;
        }
        etvs[i] = 0;
    }
    
        
    // 栈顶元素
    int stackTop;
    // 记录输出的顶点个数
    int count;
    
    // 存储拓扑排序
    topoStack = (int *)malloc(sizeof(int) * graph->vertexNum);
    top2 = -1;
    
    EdgeNode *eNode;
    while (top != -1) {
        stackTop = stack[top];
        top -= 1;
        top2 += 1;
        topoStack[top2] = stackTop;

        count += 1;
        eNode = graph->adjList[stackTop].firstEdge;
        while (eNode) {
            if (!(--graph->adjList[eNode->adjvex].inDegree)) {
                stack[++top] = eNode->adjvex;
            }
            // 得出每一个顶点 事件的最早发生时间
            // 顶点不同路径之间比较 得到最大值 从上一个顶点到当前顶点有不同的路径 找出最大值
            if (etvs[stackTop] + eNode->weight > etvs[eNode->adjvex]) {
                etvs[eNode->adjvex] = etvs[stackTop] + eNode->weight;
            }
            eNode = eNode->next;
        }
    }
    
    if (count < graph->vertexNum) {
        return T_ERROR;
    }
    
    return T_OK;
}

根据拓扑排序和事件最早发生时间，计算出事件最晚发生时间。然后对比顶点的最早发生时间和最晚发生时间是否相等，相等即为关键路径。

// 事件最晚发生时间数组
int *ltvs;

void getKeyPath(AdjListGraph *graph) {
    ltvs = (int *)malloc(sizeof(int) * graph->vertexNum);
    
    // 默认把事件最晚发生时间都设置为最大的开始时间
    for (int i = 0; i < graph->vertexNum; i++) {
        ltvs[i] = etvs[graph->vertexNum-1];
    }
    
    // 计算事件最迟发生时间数组
    int stackTop;
    EdgeNode *eNode;
    while (top2 != -1) {
        stackTop = topoStack[top2];
        top2 -= 1;
        eNode = graph->adjList[stackTop].firstEdge;
        while (eNode) {
            // 最晚开始时间 = 下一个结点的开始时间 - 路径权值
            if (ltvs[eNode->adjvex] - eNode->weight < ltvs[stackTop]) {
                ltvs[stackTop] = ltvs[eNode->adjvex] - eNode->weight;
            }
            eNode = eNode->next;
        }
    }
 
    
    int ete, lte;
    for (int i = 0; i < graph->vertexNum; i++) {
        eNode = graph->adjList[i].firstEdge;
        while (eNode) {
            ete = etvs[i];
            lte = ltvs[eNode->adjvex] - eNode->weight;
            // 最早开始时间等于最晚开始时间 则该路径就为关键路径
            if (ete == lte) {
                printf("<V%d-V%d> length:%d\n", graph->adjList[i].data, graph->adjList[eNode->adjvex].data, eNode->weight);
            }
            eNode = eNode->next;
        }
    }
}

void keyPathTest() {
    int vertexNumber = 10;
    int edgeNumber   = 13;
    int starts[]     = {0, 0, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7, 8};
    int ends[]       = {1, 2, 4, 3, 3, 5, 4, 6, 7, 7, 9, 8, 9};
    int weights[]    = {3, 4, 6, 5, 8, 7, 3, 9, 4, 6, 2, 5, 3};

    EdgeInfo *eInfos = malloc(sizeof(EdgeInfo) * edgeNumber);
    initEdgeInfos(edgeNumber, starts, ends, weights, eInfos);
    
    AdjListGraph graph;
    VertexType vertexes[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
    initAdjListGraph(&graph, vertexNumber, edgeNumber, vertexes, eInfos);
    
    TStatus st = topologicalOrder(&graph);
    printf("\n%s是AOV网\n", st == T_OK ? "": "不");
    getKeyPath(&graph);
}

// 控制台输出
是AOV网

<V0-V2> length:4
<V2-V3> length:8
<V3-V4> length:3
<V4-V7> length:4
<V7-V8> length:5
<V8-V9> length:3

$m$ 个顶点， $n$ 条弧的AOV网，拓扑排序的时间复杂度为 $O(m+n)$ ，而后进行处理的时间复杂度为 $O(m) + O(m+n) + O(m+n)$ ，所以求关键路径的整体时间复杂度为 $O(m+n)$ 。

参考文献：

大话数据结构

数据结构(19)-图之关键路径

定义

关键路径算法原理

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构