AOE网与关键路径

语言: CN / TW / HK

声明:图片及内容基于 https://www.bilibili.com/video/BV1BZ4y1T7Yx?from=articleDetail

原理

AOE网

关键路径

数据结构

核心代码

TopologicalSort

/*
    TopologicalSort用于实现拓扑排序
    参数:result用来保存处理过的拓扑排序顶点;count用来保存处理过的拓扑排序顶点的个数
    功能:进行拓扑排序,将找到的拓扑顶点序号存入result数组(result可以看成一个栈,count可以看成是栈顶指针)
          增加的功能:用注释=====标识,在拓扑排序的同时计算ve数组的值[事件最早发生时间]
*/
bool ALGraph ::TopologicalSort(int result[], int &count){
    
    int stack[MAX_VERTEX];   //把顶点对应的下标压入堆栈

    int top = -1;
    int inVex; //用来保存从堆栈中弹出的顶点(下标)[书上的j,代表一个边的起始顶点]
    int outVex;//遍历一个顶点的所有邻接边结点时,用outVex暂存当前处理的顶点[书上的k,代表一个边的终止顶点]
    ArcNode *p;
    
    //初始化事件最早发生时间ve数组=====
    for(int i=0;i<vertexNum;i++){
        ve[i]=0;
    }
    //遍历顶点表,把入度为0的压栈
    for(int i=0;i<vertexNum;i++){
        if(adjList[i].in==0){
            stack[++top]=i;
        }
    }
    //完成拓扑排序
    count=0;
    while(top!=-1){
        inVex=stack[top--];
        result[count]=inVex;
        count++;
        p=adjList[inVex].firstEdge;
        while(p){
            outVex=p->adjvex;
            adjList[outVex].in--;
            if(adjList[outVex].in==0)
                stack[++top]=outVex;
            if(ve[inVex]+p->weight>ve[outVex])
                ve[outVex]=ve[inVex]+p->weight;
            p=p->next; 
        }
    }
    //判断拓扑排序是否正确
    if(count==vertexNum)
        return true;
    return false;
}

CriticalPath

/*
    CriticalPath用于求关键路径
    首先调用TopologicalSort函数检查是否是一个没有环的图
*/
bool ALGraph::CriticalPath(){
    
    int resultStack[MAX_VERTEX]; //存储拓扑排序结果序列(存储下标)
    int resultTop;               //拓扑排序有效顶点个数(栈顶指针)
    ArcNode *p;
    int i,count;
    int inVex,outVex;   //inVex,outVex,分别代表一条边的起点顶点号和终点顶点号

    if(!TopologicalSort(resultStack,count)) {
        return false;
    }
    
    //输出拓扑排序的顶点处理顺序
    cout<<"拓扑排序的顶点处理顺序是:"<<endl;
    for(int i=0;i<count;i++){
        cout<<resultStack[i]<<" ";
    }
    cout<<endl;
    //输出ve数组的值
    cout<<"ve数组的值为:"<<endl;
    for(int i=0;i<count;i++){
        cout<<"ve["<<i<<"]="<<ve[i]<<endl;
    }
    //完成关键路径的求解
    resultTop=count-1;
    inVex=resultStack[resultTop--];
    for(int i=0;i<vertexNum;i++){
        vl[i]=ve[inVex];
    }
    while(resultTop!=-1){
        inVex=resultStack[resultTop--];
        p=adjList[inVex].firstEdge;
        while(p){
            outVex=p->adjvex;
            if(vl[inVex]>vl[outVex]-p->weight)
                vl[inVex]=vl[outVex]-p->weight;
            p=p->next;
        }
    }
    cout<<"vl数组的值为:"<<endl;
    for(int i=0;i<count;i++){
        cout<<"vl["<<i<<"]="<<vl[i]<<endl;
    }
    return true;
}

完整代码

#include <iostream>
#include <stdio.h>
using namespace std;

const int MAX_VERTEX = 30;    //图的最大顶点数

struct ArcNode  /*边表*/
{
    int weight;     //增加权值分量,代表活动时间=====
    int adjvex;
    ArcNode *next;
};

struct VertexNode  /*顶点表*/
{
    int in;                //增加入度字段-----
    char vertex;
    ArcNode *firstEdge;
};

