上篇博客我們介紹了AOV網(wǎng)的拓?fù)湫蛄?/span>，請(qǐng)參考《數(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)目中的一些子工程是可以并行來(lái)完成的，這也就類似我們的多線程。今天我們要解決的問(wèn)題就是找出一個(gè)關(guān)鍵路徑，是工期最優(yōu)并保證工程的完成。什么是關(guān)鍵路徑，我們?cè)谙路綍?huì)進(jìn)行詳細(xì)介紹。
一、關(guān)鍵路徑概述
在聊關(guān)鍵路徑之前，我們先看一個(gè)簡(jiǎn)單的實(shí)例，如下圖所示。我們將下方這個(gè)有向無(wú)環(huán)圖看做是整個(gè)工程，將每個(gè)節(jié)點(diǎn)看做是該項(xiàng)目工程的一個(gè)子工程。子工程間又有一定的優(yōu)先級(jí)。在下方圖中，A的優(yōu)先級(jí)最高。A做完后，B、C才可以進(jìn)行開(kāi)發(fā)。B、C完成后，我們才可以開(kāi)發(fā)D。從下圖中我們不難看出，該圖的拓?fù)湫蛄袨锳, B, C, D。如果我們按照串行的方式來(lái)完成此工程的話，那么工程完成的順序可以是A-5->B, A-8->C, B-3->D, C-10->D?？倳r(shí)間為26。
從上面這個(gè)序列中我們顯然可以看出來(lái)這不是最優(yōu)的，因?yàn)?span style="margin: 0px; padding: 0px; color: rgb(255, 0, 0);">A->B, A->C可以同時(shí)進(jìn)行，B->D和C->D也可以同時(shí)進(jìn)行。在允許某些子工程同時(shí)進(jìn)行的情
