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