class ALGraph {
private:
    VertexNode *adjList;  //邻接表
    int vertexNum, arcNum;
    int *ve, *vl; //ve数组是事件最早发生时间,vl事件最迟发生时间(数组长度跟顶点数相等)=====
public:
    ALGraph(char v[], int n, int e);
    ~ALGraph();
    void inputEdges();
    bool setEdge(int vi,int vj,int weight);
    void displayData();

    bool TopologicalSort(int result[], int &count); //拓扑排序
    bool CriticalPath();   //求关键路径
};

ALGraph:: ALGraph(char v[], int n, int e){
    vertexNum = n;
    arcNum = e;
    adjList = new VertexNode[vertexNum];
    for (int i=0; i<vertexNum; i++) {
        //输入顶点信息,初始化顶点表
        adjList[i].in = 0;    //增加in的初始化-----
        adjList[i].vertex = v[i];
        adjList[i].firstEdge = NULL;
    }
    ve = new int[vertexNum];
    vl = new int[vertexNum];

}
ALGraph ::~ALGraph(){
    ArcNode *p,*pre;
    //遍历顶点表数组,把顶点表指向的所有边结点删除
    for(int i=0; i<vertexNum; i++){
        p = adjList[i].firstEdge;
        adjList[i].firstEdge = NULL;
        while(p){
            pre = p;
            p = p-> next;
            delete pre;
        }
    }
    delete [] adjList;
    delete [] ve;
    delete [] vl;
}

void ALGraph  ::inputEdges(){  //=====
    cout << "请输入两个事件顶点编号(范围0-"<< vertexNum-1 << ")和活动时间:"<<endl;
    for (int i=0; i<arcNum; i++) {
         //输入边的信息存储在边表中
        int vi,vj, weight;
        cin >> vi >> vj >> weight;   //输入边依附的两个顶点的编号
        if(!setEdge(vi,vj,weight)){
            cout << "输入的顶点编号超过范围或者相等,需要重新输入" << endl;
            i--;
        }
    }
}

bool ALGraph::setEdge(int vi,int vj, int weight){  //=====
    //修改setEdge函数,把vj顶点表中的入度+1 -----
    ArcNode *s;
    if (vi>=0 && vi<vertexNum && vj>=0 && vj<vertexNum && vi!=vj){
        //创建一个边结点vj
        s = new ArcNode;
        s->adjvex = vj;
        s->weight = weight; //=====
        //把边结点vj插入到顶点表vi项的邻接表中,成为第一个结点
        s->next = adjList[vi].firstEdge;
        adjList[vi].firstEdge = s;
        //vj顶点表中的入度+1   -----
        adjList[vj].in++;
        return true;
    }
    else {
        return false;
    }
}


void ALGraph ::displayData(){
    ArcNode *p;
     cout << "输出图的存储情况:"<<endl;
    for(int i=0; i<vertexNum; i++){
        cout << "顶点" << adjList[i].vertex << "的入度为:" << adjList[i].in <<",从这个顶点发出的的边为:" << endl;//-----
        p = adjList[i].firstEdge;
        if (!p)
            cout << "没有。"<< endl;
        while(p){
            cout <<"<" << i <<"," << p->adjvex<< ">" << p->weight <<endl;
            p = p->next;
        }
    }
}
/*
    TopologicalSort用于实现拓扑排序
    参数:result用来保存处理过的拓扑排序顶点;count用来保存处理过的拓扑排序顶点的个数
    功能:进行拓扑排序,将找到的拓扑顶点序号存入result数组(result可以看成一个栈,count可以看成是栈顶指针)
          增加的功能:用注释=====标识,在拓扑排序的同时计算ve数组的值[事件最早发生时间]
*/
bool ALGraph ::TopologicalSort(int result[], int &count){
    
    int stack[MAX_VERTEX];   //把顶点对应的下标压入堆栈

    int top = -1;
    int inVex; //用来保存从堆栈中弹出的顶点(下标)[书上的j,代表一个边的起始顶点]
    int outVex;//遍历一个顶点的所有邻接边结点时,用outVex暂存当前处理的顶点[书上的k,代表一个边的终止顶点]
    ArcNode *p;
    
    //初始化事件最早发生时间ve数组=====
    for(int i=0;i<vertexNum;i++){
        ve[i]=0;
    }
    //遍历顶点表,把入度为0的压栈
    for(int i=0;i<vertexNum;i++){
        if(adjList[i].in==0){
            stack[++top]=i;
        }
    }
    //完成拓扑排序
    count=0;
    while(top!=-1){
        inVex=stack[top--];
        result[count]=inVex;
        count++;
        p=adjList[inVex].firstEdge;
        while(p){
            outVex=p->adjvex;
            adjList[outVex].in--;
            if(adjList[outVex].in==0)
                stack[++top]=outVex;
            if(ve[inVex]+p->weight>ve[outVex])
                ve[outVex]=ve[inVex]+p->weight;
            p=p->next; 
        }
    }
    //判断拓扑排序是否正确
    if(count==vertexNum)
        return true;
    return false;
}

