上篇博客我們介紹了AOV網(wǎng)的拓?fù)湫蛄?/span>，請參考《數(shù)據(jù)結(jié)構(gòu)(七) AOV網(wǎng)的拓?fù)渑判?Swift面向?qū)ο蟀?》。拓?fù)湫蛄兄邪?xiàng)目的每個(gè)結(jié)點(diǎn)，沿著拓?fù)湫蛄袑㈨?xiàng)目進(jìn)行下去是肯定可以將項(xiàng)目完成的，但是工期不是最優(yōu)的。因?yàn)橥負(fù)湫蛄惺且粋€(gè)串行序列，如果按照該序列執(zhí)行項(xiàng)目，那么就是串行執(zhí)行的。我們知道在一個(gè)項(xiàng)目中的一些子工程是可以并行來完成的，這也就類似我們的多線程。今天我們要解決的問題就是找出一個(gè)關(guān)鍵路徑，是工期最優(yōu)并保證工程的完成。什么是關(guān)鍵路徑，我們在下方會(huì)進(jìn)行詳細(xì)介紹。

 

一、關(guān)鍵路徑概述

在聊關(guān)鍵路徑之前，我們先看一個(gè)簡單的實(shí)例，如下圖所示。我們將下方這個(gè)有向無環(huán)圖看做是整個(gè)工程，將每個(gè)節(jié)點(diǎn)看做是該項(xiàng)目工程的一個(gè)子工程。子工程間又有一定的優(yōu)先級。在下方圖中，A的優(yōu)先級最高。A做完后，B、C才可以進(jìn)行開發(fā)。B、C完成后，我們才可以開發(fā)D。從下圖中我們不難看出，該圖的拓?fù)湫蛄袨锳, B, C, D。如果我們按照串行的方式來完成此工程的話，那么工程完成的順序可以是A-5->B, A-8->C, B-3->D, C-10->D。總時(shí)間為26。

從上面這個(gè)序列中我們顯然可以看出來這不是最優(yōu)的，因?yàn)?span style="color:#FF0000;">A->B, A->C可以同時(shí)進(jìn)行，B->D和C->D也可以同時(shí)進(jìn)行。在允許某些子工程同時(shí)進(jìn)行的情況下，A->B和A-C可以同時(shí)進(jìn)行，因?yàn)锳->B所需時(shí)間小于A->C所需時(shí)間，所以我們選擇A->C。在A->C執(zhí)行這8個(gè)小時(shí)的時(shí)間里，A->B和B->D已經(jīng)執(zhí)行完了，就剩下C->D了，所以關(guān)鍵工期為A->C->D=18。

在求關(guān)鍵路徑的算法中，我們先求出每個(gè)事件的最早完成時(shí)間。在事件最早完成的時(shí)間集合中，工程最后一步完成的時(shí)間就是我們工程完成的最優(yōu)時(shí)間。然后在工程時(shí)間最優(yōu)的情況下求出每個(gè)事件最晚完成時(shí)間。如果某個(gè)時(shí)間最早的完成時(shí)間與最晚的完成時(shí)間相同，那么該事件就是我們的關(guān)鍵事件，該事件就位于我們關(guān)鍵路徑中。如果這樣敘述有些抽象，那么我們就拿下方這個(gè)簡單圖來做個(gè)類比。

在上方這個(gè)有向無環(huán)圖中，我們可以求出每個(gè)事件最早發(fā)生的時(shí)間。下方截圖就是每個(gè)事件所對應(yīng)的最早完成的事件，因?yàn)镈是工程的尾結(jié)點(diǎn)，所以該工程完成的最早