有向圖:

由定點(diǎn)和有向邊組成。

每個(gè)有向邊是一個(gè)形如(u,v)的有序?qū)Γ渲衭和v代表頂點(diǎn)。

當(dāng)一個(gè)有向圖包含一個(gè)有向邊(u,v)時(shí)，我們稱v臨接于u，并且(u,v)表示從u發(fā)出，且進(jìn)入v。

有向無環(huán)圖：不存在任何一個(gè)從某個(gè)頂點(diǎn)發(fā)出，經(jīng)過一條或者多條邊后，重新又回到出發(fā)點(diǎn)的路徑。

入度：進(jìn)入該頂點(diǎn)的邊的個(gè)數(shù)稱為該頂點(diǎn)的入度。（可以以任意一個(gè)入度為0的頂點(diǎn)作為起始頂點(diǎn)。）

出度：從該頂點(diǎn)發(fā)出的邊的個(gè)數(shù)。

任何一個(gè)有向無環(huán)圖中必定至少存在一個(gè)入度為0的頂點(diǎn)，至少存在一個(gè)出度為0的頂點(diǎn)，否則圖中必存在環(huán)。

有向無環(huán)圖對(duì)于構(gòu)造一個(gè)任務(wù)必須發(fā)生在另一個(gè)任務(wù)之前的這種依賴模型特別有效。有向無環(huán)圖的另一個(gè)應(yīng)用是規(guī)劃項(xiàng)目，例如建造房屋時(shí)，框架的設(shè)計(jì)必須在蓋屋頂之前。

如何表示有向圖？

在計(jì)算機(jī)中，可以用若干種方式來表示一個(gè)有向圖，若一個(gè)圖包含n個(gè)頂點(diǎn)，m條邊，同時(shí)假定每個(gè)頂點(diǎn)的編號(hào)是介于1～n的范圍之內(nèi)，則能將頂點(diǎn)看作是數(shù)組索引，或者甚至是看成是一個(gè)矩陣的行號(hào)或者列號(hào)。

A.如果僅僅想要知道存在哪些頂點(diǎn)和哪些邊，則使用一個(gè)n*n的鄰接矩陣來表示一個(gè)圖，其中每行和每列均對(duì)應(yīng)著一個(gè)頂點(diǎn)，并且頂點(diǎn)u所對(duì)應(yīng)的行和頂點(diǎn)v所對(duì)應(yīng)的列的交叉位置處，當(dāng)邊(u,v)存在時(shí)，該位置處為1，若圖中不包含邊(u,v),該交叉位置處為0。由于一個(gè)鄰接矩陣包含n^2個(gè)項(xiàng)，那么m<=n^2必定是成立的。

B.另一種表示方式是可以只保存一個(gè)具有m條邊的無序列表。將鄰接矩陣和無序列表結(jié)合起來就得到了一種新的圖的表示方式——鄰接表，即一個(gè)n元素?cái)?shù)組，索引是各個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)u所對(duì)應(yīng)的數(shù)組項(xiàng)是頂點(diǎn)u的所有鄰接頂點(diǎn)所組成的表。總而言之，鄰接表的所有頂點(diǎn)所對(duì)應(yīng)的數(shù)組項(xiàng)中共包含m個(gè)頂點(diǎn)

然而邊的無序列表和鄰接表會(huì)產(chǎn)生一個(gè)問題：如何表示一個(gè)表。表示一個(gè)表的最好方法取決于我們需要在表上完成什么類型的操作。

對(duì)于邊的無序列表和鄰接表，我們已經(jīng)提前知道了每個(gè)表中邊的個(gè)數(shù)，且表的內(nèi)容不會(huì)發(fā)生改變，因此我們能將每個(gè)表存儲(chǔ)在一個(gè)數(shù)組中。即使表的內(nèi)容會(huì)隨著時(shí)間的變化而發(fā)生改變，只要我們知道在任意時(shí)刻一個(gè)表中所包含的最大個(gè)數(shù)，我們也可以使用數(shù)組來存儲(chǔ)該表。如果不需要在表的內(nèi)部插入新項(xiàng)或者刪除項(xiàng)，那么使用數(shù)組來表示表的效率和其他方式一樣高。

如果確實(shí)需要在表中插入新項(xiàng)，那么我們可以使用鏈表，鏈表中的每項(xiàng)君包含它的后繼位置，如果需要在表內(nèi)刪除元素，那么鏈表也應(yīng)該包括該項(xiàng)的前驅(qū)位置，以便我們能迅速地建立新的次序關(guān)系。

單向鏈表：僅僅包括后繼鏈的鏈表

