数据结构（21）图的关键路径

痛定思痛。 2022-11-30 01:21 119阅读 0赞

### 数据结构（21）图的关键路径 ###

*   *   *  前言
         *  关键路径算法的实现
         *  全部代码
         *   *  GraphMtx.h
             *  GraphMtx.c
             *  Main.c

### 前言 ###

图的关键路径同样是有向无环图的应用。在拓扑排序中，我们关心的问题是工程能否顺利进行的问题，与顶点的次序有关；而在关键路径中，我们关心的是完成工程所必须的最短时间的问题，同边的权值有关。

![img\_1][img_1]

如图所示，其中顶点表示工程，边表示活动，边的权值表示活动的持续时间。

以要完成子工程E为例，需要先完成工程B、C，以及B、C的前提工程A。其中，A-B-E边的总权值为7，这意味着E的前提工程A-B-E要7个单位时间才能完成。而A-C-E边的总权值为5，这意味着E的另一个前提工程A-C-E要5个单位时间才能完成。

假设A工程从0时开始，那么E工程最早要在7时才能开始，并且B工程必须在6时就开始。而A-C只需要5个单位时间，即使它在5时能完成，也必须要等到7时才能开始E工程。也就是说，C工程不一定必须在4时就开始，它可以在5时开始（6时完成），也可以在6时开始（7时完成）。

可以发现，A-B工程的完成时间是没有弹性的，它的完成时间决定了E工程的开始时间；而A-C工程则不一定。

这时候，假设我们想提升工程进度，让E工程早一些开始，缩短A-C的时间是没有意义的，必须要从A-B工程入手。

因此可以说，A-B边是一条关键路径。

在图中，有一些活动可以并行进行，所以完成工程的最短时间是从开始到结束的最长路径长度（即路径上各个活动的持续时间），这条路径就叫关键路径。

也就是说，这条最长路径长度决定了整个工程的完成时间，分析关键路径的目的是区分出关键活动，以便提高关键活动的功效，缩短整个工程的完成时间。

### 关键路径算法的实现 ###

计算图的关键路径，与图中每个工程的最早开始和最晚开始时间有关。

![img\_2][img_2]

如图所示，我们从A开始，得到A的邻接顶点B。B的最晚开始时间为6，减掉A-B边的权值6，正好是A的最早开始时间0，说明A-B是一条关键路径，将其输出。

此时得到A的下一个邻接顶点C，C的最晚开始时间为6，减掉A-C边的权值4，得2，与A的最早开始时间不同，说明这不是一条关键路径，继续去找下一个邻接顶点。

这样遍历，就能得到整个图的关键路径。

因此，实现这个算法主要有三个步骤：

1.  计算出每个工程最早开始的时间
2.  计算出每个工程最晚开始的时间
3.  若本结点的最早开始时间同【其邻接顶点的最晚开始时间减去边的权值】一致，则说明该边是关键路径。

同时还需要两个辅助空间，保存每个工程的最早开始时间和最晚开始时间。

//获取两个顶点之间边的权值
    int GetWeight(GraphMtx *g,int v1,int v2){ 
        return (v1 == -1 || v2 == -1) ? 0 : g->Edge[v1][v2];
    }
    //关键路径
    void CriticalPath(GraphMtx *g){ 
        int n = g->NumVertices;
        int *ve = (int *)malloc(sizeof(int)*n);
        int *vl = (int *)malloc(sizeof(int)*n);
        assert(ve != NULL && vl != NULL);
        //初始化
        for (int i = 0; i < n; i ++) { 
            //保存最早开始时间
            ve[i] = 0;
            //保存最晚开始时间
            vl[i] = MAX_COST;
        }
        
        
        int j,w;
        //求解最早开始时间
        for (int i = 0; i < n; i ++) { 
            //获得第一个邻接顶点
            j = GetFirstNeighbor(g, g->VerticesList[i]);
            while (j != -1) { 
                //邻接顶点存在->获取边的值
                w = GetWeight(g, i, j);
                if ((ve[i] + w) > ve[j]) { 
                    //本顶点加上这条边的值后，比原来的时间长
                    //说明工程要更晚才能开始->替换最早开始时间
                    ve[j] = ve[i] + w;
                }
                
                //获取下一个邻接顶点
                j = GetNextNeighbor(g, g->VerticesList[i], g->VerticesList[j]);
            }
        }
        
        //求解最晚开始时间
        //最后一个不变
        vl[n-1] = ve[n-1];
        for (int i = n-2; i > 0; i --) { 
            j = GetFirstNeighbor(g, g->VerticesList[i]);
            while (j != -1) { 
                //邻接顶点存在-获取边的值
                w = GetWeight(g, i, j);
                if ((vl[j] - w) < vl[i]) { 
                    //本顶点减去这条边的值后，比原来的时间更短
                    //说明这项工程要更早开始->替换最晚开始时间
                    vl[i] = vl[j] - w;
                }
                j = GetNextNeighbor(g, g->VerticesList[i], g->VerticesList[j]);
            }
        }
        
        int Ae,Al;
        //求关键路径
        for (int i = 0; i < n; i ++) { 
            j = GetFirstNeighbor(g, g->VerticesList[i]);
            while (j != -1) { 
                Ae = ve[i];
                Al = vl[j] - GetWeight(g, i, j);
                if (Ae == Al) { 
                    printf("<%c,%c>是关键路径\n",g->VerticesList[i],g->VerticesList[j]);
                }
                j = GetNextNeighbor(g, g->VerticesList[i], g->VerticesList[j]);
            }
        }
    }

