AOE網與關鍵路徑
宣告：圖片及內容基於 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
「其他文章」
- 記一次批量更新整型型別的列 → 探究 UPDATE 的使用細節
- 編碼中的Adapter，不僅是一種設計模式，更是一種架構理念與解決方案
- 執行緒池底層原理詳解與原始碼分析
- 30分鐘掌握 Webpack
- 線性迴歸大結局(嶺(Ridge)、 Lasso迴歸原理、公式推導)，你想要的這裡都有
- Django 之路由層
- 【前端必會】webpack loader 到底是什麼
- day42-反射01
- 中心化決議管理——雲端分析
- HashMap底層原理及jdk1.8原始碼解讀
- 詳解JS中 call 方法的實現
- 列印 Logger 日誌時，需不需要再封裝一下工具類？
- 初識設計模式 - 代理模式
- 設計模式---享元模式
- 密碼學奇妙之旅、01 CFB密文反饋模式、AES標準、Golang程式碼
- [ML從入門到入門] 支援向量機：從SVM的推導過程到SMO的收斂性討論
- 從應用訪問Pod元資料-DownwardApi的應用
- Springboot之 Mybatis 多資料來源實現
- Java 泛型程式設計
- CAS核心思想、底層實現