前言

數(shù)據(jù)結(jié)構(gòu)，一門數(shù)據(jù)處理的藝術(shù)，精巧的結(jié)構(gòu)在一個(gè)又一個(gè)算法下發(fā)揮著他們無與倫比的高效和精密之美，在為信息技術(shù)打下堅(jiān)實(shí)地基的同時(shí)，也令無數(shù)開發(fā)者和探索者為之著迷。

也因如此，它作為博主大二上學(xué)期最重要的必修課出現(xiàn)了。由于大家對于上學(xué)期C++系列博文的支持，我打算將這門課的筆記也寫作系列博文，既用于整理、消化，也用于同各位交流、展示數(shù)據(jù)結(jié)構(gòu)的美。

此系列文章，將會(huì)分成兩條主線，一條“數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)”，一條“數(shù)據(jù)結(jié)構(gòu)拓展”。“數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)”主要以記錄課上內(nèi)容為主，“拓展”則是以課上內(nèi)容為基礎(chǔ)的更加高深的數(shù)據(jù)結(jié)構(gòu)或相關(guān)應(yīng)用知識。

歡迎關(guān)注博主，一起交流、學(xué)習(xí)、進(jìn)步，往期的文章將會(huì)放在文末。

---

話說在前面的章節(jié)，我們介紹了一種工程上常用的AOV網(wǎng)絡(luò)，他可以清晰的表示工程中每項(xiàng)活動(dòng)的先后順序，并計(jì)算出滿足要求的活動(dòng)規(guī)劃，也就是拓?fù)渑判颉?/p>

這一節(jié)，我們將繼續(xù)研究這類網(wǎng)絡(luò)。

AOE網(wǎng)絡(luò)

在一般工程項(xiàng)目中，我們不僅會(huì)關(guān)心每項(xiàng)活動(dòng)的先后次序，更會(huì)關(guān)心活動(dòng)之間更加嚴(yán)格的時(shí)間約束關(guān)系。

不妨改造AOV網(wǎng)絡(luò)的有向無環(huán)圖，在此基礎(chǔ)上引入邊權(quán)，使其成為有向有權(quán)無環(huán)圖。

以一條有向邊代替一個(gè)活動(dòng)，邊權(quán)為其進(jìn)行的時(shí)間長度，邊的起點(diǎn)表示該任務(wù)的開始，終點(diǎn)表示該任務(wù)的完成。從點(diǎn)的角度來看，出邊表示一個(gè)活動(dòng)開始的狀態(tài)，也稱為一個(gè)事件，入邊表示一個(gè)任務(wù)的完成。

這樣的圖被稱作AOE網(wǎng)絡(luò)($ActivityOnEdgeNetwork$)。如果比較他和AOV網(wǎng)絡(luò)的名稱，不難發(fā)現(xiàn)他將關(guān)注的重點(diǎn)從頂點(diǎn)變成了邊，這也將是兩個(gè)網(wǎng)絡(luò)處理問題和算法不同之處的來源。

在工程中由于一般只有一個(gè)起始點(diǎn)和一個(gè)完成點(diǎn)，所以在正常的情況下，一張AOE網(wǎng)絡(luò)中也只有一個(gè)源點(diǎn)和匯點(diǎn)。其中源點(diǎn)入度為0，匯點(diǎn)出度為0。如下圖：

在AOE網(wǎng)絡(luò)中，我們關(guān)心的問題不在僅僅是任務(wù)進(jìn)行的先后順序，更包括了每個(gè)任務(wù)乃至整個(gè)工程項(xiàng)目的計(jì)劃完成時(shí)間。一般來說，一些活動(dòng)能夠同時(shí)開工，他們會(huì)從同一頂點(diǎn)出發(fā)。有些狀態(tài)必須等到若干前置工作的完成，這些任務(wù)會(huì)匯集到一個(gè)頂點(diǎn)處。

畫出工程對應(yīng)的AOE網(wǎng)絡(luò)可以使我們得出：

