数据结构----关键路径详解

分手后的思念是犯贱 2022-07-16 00:46 199阅读 0赞

*前言*  
Live beautifully, dream passionately, love completely.  
Name：Willam  
Time：2017/3/7

## 1、AOE-网介绍 ##

我们在学习拓扑排序（如果没学，可以看看这篇博客：[拓扑排序详解][Link 1]）的时候，已经接触了什么是AOV-网，AOV-网是优先考虑顶点的思路，而我们也同样可以优先考虑边，这个就是AOE-网的思路。

若在带权的有向无环图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向无环图称为AOE网。记住AOE-网只是比AOV-网多了一个边的权重，而且AOV-网一般是设计一个庞大的工程各个子工程实施的先后顺序，而我们的AOE-网就是不仅仅关系整个工程中各个子工程的实施的先后顺序，同时也关系整个工程完成最短时间。

因此，通常在AOE网中列出完成预定工程计划所需要进行的活动，每个活动计划完成的时间，要发生哪些事件以及这些事件与活动之间的关系，从而可以确定该项工程是否可行，估算工程完成的时间以及确定哪些活动是影响工程进度的关键。

AOE-网还有一个特点就是：只有一个起点（入度为0的顶点）和一个终点（出度为0的顶点），并且AOE-网有两个待研究的问题：

1.  完成整个工程需要的时间
2.  哪些活动是影响工程进度的关键

## 2、名词解释 ##

![这里写图片描述][SouthEast]

*  关键路径：AOE-网中，从起点到终点最长的路径的长度（长度指的是路径上边的权重和）
 *  关键活动：关键路径上的边

假设起点是vo，则我们称从v0到vi的最长路径的长度为vi的**最早发生时间**，同时，vi的最早发生时间也是所有以vi为尾的弧所表示的**活动的最早开始时间**，使用e（i）表示活动ai最早发生时间，除此之外，我们还定义了一个**活动最迟发生时间**，使用l（i）表示，不推迟工期的最晚开工时间。我们把e（i）=l（i）的活动ai称为**关键活动**，因此，这个条件就是我们求一个AOE-网的关键路径的关键所在了。

所以，我们现在要求的就是每弧所对应的e（i）和l（i），求这两个变量的公式是：

e(i)=ve(j)
    l(i)=vl(k)-dut(<j,k>)

变量的介绍：

首先我们假设活动a（i）是弧<j,k>上的活动，j为弧尾顶点，k为弧头（有箭头的一边），
    ve（j）代表的是弧尾j的最早发生时间，
    vl（k）代表的是弧头k的最迟发生时间
    dut（<j,k>）代表该活动要持续的时间，既是弧的权值

好了，先在我们知道了求e（i）和l（i）就必须先知道各个顶点的ve和vl了，所以下面我们就来求每个顶点ve和vl。其中，我们要知道ve和vl是要分开来求的。

先求ve，从ve（0）=0开始往前推（其实就是从起点开始往后，求各个顶点最早发生时间），公式如下：

ve（j）=Max{ve{i}+dut（<i,j>）};
    <i,j>属于T，j=1,2.....n-1，
    其中T是所有以第j个顶点为头的弧的集合。n为顶点的个数

下面我们继续求：各个顶点的vl，vl是从vl（n-1）=ve（n-1）往后推进（其实就是从终点开始往前求各个顶点的最迟发生时间，其中终点的ve和vl是相等的）

vl（i）=Min{vl(j)-dut(<i,j>)}
    <i,j>属于S，i=n-2,n-3.....0
    其中，S是所有以第i个顶点为尾的弧的集合

## 3、求关键路径的步骤 ##

1.  输入顶点数和边数，已经各个弧的信息建立图
2.  从源点v1出发，令ve\[0\]=0;按照拓扑序列往前求各个顶点的ve。如果得到的拓扑序列个数小于网的顶点数n，说明我们建立的图有环，无关键路径，直接结束程序
3.  从终点vn出发，令vl\[n-1\]=ve\[n-1\]，按逆拓扑序列，往后求其他顶点vl值
4.  根据各个顶点的ve和vl求每个弧的e（i）和l（i），如果满足e（i）=l（i），说明是关键活动。

## 4、求关键路径的代码实现 ##

*  CriticalPath.h文件的代码：

