有向圖:

由定點和有向邊組成。

每個有向邊是一個形如(u,v)的有序對，其中u和v代表頂點。

當一個有向圖包含一個有向邊(u,v)時，我們稱v臨接于u，并且(u,v)表示從u發出，且進入v。

有向無環圖：不存在任何一個從某個頂點發出，經過一條或者多條邊后，重新又回到出發點的路徑。

入度：進入該頂點的邊的個數稱為該頂點的入度。（可以以任意一個入度為0的頂點作為起始頂點。）

出度：從該頂點發出的邊的個數。

任何一個有向無環圖中必定至少存在一個入度為0的頂點，至少存在一個出度為0的頂點，否則圖中必存在環。

有向無環圖對于構造一個任務必須發生在另一個任務之前的這種依賴模型特別有效。有向無環圖的另一個應用是規劃項目，例如建造房屋時，框架的設計必須在蓋屋頂之前。

如何表示有向圖？

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

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

B.另一種表示方式是可以只保存一個具有m條邊的無序列表。將鄰接矩陣和無序列表結合起來就得到了一種新的圖的表示方式——鄰接表，即一個n元素數組，索引是各個頂點，且每個頂點u所對應的數組項是頂點u的所有鄰接頂點所組成的表?？偠灾?，鄰接表的所有頂點所對應的數組項中共包含m個頂點

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

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

如果確實需要在表中插入新項，那么我們可以使用鏈表，鏈表中的每項君包含它的后繼位置，如果需要在表內刪除元素，那么鏈表也應該包括該項的前驅位置，以便我們能迅速地建立新的次序關系。

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

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

拓撲排序：

一個有向無環圖的拓撲排序需要產生一個線性序列：如果(u,v)是有向無環圖的一條邊，那么在線性序列匯中，u必須出現在v之前。

程序 TOPOLLOGICAL-SORT(G)

輸入 G：一個頂點編號為從1～n的有向無環圖

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

步驟

1.令in-degree[1......n]為一個新數組，創建一個空的關于頂點的線性序列。

2.令in-degree數組中的每個元素均為0。

3.對于每個頂點u:

A.對于每個與頂點u相鄰接的頂點v:

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

4.創建一個列表next,用以存放所有滿足in-degree[u]=0的頂點u。

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

A.從next列表中刪除一個頂點（將該頂點稱為頂點u）。

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

C.對于每個與u相鄰接的頂點v:

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

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

6.返回線性序列。

拓撲排序程序中僅僅記錄了每個頂點的入度，并將理論上移除的邊所指向的頂點的入度減一。由于數組索引是整數，現假定每個頂點均由一個介于1～n范圍內的一個確定的整數表示。因為該程序需要快速地確定入度為0的頂點，它將每隔頂點的入讀存儲在數組in-degree中，并且將所有入度為0的頂點存儲在列表next中。第1～3步初始化in-degree數組，第4步初始化next列表，且當頂點和邊在概念上被移除時，第5步負責更新in-degree數組和next列表。該程序能選擇next列表中的任何一個頂點作為線性序列的下一個元素。

拓撲排序的運行時間：

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

PERT圖表中的關鍵路徑：

<PERT："PRogram evaluation and review technique"，即令多個任務盡可能地同時執行，完成整個工作的時間被稱為PERT圖表的“關鍵路徑”>

<路徑：指一個頂點和邊構成的序列，該序列允許從一個頂點到達另一個頂點（允許從一個頂點到達它本身）的邊的序列>

<環：一條從一個頂點出發，最后又能回歸原頂點的路徑>

<權：用來表示和邊相關聯的一個通用術語。一個邊上帶有權重的有向圖稱為加權有向圖>

<一條路徑的權重：表示路徑上所有邊的權重之和>

<最短路徑：表示從頂點u到頂點v的所有路徑中的邊的權重和最小的路徑，最短路徑并不一定是唯一的，因為一個有向圖中從頂點u到頂點v可能存在多條最短路徑>