• 完成整個(gè)工程至少需要多少時(shí)間
• 為縮短完成工程所需要的時(shí)間，應(yīng)當(dāng)加快那些活動(dòng)
• 為了不延誤整個(gè)工程，哪些活動(dòng)不得延期，那些活動(dòng)可以適當(dāng)延期

關(guān)鍵路徑

根據(jù)上文的敘述，不難發(fā)現(xiàn)整個(gè)工程完成的最短時(shí)間，取決于從源點(diǎn)到匯點(diǎn)的最長路徑的長度。我們將這個(gè)路徑定義為該網(wǎng)絡(luò)的關(guān)鍵路徑。上文圖中的關(guān)鍵路徑就如下所示：

在關(guān)鍵路徑中的任何一環(huán)不能按時(shí)完成，就會(huì)延誤整個(gè)項(xiàng)目的進(jìn)度。如在上圖中，標(biāo)紅的路徑中任意一條路徑的長度增加都會(huì)使得源點(diǎn)到匯點(diǎn)的最長路徑增加。而增加其他邊則不一定。

需要注意的是，關(guān)鍵路徑也有可能存在多條，定義中并沒有限制一張AOE網(wǎng)絡(luò)只能有一條關(guān)鍵路徑。如將上圖中的權(quán)值稍作修改，就會(huì)出現(xiàn)多條關(guān)鍵路徑：

在關(guān)鍵路徑上所有的活動(dòng)都是關(guān)鍵活動(dòng)。（需要注意的是在AOE網(wǎng)絡(luò)中，活動(dòng)是邊而不是頂點(diǎn)）

多條關(guān)鍵路徑的來源往往就在于一些狀態(tài)之間可能存在著不同的活動(dòng)路徑，他們的時(shí)間加和相同（就像上圖中的狀態(tài)15之間存在兩條路徑）。而不同的路徑在經(jīng)過相同的頂點(diǎn)時(shí)遵循著乘法原理（上圖為$1\times 2$）

算法設(shè)計(jì)

有了對關(guān)鍵路徑的定義和分析，下面的重點(diǎn)就是如何從AOE網(wǎng)絡(luò)中尋找關(guān)鍵路徑。

這里介紹一種基于拓?fù)渑判虻乃惴ㄋ悸?#xff1a;

將源點(diǎn)加入隊(duì)列，所有頂點(diǎn)默認(rèn)最長距離為0

每次出隊(duì)隊(duì)首頂點(diǎn)，使用該頂點(diǎn)更新出邊終點(diǎn)。若經(jīng)過該邊到達(dá)彼點(diǎn)的累計(jì)路徑長度大于原有頂點(diǎn)距離，更新最長距離并記錄當(dāng)前頂點(diǎn)為其前驅(qū)

將該頂點(diǎn)“刪除”（所有出邊終點(diǎn)入度-1），如果有頂點(diǎn)入度為0，則加入隊(duì)列

重復(fù)23過程，直至隊(duì)列為空

該算法基于拓?fù)渑判蛩惴?#xff0c;改進(jìn)也并不大，只是在記錄頂點(diǎn)的入度和出度之余多記錄了源點(diǎn)到他的最長路徑。

代碼實(shí)現(xiàn)

路徑長度

與關(guān)鍵路徑相關(guān)的需求有很多，不妨先擬定一個(gè)需求，僅求出關(guān)鍵路徑的長度：

給定一張有向有權(quán)無環(huán)的AOE網(wǎng)絡(luò)，求出其源點(diǎn)到匯點(diǎn)的關(guān)鍵路徑長度
輸入格式：
第一行包含兩個(gè)整數(shù)n,m，表示頂點(diǎn)的個(gè)數(shù)和邊的條數(shù)
接下來m行，每行3個(gè)整數(shù)表示每條邊的起點(diǎn)，終點(diǎn)和權(quán)值

存儲(chǔ)格式采用鄰接表，頂點(diǎn)信息定義如下：