雙向鏈表：不僅包括后繼鏈，還包含前驅(qū)鏈的鏈表

拓?fù)渑判颍?/p>

一個(gè)有向無環(huán)圖的拓?fù)渑判蛐枰a(chǎn)生一個(gè)線性序列：如果(u,v)是有向無環(huán)圖的一條邊，那么在線性序列匯中，u必須出現(xiàn)在v之前。

程序 TOPOLLOGICAL-SORT(G)

輸入 G：一個(gè)頂點(diǎn)編號(hào)為從1～n的有向無環(huán)圖

輸出 關(guān)于頂點(diǎn)的一個(gè)線性序列（例如：如果(u,v)是圖上的一條邊，那么在線性序列中，u就出現(xiàn)在v之前）

步驟

1.令in-degree[1......n]為一個(gè)新數(shù)組，創(chuàng)建一個(gè)空的關(guān)于頂點(diǎn)的線性序列。

2.令in-degree數(shù)組中的每個(gè)元素均為0。

3.對(duì)于每個(gè)頂點(diǎn)u:

A.對(duì)于每個(gè)與頂點(diǎn)u相鄰接的頂點(diǎn)v:

i.增加in-degree[v]的值。

4.創(chuàng)建一個(gè)列表next,用以存放所有滿足in-degree[u]=0的頂點(diǎn)u。

5.只要next列表不為空，執(zhí)行如下操作：

A.從next列表中刪除一個(gè)頂點(diǎn)（將該頂點(diǎn)稱為頂點(diǎn)u）。

B.將u添加到線性序列的末尾處。

C.對(duì)于每個(gè)與u相鄰接的頂點(diǎn)v:

i.令in-degree[v]的值自減一。

ii.如果in-degree[v]=0，將頂點(diǎn)v添加到next列表中。

6.返回線性序列。

拓?fù)渑判虺绦蛑袃H僅記錄了每個(gè)頂點(diǎn)的入度，并將理論上移除的邊所指向的頂點(diǎn)的入度減一。由于數(shù)組索引是整數(shù)，現(xiàn)假定每個(gè)頂點(diǎn)均由一個(gè)介于1～n范圍內(nèi)的一個(gè)確定的整數(shù)表示。因?yàn)樵摮绦蛐枰焖俚卮_定入度為0的頂點(diǎn)，它將每隔頂點(diǎn)的入讀存儲(chǔ)在數(shù)組in-degree中，并且將所有入度為0的頂點(diǎn)存儲(chǔ)在列表next中。第1～3步初始化in-degree數(shù)組，第4步初始化next列表，且當(dāng)頂點(diǎn)和邊在概念上被移除時(shí)，第5步負(fù)責(zé)更新in-degree數(shù)組和next列表。該程序能選擇next列表中的任何一個(gè)頂點(diǎn)作為線性序列的下一個(gè)元素。

拓?fù)渑判虻倪\(yùn)行時(shí)間：

假定有向無環(huán)圖使用鄰接表表示并且next表是一個(gè)鏈表，那么可證TOPOLOGICAL-SOFT程序所花費(fèi)的時(shí)間是?(n+m)。

PERT圖表中的關(guān)鍵路徑：

<PERT："PRogram evaluation and review technique"，即令多個(gè)任務(wù)盡可能地同時(shí)執(zhí)行，完成整個(gè)工作的時(shí)間被稱為PERT圖表的“關(guān)鍵路徑”>

<路徑：指一個(gè)頂點(diǎn)和邊構(gòu)成的序列，該序列允許從一個(gè)頂點(diǎn)到達(dá)另一個(gè)頂點(diǎn)（允許從一個(gè)頂點(diǎn)到達(dá)它本身）的邊的序列>

<環(huán)：一條從一個(gè)頂點(diǎn)出發(fā)，最后又能回歸原頂點(diǎn)的路徑>

<權(quán)：用來表示和邊相關(guān)聯(lián)的一個(gè)通用術(shù)語。一個(gè)邊上帶有權(quán)重的有向圖稱為加權(quán)有向圖>

<一條路徑的權(quán)重：表示路徑上所有邊的權(quán)重之和>

<最短路徑：表示從頂點(diǎn)u到頂點(diǎn)v的所有路徑中的邊的權(quán)重和最小的路徑，最短路徑并不一定是唯一的，因?yàn)橐粋€(gè)有向圖中從頂點(diǎn)u到頂點(diǎn)v可能存在多條最短路徑>