/************************************************************/
    /*                程序作者：Willam                          */
    /*                程序完成时间：2017/3/6                    */
    /*                有任何问题请联系：2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    #pragma once
    //#pragma once是一个比较常用的C/C++杂注，
    //只要在头文件的最开始加入这条杂注，
    //就能够保证头文件只被编译一次。
    
    
    /*
    求解关键路径问题，
    必须是有向无环图才有关键路径
    
    */
    #include<iostream>
    #include<stack>
    #include<string>
    using namespace std;
    //表结点
    struct ArcNode {
        int start;    //弧尾的顶点的下标
        int end;    //弧头的顶点的下标 ，有箭头的一方
        int weight; //弧的权重
        ArcNode * next; //下一条弧
    };
    //头结点
    struct Vnode {
        ArcNode * firstarc;  //第一条依附在该该顶点的弧
        string data;
    };
    
    class Graph_DG {
    private:
        int vexnum; //顶点个数
        int edge;   //边的条数
        Vnode * arc; //邻接表
        int *indegree; //各个顶点的入度情况
        stack<int> List; //拓扑序列中各个边的情况
        int * ve;  //记录每个顶点的最早发生时间
        int * vl;  //记录每个顶点最迟发生时间
    
    public:
        Graph_DG(int vexnum, int edge); 
        ~Graph_DG();//析构函数
        bool check_edge_value(int, int, int); //检查边的信息是否合法
        void createGraph();//创建一个新的图
        void print();//打印图的邻接表
        bool topological_sort();
        bool CriticalPath();
    };

*  CriticalPath.cpp文件的代码

#include"CriticalPath.h"
    
    Graph_DG::Graph_DG(int vexnum, int edge) {  
            /*
            初始化一些基本的信息，
            包括边和顶点个数，各个顶点入度数组，邻接表的等
            */
            this->vexnum = vexnum;
            this->edge = edge;
            this->arc = new Vnode[this->vexnum];
            this->indegree = new int[this->vexnum];
            this->ve = new int[this->vexnum];
            this->vl = new int[this->vexnum];
            for (int i = 0; i < this->vexnum; i++) {
                this->indegree[i] = 0;
                this->ve[i] = 0;
                this->arc[i].firstarc = NULL;
                this->arc[i].data = "v" + to_string(i + 1);
            }
    }
    
    //释放内存空间
    Graph_DG::~Graph_DG() {
        ArcNode * p, *q;
        for (int i = 0; i < this->vexnum; i++) {
            if (this->arc[i].firstarc) {
                p = this->arc[i].firstarc;
                while (p) {
                    q = p->next;
                    delete p;
                    p = q;
                }
            }
        }
        delete[] this->arc;
        delete[] this->indegree;
    }
    //判断我们每次输入的的边的信息是否合法
    //顶点从1开始编号
    bool Graph_DG::check_edge_value(int start, int end,int weight) {
        if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
            return false;
        }
        return true;
    }
    
    void Graph_DG::createGraph() {
        cout << "请输入每条边的起点和终点的编号（顶点从1开始编号）以及每条边的权重" << endl;
        int count = 0; //记录初始化边的条数
        int start, end, weight;
        while (count != this->edge) {
            cin >> start >> end >> weight;
            while (!check_edge_value(start, end, weight)) {
                cout << "输入的信息不合法，请重新输入：" << endl;
                cin >> start >> end >> weight;
            }
            ArcNode * temp = new ArcNode;
            temp->start = start-1;
            temp->end = end-1;
            temp->weight = weight;
            temp->next = NULL;
            //如果当前顶点的还没有边依附时，
            ++indegree[temp->end];   //对应的弧头的顶点的入度加1
            if (this->arc[start - 1].firstarc == NULL) {
                this->arc[start - 1].firstarc = temp;
            }
            else {
                ArcNode * now = this->arc[start - 1].firstarc;
                while (now->next) {
                    now = now->next;
                }//找到该链表的最后一个结点
                now->next = temp;
            }
            ++count;
        }
    }
    void Graph_DG::print() {
        cout << "图的邻接表为：" << endl;
        int  count = 0;
        while (count != this->vexnum) {
            cout << this->arc[count].data << " ";
            ArcNode * temp = this->arc[count].firstarc;
            while (temp) {
                cout << "<"
                    << this->arc[temp->start].data
                    << ","
                    << this->arc[temp->end].data
                    << ">="
                    << temp->weight
                    << " ";
                temp = temp->next;
            }
            cout << "^" << endl;
            ++count;
        }
    }
    
    bool Graph_DG::topological_sort() {
        cout << "图的拓扑序列为：" << endl;
        stack<int> s; //保存入度为0的顶点下标
        ArcNode * temp;
        int i;
        for (i = 0; i < this->vexnum; i++) {
            if (!indegree[i]) s.push(i); //入度为0 ，则入栈
        }
        //count用于计算输出的顶点个数
        int count = 0;
        while (!s.empty()) {
       //如果栈为空，退出循环
            i = s.top(); //i等于栈顶的元素
            s.pop();
            cout << this->arc[i].data << " ";//输出拓扑序列
            temp = this->arc[i].firstarc;
            this->List.push(i);
            while (temp) {
                if (!(--indegree[temp->end])) {
       //如果入度减少到为0，则入栈
                    s.push(temp->end);
                }
                //同时更新ve的值
                if ((ve[i] + temp->weight) > ve[temp->end]) {
                    ve[temp->end] = ve[i] + temp->weight;
                }
                temp = temp->next;
            }
            ++count;
        }
        if (count == this->vexnum) {
            cout << endl;
            return true;
        }
        cout << "此图有环，无拓扑序列" << endl;
        return false;//说明这个图有环
    }
    
    bool Graph_DG::CriticalPath() {
    
        if (!this->topological_sort()) {
            cout << "此图有环，无关键路径" << endl;
            return false;
        }
        cout << "图的关键路径为：" << endl;
        //初始化vl的值都为ve[this->vexnum-1]
        int k;
    
        for (k = 0; k < this->vexnum; k++) {
            vl[k] = ve[this->vexnum - 1];
    
        }
    
        ArcNode * temp;
        while (!this->List.empty()) {
            k = List.top();//从逆拓扑排序开始，求vl
            List.pop();
            temp = this->arc[k].firstarc;
            while (temp) {
                //dut<k,temp->end>，从以第k个顶点为弧尾集合中选择一个最小的值
                //来作为第i个顶点的最迟发生时间
                if (vl[k] > (vl[temp->end] - temp->weight)) {
                    vl[k] = vl[temp->end] - temp->weight;
                }
                temp = temp->next;
            }
        }
        int ee;
        int el;
        for (k = 0; k < this->vexnum; k++) {
            temp= temp = this->arc[k].firstarc;
            while (temp) {
                ee = ve[k];
                el = vl[temp->end] - temp->weight;
                if (ee == el) {
       //这两个值相等，说明它为关键活动：
                    cout << this->arc[k].data
                        << "----"
                        << this->arc[temp->end].data
                        << "="
                        << temp->weight
                        << endl;
                }
                temp = temp->next;
            }
        }
    }