struct Edge{int vertex;Edge * next;int len;Edge(int vertex,Edge * next){this->vertex = vertex;this->next = next;this->len = len;} }; Edge *head[N];//邊鏈表頭結(jié)點(diǎn)數(shù)組 int id[N];//入度 int od[N];//出度 int dis[N];//頂點(diǎn)到源點(diǎn)的最長距離

代碼實(shí)現(xiàn)如下：

void link(int x,int y,int len){Edge * edge = new Edge(y,head[x],len);head[x] = edge; } int queue[N];//隊(duì)列 int main(){int n,m;cin >> n >> m;for(int i = 0,x,y,len;i < m;i++){//讀入邊cin >> x >>y >>len;od[x]++;id[y]++;link(x,y,len);}int l = 1,r = 0;//隊(duì)列左右下標(biāo)for(int i = 1;i <= n;i++){if(id[i] == 0){//入度為0的頂點(diǎn)入隊(duì)queue[++r] = i;}}int k;while(l <= r){//遍歷隊(duì)列，直至為空k = queue[l++];for(Edge * edge = head[k];edge != NULL;edge = edge->next){id[edge->vertex]--;//刪除邊if(id[edge->vertex] == 0){//如果后繼節(jié)點(diǎn)入度為0，該節(jié)點(diǎn)入隊(duì)queue[++r] = edge->vertex;}if(dis[edge->vertex] < dis[k] + edge->len){//使用當(dāng)前頂點(diǎn)更新相連頂點(diǎn)的最長距離dis[edge->vertex] = dis[k] + edge->len;}}}cout << dis[queue[r]] << endl;//匯點(diǎn)一定在隊(duì)列的最后，想想這是為什么？ }

編譯執(zhí)行程序，輸入上面的示例圖：

打印路徑

一個(gè)程序能找出關(guān)鍵路徑長度往往是不夠的，我們還需要得出關(guān)鍵路徑上的關(guān)鍵活動(dòng)。

那么如果題目需求輸出一條關(guān)鍵路徑應(yīng)該怎么處理呢？

這個(gè)問題其實(shí)很好解決，我們在記錄每條邊的距離源點(diǎn)的最遠(yuǎn)距離的同時(shí)記錄其最遠(yuǎn)路徑上的前驅(qū)。完成算法后從匯點(diǎn)開始，便可以順藤摸瓜的找到一條從源點(diǎn)到匯點(diǎn)的關(guān)鍵路徑上的全部頂點(diǎn)。

下面讓我們來修改上面擬定的需求：

給定一張有向有權(quán)無環(huán)的AOE網(wǎng)絡(luò)，求出其源點(diǎn)到匯點(diǎn)的關(guān)鍵路徑長度，并輸出任意一條關(guān)鍵路徑
輸入格式：
第一行包含兩個(gè)整數(shù)n,m，表示頂點(diǎn)的個(gè)數(shù)和邊的條數(shù)
接下來m行，每行3個(gè)整數(shù)表示每條邊的起點(diǎn)，終點(diǎn)和權(quán)值

圖的存儲(chǔ)結(jié)構(gòu)與上文相同，現(xiàn)需要額外定義一個(gè)最長路徑的前驅(qū)頂點(diǎn)數(shù)組：

int pre[N];//到達(dá)該頂點(diǎn)的最長路徑上的前驅(qū)結(jié)點(diǎn)

算法代碼實(shí)現(xiàn)如下：