/*
    CriticalPath用于求关键路径
    首先调用TopologicalSort函数检查是否是一个没有环的图
*/
bool ALGraph::CriticalPath(){
    
    int resultStack[MAX_VERTEX]; //存储拓扑排序结果序列(存储下标)
    int resultTop;               //拓扑排序有效顶点个数(栈顶指针)
    ArcNode *p;
    int i,count;
    int inVex,outVex;   //inVex,outVex,分别代表一条边的起点顶点号和终点顶点号

    if(!TopologicalSort(resultStack,count)) {
        return false;
    }
    
    //输出拓扑排序的顶点处理顺序
    cout<<"拓扑排序的顶点处理顺序是:"<<endl;
    for(int i=0;i<count;i++){
        cout<<resultStack[i]<<" ";
    }
    cout<<endl;
    //输出ve数组的值
    cout<<"ve数组的值为:"<<endl;
    for(int i=0;i<count;i++){
        cout<<"ve["<<i<<"]="<<ve[i]<<endl;
    }
    //完成关键路径的求解
    resultTop=count-1;
    inVex=resultStack[resultTop--];
    for(int i=0;i<vertexNum;i++){
        vl[i]=ve[inVex];
    }
    while(resultTop!=-1){
        inVex=resultStack[resultTop--];
        p=adjList[inVex].firstEdge;
        while(p){
            outVex=p->adjvex;
            if(vl[inVex]>vl[outVex]-p->weight)
                vl[inVex]=vl[outVex]-p->weight;
            p=p->next;
        }
    }
    cout<<"vl数组的值为:"<<endl;
    for(int i=0;i<count;i++){
        cout<<"vl["<<i<<"]="<<vl[i]<<endl;
    }
    return true;
}


int main(){
    char vertex[MAX_VERTEX];
    int num,edge;

    cout << "请输入顶点个数和边的个数:";
    cin >> num >> edge;
    for(int i=0; i<num; i++)
        vertex[i] = i + '0';

    ALGraph graph(vertex,num,edge);
    graph.inputEdges();
    graph.displayData();

    if(!graph.CriticalPath()){
        cout << "这个图有回路,不能求关键路径。";
    }

    //记住,main函数调用结束后,会自动调用析构函数,对图的数据以及ve,vl数组进行释放。

    return 0;
}

输入:

9 11

0 1 6

0 2 4

0 3 5

1 4 1

2 4 1

3 5 2

4 6 9

4 7 7

5 7 4

6 8 2

7 8 4

输出:

输出图的存储情况:

顶点0的入度为:0,从这个顶点发出的的边为:

<0,3>5

<0,2>4

<0,1>6

顶点1的入度为:1,从这个顶点发出的的边为:

<1,4>1

顶点2的入度为:1,从这个顶点发出的的边为:

<2,4>1

顶点3的入度为:1,从这个顶点发出的的边为:

<3,5>2

顶点4的入度为:2,从这个顶点发出的的边为:

<4,7>7

<4,6>9

顶点5的入度为:1,从这个顶点发出的的边为:

<5,7>4

顶点6的入度为:1,从这个顶点发出的的边为:

<6,8>2

顶点7的入度为:2,从这个顶点发出的的边为:

<7,8>4

顶点8的入度为:2,从这个顶点发出的的边为:

没有。

拓扑排序的顶点处理顺序是:

0 1 2 4 6 3 5 7 8

ve数组的值为:

ve[0]=0

ve[1]=6

ve[2]=4

ve[3]=5

ve[4]=7

ve[5]=7

ve[6]=16

ve[7]=14

ve[8]=18

vl数组的值为:

vl[0]=0

vl[1]=6

vl[2]=6

vl[3]=8

vl[4]=7

vl[5]=10

vl[6]=16

vl[7]=14

vl[8]=18