*  main.cpp文件的代码

#include"CriticalPath.h"
    
    //检验输入边数和顶点数的值是否有效，可以自己推算为啥：
    //顶点数和边数的关系是：((Vexnum*(Vexnum - 1)) / 2) < edge
    bool check(int Vexnum, int edge) {
        if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
            return false;
        return true;
    }
    int main() {
        int vexnum; int edge;
    
        cout << "输入图的顶点个数和边的条数：" << endl;
        cin >> vexnum >> edge;
        while (!check(vexnum, edge)) {
            cout << "输入的数值不合法，请重新输入" << endl;
            cin >> vexnum >> edge;
        }
        Graph_DG graph(vexnum, edge);
        graph.createGraph();
        graph.print();
        graph.CriticalPath();
        system("pause");
        return 0;
    
    }

构造下图：  
![这里写图片描述][SouthEast 1]

输入：

9 11
    1 2 6
    1 3 4
    1 4 5
    2 5 1
    3 5 1
    4 6 2
    5 7 9
    5 8 7
    6 8 4
    7 9 2
    8 9 4

输出：  
![这里写图片描述][SouthEast 2]

从输出可以看出，这个图有两条关键路径：  
第一条就是：

v1--v2--v5--v7--v9

第二条是：

v1--v2--v5--v8--v9

我们在构造下图的关键路径：  
![这里写图片描述][SouthEast 3]

输入：

6 8
    1 2 3
    1 3 2
    2 4 2
    2 5 3
    3 4 4
    3 6 3
    4 6 2
    5 6 1

输出：  
![这里写图片描述][SouthEast 4]

从输出可以看出，这个图有一条关键路径：

v1--v3--v4--v6

[Link 1]: http://blog.csdn.net/qq_35644234/article/details/60578189
[SouthEast]: /images/20220716/ab4311158a3848e5b63e8dc29375f2f5.png
[SouthEast 1]: /images/20220716/4c0c72baa4d948298d47228e083c9d64.png
[SouthEast 2]: /images/20220716/146683f876bc4e48ac723be4a6680840.png
[SouthEast 3]: /images/20220716/dd5d0dd0b7c740beab1cbfd763e2e884.png
[SouthEast 4]: /images/20220716/e8b688e0ec5a4d2ebce989e68674d8d5.png