void print(int k){//遞歸打印一條路徑,由于頂點(diǎn)編號從1開始，所以值為0表示沒有前驅(qū)if(k == 0){return;}print(pre[k]);cout << k << " "; } void link(int x,int y,int len){Edge * edge = new Edge(y,head[x],len);head[x] = edge; } int queue[N];//隊(duì)列 int main(){int n,m;cin >> n >> m;for(int i = 0,x,y,len;i < m;i++){//讀入邊cin >> x >>y >>len;od[x]++;id[y]++;link(x,y,len);}int l = 1,r = 0;//隊(duì)列的左右下標(biāo)for(int i = 1;i <= n;i++){if(id[i] == 0){//入度為0的頂點(diǎn)入隊(duì)queue[++r] = i;}}int k;while(l <= r){//循環(huán)遍歷隊(duì)列中的頂點(diǎn)直至隊(duì)列為空k = queue[l++];for(Edge * edge = head[k];edge != NULL;edge = edge->next){id[edge->vertex]--;//刪除該邊if(id[edge->vertex] == 0){//如果后繼節(jié)點(diǎn)入度為0，后繼節(jié)點(diǎn)入隊(duì)queue[++r] = edge->vertex;}if(dis[edge->vertex] < dis[k] + edge->len){//使用當(dāng)前結(jié)點(diǎn)更新后繼節(jié)點(diǎn)最長路徑值和前驅(qū)dis[edge->vertex] = dis[k] + edge->len;pre[edge->vertex] = k;}}}cout << dis[queue[r]] << endl;//匯點(diǎn)一定在隊(duì)列的末尾，想想這是為什么？print(queue[r]);//打印源點(diǎn)到匯點(diǎn)的路徑 }

再執(zhí)行上述代碼：

打印所有路徑

當(dāng)然，能打印一條路徑可能還不夠過癮。

那么如果需要我們打印所有路徑應(yīng)該怎么辦呢？

辦法總是有的，就是得多掉幾根頭發(fā)
——哲茨海氏沃茨基碩德

關(guān)鍵路徑不唯一，上面方法不能夠打印所有的原因在于一個(gè)頂點(diǎn)可能是多條關(guān)鍵路徑的交匯頂點(diǎn)。換句話說，就是一個(gè)頂點(diǎn)可能有多個(gè)前驅(qū)，而前驅(qū)數(shù)組只能記錄其中的一個(gè)。

其實(shí)本來源點(diǎn)到匯點(diǎn)的關(guān)鍵路徑就不像是前驅(qū)鏈表表示的那樣是一條鏈，更像是一張圖。

所以問題的關(guān)鍵就在于如何能找到一個(gè)頂點(diǎn)的所有的前驅(qū)。

方法其實(shí)也很簡單，對于一個(gè)頂點(diǎn)$k$來說，只要枚舉所有指向它的頂點(diǎn)$i$，并從中選出所有滿足dis[k] = dis[i] + len[i][k]的頂點(diǎn)，他們就是$k$的前驅(qū)。

對于上圖來說，

8號頂點(diǎn)的前驅(qū)中只有5號滿足dis[8] = dis[5] + 8

而5號頂點(diǎn)的兩個(gè)前驅(qū)2和3都分別滿足dis[5] = dis[2] + 1和dis[5] = dis[3] + 3

所以只要根據(jù)這個(gè)方式，就可以找到一個(gè)頂點(diǎn)在關(guān)鍵路徑中的所有前驅(qū)，并依次進(jìn)行遞歸。

什么？你問我怎么找一個(gè)頂點(diǎn)的前驅(qū)？我們的邊都是有向邊，只能向后找不能向前找？

不過也不是沒有解決辦法，我們可以將所有的邊都存儲(chǔ)一個(gè)反向的邊，并且在邊結(jié)點(diǎn)中加上一個(gè)字段標(biāo)記正邊還是反邊。在拓?fù)渑判蜻^程中只用正邊，獲取路徑的過程中只用反邊就好啦~

為此，我們需要修改鄰接表結(jié)點(diǎn)的定義：