### 全部代码 ###

#### GraphMtx.h ####

#ifndef GraphMtx_h
    #define GraphMtx_h
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    //默认的顶点个数
    #define DEFAULT_VERTEX_SIZE 10
    //顶点的数据类型
    #define T char
    //默认最大值
    #define MAX_COST 0x7FFFFFFF
    
    typedef struct GraphMtx{ 
        //最大的顶点数
        int MaxVertices;
        //现有的顶点数
        int NumVertices;
        //现有的边数
        int NumEdges;
        
        //顶点列表
        T *VerticesList;
        //边->矩阵
        //int Edge[DEFAULT_VERTEX_SIZE][DEFAULT_VERTEX_SIZE];
        int **Edge;
    }GraphMtx;
    
    //初始化
    void InitGraph(GraphMtx *g);
    
    //展示图
    void ShowGraph(GraphMtx *g);
    
    //获取顶点位置
    int GetVertexPos(GraphMtx *g,T v);
    
    //插入顶点
    void InsertVertex(GraphMtx *g,T v);
    //插入边-无向
    void InsertEdge(GraphMtx *g,T v1,T v2,int cost);
    //删除顶点
    void RemoveVertex(GraphMtx *g, T v);
    void RemoveVertex2(GraphMtx *g, T v);
    //删除边
    void RemoveEdge(GraphMtx *g,T v1,T v2);
    
    //获取第一个邻接顶点
    int GetFirstNeighbor(GraphMtx *g,T v);
    //获取下一个邻接顶点
    int GetNextNeighbor(GraphMtx *g,T v,T w);
    
    //摧毁图
    void DestoryGraph(GraphMtx *g);
    
    //获取两个顶点之间边的权值
    int GetWeight(GraphMtx *g,int v1,int v2);
    //关键路径
    void CriticalPath(GraphMtx *g);
    
    #endif /* GraphMtx_h */

#### GraphMtx.c ####

