AOE網與關鍵路徑
聲明：圖片及內容基於//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
