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

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

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

1、AOE-网介绍

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

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

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

AOE-网还有一个特点就是:只有一个起点(入度为0的顶点)和一个终点(出度为0的顶点),并且AOE-网有两个待研究的问题:

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

2、名词解释

这里写图片描述
  • 关键路径: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;

}
这里写图片描述

构造下图:

输入:

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
这里写图片描述

输出:

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

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

第二条是:

v1--v2--v5--v8--v9
这里写图片描述

我们在构造下图的关键路径:

输入:

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
这里写图片描述

输出:

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

v1--v3--v4--v6

点这里可以跳转到人工智能网站

发表评论