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

 

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

在聊關(guān)鍵路徑之前，我們先看一個簡單的實例，如下圖所示。我們將下方這個有向無環(huán)圖看做是整個工程，將每個節(jié)點(diǎn)看做是該項目工程的一個子工程。子工程間又有一定的優(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?？倳r間為26。

從上面這個序列中我們顯然可以看出來這不是最優(yōu)的，因為A->B, A->C可以同時進(jìn)行，B->D和C->D也可以同時進(jìn)行。在允許某些子工程同時進(jìn)行的情