一個(gè)PERT圖表中的一條關(guān)鍵路徑是指所有路徑中完成任務(wù)所花費(fèi)時(shí)間總和最大的路徑。沿著一條關(guān)鍵路徑完成任務(wù)所花費(fèi)的時(shí)間給出了無論多少個(gè)任務(wù)被同時(shí)執(zhí)行，完成整個(gè)工作所需要花費(fèi)的最少可能時(shí)間。

為了將任務(wù)時(shí)間取反的PERT圖表轉(zhuǎn)化為一個(gè)加權(quán)有向圖，將每個(gè)頂點(diǎn)上的取反的任務(wù)時(shí)間轉(zhuǎn)化為所有指向它的邊上的任務(wù)時(shí)間。也就是說，如果頂點(diǎn)v有一個(gè)（非-取反的）任務(wù)時(shí)間t,那么將每個(gè)滿足(u,v)的邊，即指向v的邊均設(shè)置為-t。

//在得出關(guān)鍵路徑之前，需要先學(xué)會(huì)求最短路徑。

有向無環(huán)圖中的最短路徑：

我們假定有向無環(huán)圖被存儲(chǔ)在一個(gè)鄰接表中，并且將于邊(u,v)關(guān)聯(lián)的權(quán)重存儲(chǔ)為weight(u,v)。

在一個(gè)由PERT圖表所衍生出來的有向無環(huán)圖中，想要尋找一條從源點(diǎn)到匯點(diǎn)的最短路徑（將源點(diǎn)稱為start，將匯點(diǎn)稱為finish）

將源點(diǎn)命名為s，并且計(jì)算出關(guān)于每個(gè)頂點(diǎn)的兩個(gè)值。首先，從源點(diǎn)s到頂點(diǎn)v的最短路徑，用sp(s,v)表示，接著從源點(diǎn)s到頂點(diǎn)v的最短路徑中的頂點(diǎn)v的前驅(qū)：頂點(diǎn)v的前驅(qū)是滿足以下條件的頂點(diǎn)u:從源點(diǎn)s到頂點(diǎn)v的最短路徑等于從源點(diǎn)s到頂點(diǎn)u的最短路徑再加上邊(u,v)的權(quán)重。我們對(duì)n個(gè)頂點(diǎn)從1到n進(jìn)行編號(hào)，以方便執(zhí)行最短路徑算法。

將最短路徑算法的結(jié)果分別存儲(chǔ)在數(shù)組shortest[1......n]和數(shù)組pred[1......n]中。（運(yùn)行過程中兩個(gè)數(shù)組中的值可能不是最終的正確值，可是當(dāng)算法執(zhí)行完畢之后，兩個(gè)數(shù)組存儲(chǔ)的結(jié)果就是正確的值）

我們需要處理所產(chǎn)生的幾個(gè)問題。

1.要是從頂點(diǎn)s到頂點(diǎn)v不存在路徑呢？

那么我們就設(shè)sp(s,v)=∞，則shortest[v]結(jié)果應(yīng)該是∞。因?yàn)轫旤c(diǎn)v在從源點(diǎn)s出發(fā)的最短路徑上不存在前驅(qū)，所以pred[v]應(yīng)該為NULL。而頂點(diǎn)s也沒有前驅(qū)，所以稱pred[s]也應(yīng)該為NULL。

2.圖中可能存在環(huán)，同時(shí)也存在帶負(fù)權(quán)重的邊，要是存在一個(gè)權(quán)重和為負(fù)的環(huán)呢？

那么我們可以循環(huán)地?zé)o窮次在該環(huán)上執(zhí)行操作，每循環(huán)一次就會(huì)使得路徑上的權(quán)重降低一些。然而，我們僅僅關(guān)心無環(huán)圖，所以圖中不會(huì)存在環(huán)路，我們也無需擔(dān)心權(quán)重和為負(fù)的環(huán)了。

為了計(jì)算從源點(diǎn)s出發(fā)的最短路徑，我們以shortest[s]=0開始計(jì)算，對(duì)于所有其他頂點(diǎn)v，shortest[v]=∞（因?yàn)槲覀兲崆安⒉恢缽捻旤c(diǎn)s出發(fā)時(shí)，我們能夠到達(dá)哪個(gè)頂點(diǎn)），并且對(duì)于所有的頂點(diǎn)v，均有pred[v]=NULL成立。隨后我們對(duì)圖上的邊應(yīng)用一系列的松弛步驟：

程序 RELAX（u,v）

輸入 u,v：邊（u,v）的頂點(diǎn)u,v。

結(jié)果 shortest[v]的值可能會(huì)減小，如果它確實(shí)會(huì)減小，那么令pred[v]取u。

步驟