struct Edge{int vertex;Edge * next;int len;bool dir;//true代表正向，false代表反向Edge(int vertex,Edge * next,int len,bool dir){this->vertex = vertex;this->next = next;this->len = len;this->dir = dir;} }; Edge * head[N];//邊鏈表頭結(jié)點(diǎn)數(shù)組 int path[N];//遞歸打印路徑輔助數(shù)組 void print(int k,int cnt){//遞歸打印所有路徑path[cnt] = k;if(dis[k] == 0){//如果該頂點(diǎn)為源點(diǎn)，打印路徑for(int i = cnt;i > 0;i--){cout << path[i] << " ";}cout << endl;return;}for(Edge * edge = head[k];edge != NULL;edge = edge->next){//遍歷所有反邊，找到關(guān)鍵路徑上的前驅(qū)if(edge->dir){continue;}if(dis[k] == dis[edge->vertex] + edge->len){//找到關(guān)鍵路徑上的前驅(qū)并遞歸打印print(edge->vertex,cnt + 1);}} } void link(int x,int y,int len,bool dir){Edge * edge = new Edge(y,head[x],len,dir);head[x] = edge; } int queue[N];//隊(duì)列 int main(){int n,m;cin >> n >> m;for(int i = 0,x,y,len;i < m;i++){//讀入邊cin >> x >>y >>len;od[x]++;id[y]++;//正反邊都要建link(x,y,len,true);link(y,x,len,false);}int l = 1,r = 0;//隊(duì)列的左右下標(biāo)for(int i = 1;i <= n;i++){if(id[i] == 0){//入度為0的頂點(diǎn)入隊(duì)queue[++r] = i;}}int k;while(l <= r){//循環(huán)遍歷隊(duì)列中的頂點(diǎn)直至隊(duì)列為空k = queue[l++];for(Edge * edge = head[k];edge != NULL;edge = edge->next){if(edge->dir == false){continue;}id[edge->vertex]--;//刪除該邊if(id[edge->vertex] == 0){//如果后繼節(jié)點(diǎn)入度為0，后繼節(jié)點(diǎn)入隊(duì)queue[++r] = edge->vertex;}if(dis[edge->vertex] < dis[k] + edge->len){//使用當(dāng)前結(jié)點(diǎn)更新后繼節(jié)點(diǎn)最長路徑值和前驅(qū)dis[edge->vertex] = dis[k] + edge->len;}}}cout << dis[queue[r]] << endl;//匯點(diǎn)一定在隊(duì)列的末尾，想想這是為什么？print(queue[r],1);//打印源點(diǎn)到匯點(diǎn)的路徑 }

執(zhí)行示例，發(fā)現(xiàn)兩條關(guān)鍵路徑：

---

往期博客

• 【數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)概念
• 【數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】線性數(shù)據(jù)結(jié)構(gòu)——線性表概念 及 數(shù)組的封裝
• 【數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】線性數(shù)據(jù)結(jié)構(gòu)——三種鏈表的總結(jié)及封裝
• 【數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】線性數(shù)據(jù)結(jié)構(gòu)——棧和隊(duì)列的總結(jié)及封裝(C和java)
• 【算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】模式匹配問題與KMP算法
• 【數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)】二叉樹與其遍歷序列的互化 附代碼實(shí)現(xiàn)（C和java）
• 【數(shù)據(jù)結(jié)構(gòu)與算法拓展】 單調(diào)隊(duì)列原理及代碼實(shí)現(xiàn)
• 【數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】圖的存儲(chǔ)結(jié)構(gòu)
• 【數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)】并查集原理、封裝實(shí)現(xiàn)及例題解析（C和java）
• 【數(shù)據(jù)結(jié)構(gòu)與算法拓展】二叉堆原理、實(shí)現(xiàn)與例題（C和java）
• 【數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)】哈夫曼樹與哈夫曼編碼(C++)
• 【數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)】最短路徑問題
• 【數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)】堆排序原理及實(shí)現(xiàn)
• 【數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)】最小生成樹算法原理及實(shí)現(xiàn)
• 【數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】圖的遍歷方法與應(yīng)用
• 【數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】矩陣的存儲(chǔ)結(jié)構(gòu)，數(shù)組，三元組表及十字鏈表
• 【數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)】拓?fù)渑判蚺cAOV網(wǎng)絡(luò)

---

參考資料：

• 《數(shù)據(jù)結(jié)構(gòu)》（劉大有，楊博等編著）
• 《算法導(dǎo)論》（托馬斯·科爾曼等編著）
• OI WiKi

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法基础】AOE网络与关键路径的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。