#include "GraphMtx.h"
    
    //初始化
    void InitGraph(GraphMtx *g){ 
        //数据初始化
        g->MaxVertices = DEFAULT_VERTEX_SIZE;
        g->NumVertices = g->NumEdges = 0;
        
        //开辟储存顶点的空间
        g->VerticesList = (T*)malloc(sizeof(T) * g->MaxVertices);
        assert(g->VerticesList != NULL);
        
        //开辟储存边的空间
        g->Edge = (int **)malloc(sizeof(int*) * g->MaxVertices);
        assert(g->Edge != NULL);
        for (int i = 0; i < g->MaxVertices; i ++) { 
            g->Edge[i] = (int *)malloc(sizeof(int) * g->MaxVertices);
            assert(g->Edge[i] != NULL);
        }
        
        //初始化边
        for (int i = 0; i < g->MaxVertices; i ++) { 
            for (int j = 0; j < g->MaxVertices; j ++) { 
                g->Edge[i][j] = 0;
            }
        }
    }
    
    //展示图
    void ShowGraph(GraphMtx *g){ 
        
        //打印第一排的顶点
        printf(" ");
        for (int i = 0; i < g->NumVertices; i ++) { 
            printf("%c ",g->VerticesList[i]);
        }
        printf("\n");
        
        //打印边->矩阵
        for (int i = 0; i < g->NumVertices; i ++) { 
            printf("%c ",g->VerticesList[i]);
            for (int j = 0; j < g->NumVertices; j ++) { 
                printf("%d ",g->Edge[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    
    //获取顶点位置
    int GetVertexPos(GraphMtx *g,T v){ 
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (g->VerticesList[i] == v) { 
                return i;
            }
        }
        return -1;
    }
    
    //插入顶点
    void InsertVertex(GraphMtx *g,T v){ 
        if (g->NumVertices == g->MaxVertices) { 
            printf("顶点已满，无法插入\n");
            return;
        }
        g->VerticesList[g->NumVertices ++] = v;
    }
    //插入边
    void InsertEdge(GraphMtx *g,T v1,T v2,int cost){ 
        //获取v1的位置
        int p1 = GetVertexPos(g, v1);
        //获取v2的位置
        int p2 = GetVertexPos(g, v2);
        if (p1 == -1 || p2 == -1) { 
            printf("有顶点不存在\n");
            return;
        }
        
        g->Edge[p1][p2] = cost;
        g->NumEdges ++;
    }
    
    //删除顶点
    void RemoveVertex(GraphMtx *g, T v){ 
        //获取顶点位置
        int p = GetVertexPos(g, v);
        if (p == -1) { 
            printf("顶点不存在\n");
            return;
        }
        
        //删除顶点
        for (int i = p; i < g->NumVertices-1; i ++) { 
            g->VerticesList[i] = g->VerticesList[i+1];
        }
    
        
        //计算要删除的边的数量
        int count = 0;
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (g->Edge[p][i] == 1) { 
                count ++;
            }
        }
        
        //删除行
        for (int  i = p; i < g->NumVertices-1; i ++) { 
            for (int j = 0; j < g->NumVertices; j++) { 
                g->Edge[i][j] = g->Edge[i+1][j];
            }
        }
        
        //删除列
        for (int i = p; i < g->NumVertices-1; i ++) { 
            for (int j = 0; j < g->NumVertices; j ++) { 
                g->Edge[j][i] = g->Edge[j][i+1];
            }
        }
        
        g->NumVertices --;
        g->NumEdges -= count;
    }
    void RemoveVertex2(GraphMtx *g, T v){ 
        //获取顶点位置
        int p = GetVertexPos(g, v);
        if (p == -1) { 
            printf("顶点不存在\n");
            return;
        }
        
        //删除顶点->替换
        g->VerticesList[p] = g->VerticesList[g->NumVertices-1];
        
        //计算要删除的边的数量
        int count = 0;
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (g->Edge[p][i] == 1) { 
                count ++;
            }
        }
        
        //删除边->替换行
        for(int i = 0; i < g->NumVertices; i ++){ 
            g->Edge[p][i] = g->Edge[g->NumVertices-1][i];
        }
        //替换列
        for (int i = 0; i < g->NumVertices; i ++) { 
            g->Edge[i][p] = g->Edge[i][g->NumVertices-1];
        }
        
        g->NumVertices --;
        g->NumEdges -= count;
    }
    //删除边
    void RemoveEdge(GraphMtx *g,T v1,T v2){ 
       //获取顶点位置
        int p1 = GetVertexPos(g, v1);
        int p2 = GetVertexPos(g, v2);
        if (p1 == -1 || p2 == -1) { 
            printf("有顶点不存在\n");
            return;
        }
        
        if (g->Edge[p1][p2] == 1) { 
            g->Edge[p1][p2] = g->Edge[p2][p1] = 0;
            g->NumEdges --;
        }
    }
    
    //获取第一个邻接顶点
    int GetFirstNeighbor(GraphMtx *g,T v){ 
        
        int p = GetVertexPos(g, v);
        if (p == -1) { 
            return -1;
        }
        
        for (int i = 0; i < g->NumVertices; i ++) { 
            if (g->Edge[p][i] != 0) { 
                return i;
            }
        }
        
        return -1;
    }
    //获取顶点v的邻接顶点w的下一个邻接顶点
    int GetNextNeighbor(GraphMtx *g,T v,T w){ 
        int pv = GetVertexPos(g, v);
        int pw = GetVertexPos(g, w);
        if (pv == -1 || pw == -1) { 
            return -1;
        }
        
        for (int i = pw+1; i < g->NumVertices; i ++) { 
            if (g->Edge[pv][i] != 0) { 
                return i;
            }
        }
        
        return -1;
    }
    
    //摧毁图
    void DestoryGraph(GraphMtx *g){ 
        //释放顶点空间
        free(g->VerticesList);
        g->VerticesList = NULL;
        for (int i = 0; i < g->NumVertices; i ++) { 
            free(g->Edge[i]);
        }
        g->Edge = NULL;
        g->MaxVertices = g->NumEdges = g->NumVertices = 0;
    }
    
    //获取两个顶点之间边的权值
    int GetWeight(GraphMtx *g,int v1,int v2){ 
        return (v1 == -1 || v2 == -1) ? 0 : g->Edge[v1][v2];
    }
    
    //关键路径
    void CriticalPath(GraphMtx *g){ 
        int n = g->NumVertices;
        int *ve = (int *)malloc(sizeof(int)*n);
        int *vl = (int *)malloc(sizeof(int)*n);
        assert(ve != NULL && vl != NULL);
        //初始化
        for (int i = 0; i < n; i ++) { 
            //保存最早开始时间
            ve[i] = 0;
            //保存最晚开始时间
            vl[i] = MAX_COST;
        }
        
        
        int j,w;
        //求解最早开始时间
        for (int i = 0; i < n; i ++) { 
            //获得第一个邻接顶点
            j = GetFirstNeighbor(g, g->VerticesList[i]);
            while (j != -1) { 
                //邻接顶点存在->获取边的值
                w = GetWeight(g, i, j);
                if ((ve[i] + w) > ve[j]) { 
                    //本顶点加上这条边的值后，比原来的时间长
                    //说明工程要更晚才能开始->替换最早开始时间
                    ve[j] = ve[i] + w;
                }
                
                //获取下一个邻接顶点
                j = GetNextNeighbor(g, g->VerticesList[i], g->VerticesList[j]);
            }
        }
        
        //求解最晚开始时间
        //最后一个不变
        vl[n-1] = ve[n-1];
        for (int i = n-2; i > 0; i --) { 
            j = GetFirstNeighbor(g, g->VerticesList[i]);
            while (j != -1) { 
                //邻接顶点存在-获取边的值
                w = GetWeight(g, i, j);
                if ((vl[j] - w) < vl[i]) { 
                    //本顶点减去这条边的值后，比原来的时间更短
                    //说明这项工程要更早开始->替换最晚开始时间
                    vl[i] = vl[j] - w;
                }
                j = GetNextNeighbor(g, g->VerticesList[i], g->VerticesList[j]);
            }
        }
        
        int Ae,Al;
        //求关键路径
        for (int i = 0; i < n; i ++) { 
            j = GetFirstNeighbor(g, g->VerticesList[i]);
            while (j != -1) { 
                Ae = ve[i];
                Al = vl[j] - GetWeight(g, i, j);
                if (Ae == Al) { 
                    printf("<%c,%c>是关键路径\n",g->VerticesList[i],g->VerticesList[j]);
                }
                j = GetNextNeighbor(g, g->VerticesList[i], g->VerticesList[j]);
            }
        }
    }

#### Main.c ####

int main(int argc, const char * argv[]) { 
        GraphMtx gm;
        InitGraph(&gm);
        InsertVertex(&gm,'A');
        InsertVertex(&gm,'B');
        InsertVertex(&gm,'C');
        InsertVertex(&gm,'D');
        InsertVertex(&gm,'E');
        InsertVertex(&gm,'F');
        InsertVertex(&gm,'G');
        InsertVertex(&gm,'H');
        InsertVertex(&gm,'I');
        
        InsertEdge(&gm,'A','B',6);
        InsertEdge(&gm,'A','C',4);
        InsertEdge(&gm,'A','D',5);
        InsertEdge(&gm,'B','E',1);
        InsertEdge(&gm,'C','E',1);
        InsertEdge(&gm,'D','F',2);
        InsertEdge(&gm,'E','G',9);
        InsertEdge(&gm,'E','H',7);
        InsertEdge(&gm,'F','H',4);
        InsertEdge(&gm,'G','I',2);
        InsertEdge(&gm,'H','I',4);
    
        ShowGraph(&gm);
        
        CriticalPath(&gm);
    
        DestoryGraph(&gm);
        
        return 0;
    }

[img_1]: /images/20221124/6dd34ec59c114d5aaa5e3578aba45a67.png
[img_2]: /images/20221124/5d586e391c6c4ed8a6016871e55ce9c9.png