一個PERT圖表中的一條關鍵路徑是指所有路徑中完成任務所花費時間總和最大的路徑。沿著一條關鍵路徑完成任務所花費的時間給出了無論多少個任務被同時執行，完成整個工作所需要花費的最少可能時間。

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

//在得出關鍵路徑之前，需要先學會求最短路徑。

有向無環圖中的最短路徑：

我們假定有向無環圖被存儲在一個鄰接表中，并且將于邊(u,v)關聯的權重存儲為weight(u,v)。

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

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

將最短路徑算法的結果分別存儲在數組shortest[1......n]和數組pred[1......n]中。（運行過程中兩個數組中的值可能不是最終的正確值，可是當算法執行完畢之后，兩個數組存儲的結果就是正確的值）

我們需要處理所產生的幾個問題。

1.要是從頂點s到頂點v不存在路徑呢？

那么我們就設sp(s,v)=∞，則shortest[v]結果應該是∞。因為頂點v在從源點s出發的最短路徑上不存在前驅，所以pred[v]應該為NULL。而頂點s也沒有前驅，所以稱pred[s]也應該為NULL。

2.圖中可能存在環，同時也存在帶負權重的邊，要是存在一個權重和為負的環呢？

那么我們可以循環地無窮次在該環上執行操作，每循環一次就會使得路徑上的權重降低一些。然而，我們僅僅關心無環圖，所以圖中不會存在環路，我們也無需擔心權重和為負的環了。

為了計算從源點s出發的最短路徑，我們以shortest[s]=0開始計算，對于所有其他頂點v，shortest[v]=∞（因為我們提前并不知道從頂點s出發時，我們能夠到達哪個頂點），并且對于所有的頂點v，均有pred[v]=NULL成立。隨后我們對圖上的邊應用一系列的松弛步驟：

程序 RELAX（u,v）

輸入 u,v：邊（u,v）的頂點u,v。

結果 shortest[v]的值可能會減小，如果它確實會減小，那么令pred[v]取u。

步驟

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

當調用RELAX（u,v）時，我們判定能否通過將(u,v)作為最后一條邊來改進從源點s到頂點v的最短路徑。

如果沿著最短路徑按序對各個邊執行松弛操作，我們會得到正確的結果。（可是，當我們甚至都還不知道哪條路徑是最短路徑的時候，如何能做到沿著最短路徑按序對各個邊執行松弛操作呢？A：對于一個有向無環圖來說，操作很簡單，我們對有向無環圖中的所有邊進行松弛操作，并且當我們對于所有邊執行松弛操作時，每條最短路徑上的邊也都按序被執行了松弛操作。）

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

對于除源點之外的所有頂點，shortest[u]=∞，對于所有頂點pred[u]=NULL，而對于源點s,shortest[s]=0。

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

當對邊執行松弛操作后，頂點v的shortest值和pred值是正確的：shortest[v]=sp(u,v)，且pred[v]是位于從源點s出發的最短路徑上的頂點v的前驅。

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

首先，利用拓撲排序對有向無環圖進行排序。

隨后，對于按照拓撲排序后所得到的線性序列中的每個頂點，依序對從每個頂點出發的所有邊執行松弛操作。

由于每條邊必定是從線性序列中的排列在較前側的頂點出發，然后進入到線性序列中排列在后面的頂點，因此有向無環圖中的每個路徑一定會以一種與線性序列相一致的順序來訪問各個頂點。

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

輸入 G：一個加權有向無環圖（包含具有n個頂點的集合V，m條有向邊的集合E）

s：集合V中的一個源點

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

步驟

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

2.對于除了頂點s之外的任一頂點v，shortest[v]均被賦值為∞，將shortest[s]賦值為0，對于每個頂點v，將pred[v]賦值為NULL。

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

A.對于每個與頂點u相鄰接的頂點v：

i.調用RELAX（u,v)。