1.如果shortest[u]+weight(u,v)<shortest[v]，那么將shortest[v]賦值為shortest[u]+weight(u,v)，將pred[v]賦值為u。

當(dāng)調(diào)用RELAX（u,v）時(shí)，我們判定能否通過將(u,v)作為最后一條邊來改進(jìn)從源點(diǎn)s到頂點(diǎn)v的最短路徑。

如果沿著最短路徑按序?qū)Ω鱾€(gè)邊執(zhí)行松弛操作，我們會(huì)得到正確的結(jié)果。（可是，當(dāng)我們甚至都還不知道哪條路徑是最短路徑的時(shí)候，如何能做到沿著最短路徑按序?qū)Ω鱾€(gè)邊執(zhí)行松弛操作呢？A：對(duì)于一個(gè)有向無環(huán)圖來說，操作很簡(jiǎn)單，我們對(duì)有向無環(huán)圖中的所有邊進(jìn)行松弛操作，并且當(dāng)我們對(duì)于所有邊執(zhí)行松弛操作時(shí)，每條最短路徑上的邊也都按序被執(zhí)行了松弛操作。）

下面是關(guān)于如何沿著最短路徑上的邊進(jìn)行松弛操作的更精準(zhǔn)的描述，并且它適用于任何有向圖（無論是否存在環(huán)）：

對(duì)于除源點(diǎn)之外的所有頂點(diǎn)，shortest[u]=∞，對(duì)于所有頂點(diǎn)pred[u]=NULL，而對(duì)于源點(diǎn)s,shortest[s]=0。

隨后對(duì)從源點(diǎn)s到任何頂點(diǎn)v的最短路徑上的邊執(zhí)行松弛操作（以從源點(diǎn)s出發(fā)的邊開始，并且一直到進(jìn)入頂點(diǎn)v的邊結(jié)束）。對(duì)于其他邊的松弛操作可能會(huì)大量地穿插在沿著這個(gè)最短路徑進(jìn)行松弛操作的過程中，但是只有松弛操作才可能會(huì)改變shortest或者pred的值。

當(dāng)對(duì)邊執(zhí)行松弛操作后，頂點(diǎn)v的shortest值和pred值是正確的：shortest[v]=sp(u,v)，且pred[v]是位于從源點(diǎn)s出發(fā)的最短路徑上的頂點(diǎn)v的前驅(qū)。

由上，我們可以沿著每條最短路徑按序精確地對(duì)每條邊執(zhí)行松弛操作。

首先，利用拓?fù)渑判驅(qū)τ邢驘o環(huán)圖進(jìn)行排序。

隨后，對(duì)于按照拓?fù)渑判蚝笏玫降木€性序列中的每個(gè)頂點(diǎn)，依序?qū)拿總€(gè)頂點(diǎn)出發(fā)的所有邊執(zhí)行松弛操作。

由于每條邊必定是從線性序列中的排列在較前側(cè)的頂點(diǎn)出發(fā)，然后進(jìn)入到線性序列中排列在后面的頂點(diǎn)，因此有向無環(huán)圖中的每個(gè)路徑一定會(huì)以一種與線性序列相一致的順序來訪問各個(gè)頂點(diǎn)。

程序 DAG-SHORTEST-PATHS（G，s）

輸入 G：一個(gè)加權(quán)有向無環(huán)圖（包含具有n個(gè)頂點(diǎn)的集合V，m條有向邊的集合E）

s：集合V中的一個(gè)源點(diǎn)

結(jié)果 對(duì)于集合V中的每個(gè)非源頂點(diǎn)v,shortest[v]表示從s 到v的一條最短路徑的權(quán)重和sp(s,v),pred[v]表示在這條最短路徑上出現(xiàn)在頂點(diǎn)v之前的頂點(diǎn)。對(duì)于源點(diǎn)s，shortest[s]=0,pred[s]=NULL。如果從s到v沒有路徑，那么shortest[v]為∞，pred[v]=NULL。

步驟

1.調(diào)用TOPOLOGICAL-SORT（G），L被賦值為由TOPOLOGICAL-SORT（G）調(diào)用所返回的頂點(diǎn)的線性序列。

2.對(duì)于除了頂點(diǎn)s之外的任一頂點(diǎn)v，shortest[v]均被賦值為∞，將shortest[s]賦值為0，對(duì)于每個(gè)頂點(diǎn)v，將pred[v]賦值為NULL。

3.按照線性序列L的排序，依次取線性序列L中的頂點(diǎn)為u：

A.對(duì)于每個(gè)與頂點(diǎn)u相鄰接的頂點(diǎn)v：

i.調(diào)用RELAX（u,v)。