第7章 數(shù)據(jù)結(jié)構(gòu)（Ｃ＋＋版）4圖

第7章圖第4講第6章樹與二叉樹1本章分為（4～5）講第1講

7.1

圖的基本概念

7.2

圖的存儲結(jié)構(gòu)-7.2.1第3講

7.4圖的最小生成樹

7.5最短路徑第2講

7.4圖的存儲結(jié)構(gòu)-7.2.2,7.2.3,7.2.47.3圖的遍歷與連通性

第4講7.6拓撲排序與關鍵路徑題小結(jié)

供教師參考27.6

拓撲排序與關鍵路徑一個無環(huán)的有向圖稱為有向無環(huán)圖（DirectedAcyclicGraph），簡稱DAG圖。有向無環(huán)圖是描述一項工程的有效工具。如計劃過程、施工工程、生產(chǎn)流程、程序流程等。一般來說，每個工程（Project）都可分成若干個稱為活動（Activity）的子工程。這些子工程之間存在一定的約束，其中某些子工程的開始必須在另一些子工程完成之后。37.6拓撲排序與關鍵路徑用有向無環(huán)圖可表示一個工程，其中有向邊表示約束關系。對于整個工程，人們關心的是兩方面的問題：一是工程能否順利進行；二是估算整個工程完成所需的最短時間。關系到兩個問題：拓撲排序和關鍵路徑。47.6.1

拓撲排序一個計算機專業(yè)的學生課程計劃可以看成一個工程.代號課程名先行課代號課程名先行課C1

計算機導論無C9

算法分析C3C2

數(shù)值分析C1,C14C10

高級語言C3,C4C3

數(shù)據(jù)結(jié)構(gòu)C1,C14C11

編譯系統(tǒng)C10C4

匯編語言C1,C13C12

操作系統(tǒng)C11C5

自動機理論C15C13

解析幾何無C6

人工智能C3C14

微積分C13C7

圖形學C3,C4,C10C15

線性代數(shù)C14C8

計算機原理C45有向圖有些課程是獨立于其他課程的基礎課，而有些課卻需要有先行課，前提條件規(guī)定了課程之間的優(yōu)先關系?？捎糜邢驁D表示。用頂點表示課程（活動）,有向邊表示前提條件。

這種用頂點表示活動、用有向邊表示活動之間的優(yōu)先關系的有向圖稱為頂點表示活動的網(wǎng)絡（ActivityOnVertexNetwork），簡稱AOV網(wǎng)。6拓撲排序

實際工程需要把AOV網(wǎng)中全部頂點排成一個線性序列，使得在此序列中頂點之間不僅保持有向圖中原有的次序關系，而且在有向圖中所有無關系的各對頂點之間人為地建立一個次序關系。稱具有上述特性的線性序列為拓撲有序序列。對AOV網(wǎng)構(gòu)造拓撲有序序列的運算稱為拓撲排序（TopologicalSort）。若AOV無環(huán)，可以找到該網(wǎng)的拓撲有序序列。反之，不存在拓撲有序序列。一個AOV網(wǎng)的拓撲有序序列不是唯一的。7AOV網(wǎng)進行拓撲排序的方法和步驟：（1）從AOV網(wǎng)中選擇一個沒有前趨的頂點（該頂點的入度為0）并且輸出它。（2）從網(wǎng)中刪去該頂點，并且刪去從該頂點發(fā)出的所有的弧。（3）重復上述兩步，直到剩余網(wǎng)中不再存在沒有前趨（入度為0）的頂點為止。兩種結(jié)果：一種是網(wǎng)中全部頂點都被輸出，拓撲排序成功；另一種是網(wǎng)中頂點未被全部輸出，剩余的頂點均有前趨頂點，存在有向回路，拓撲排序失敗。8一個AOV網(wǎng)拓撲排序的例子得到一個拓撲序列：（v1,v6,v4,v3,v2,v5）。9采用鄰接鏈表存儲結(jié)構(gòu)在表頭結(jié)點中增設一個入度域，以存放各個頂點當前的入度值。每個頂點的入度域的值都隨鄰接鏈表動態(tài)生成過程中累計得到，如圖（a）所示。10采利用入度為零的域作為鏈棧：為了避免在選入度為零的頂點時重復掃描表頭數(shù)組，利用數(shù)組中入度為零的頂點域作為鏈棧域，存放下一個入度為零的頂點序號。零表示棧底，棧頂指針為top。該棧鏈表如圖（b）。

棧頂指針top=6表明v6的入度為零；

v6的入度域為1，表明下一個入度為零的頂點是v1；

v1的入度為零表示v1是棧底。11鄰接鏈表為存儲結(jié)構(gòu)的拓撲排序算法：（1）掃描頂點表，將入度為零的頂點入棧。（2）While（棧非空）

{將棧頂點vj

彈出并輸出之；在鄰接鏈表中查vj

的直接后繼vk

，把vk的入度減1，若vk

的入度為零則進棧；

}（3）若輸出的頂點數(shù)等于n，則拓撲排序成功；否則有回路。12邊結(jié)點和頂點結(jié)點的結(jié)構(gòu)struct

edgenode //邊結(jié)點結(jié)構(gòu)

{intvex;

edgenode*link;};struct

vexnode //頂點的結(jié)構(gòu)

{intvex;

intid;

edgenode*link;//指向邊結(jié)點的指針};13拓撲排序-算法7.8：voidTOPOSORT(vexnodedig[])//AOV網(wǎng)的鄰接鏈表

{edgenode*p;top=0; //棧頂指針

m=0; //訪問輸出頂點計數(shù)

for(i=1;i<n+1;i++) //入度為零的頂點進棧

if(dig[i].id==0){dig[i].id=top;top=i;}while(top>0) //棧不空循環(huán)

{j=top;top=dig[top].id; //棧頂指針下移

cout<<j<<endl; //刪除入度零的頂點并輸出

m++;p=dig[j].link;

14

while(p!=NULL) //處理以vj為尾的弧

{k=p->vex;dig[k].id--; //把以vj為尾的弧的頭頂點vk的入度減1if(dig[k].id==0){dig[k].id=top; //若入度為零，則進棧

top=k;}p=p->link;}}//whiletopif(m<n)cout<<”Thenetworkhasacycle.″<<endl;}//TOPOSORT15拓撲排序算法分析對一個具有n個頂點e條邊的網(wǎng)來說，初始建立入度為零0的頂點棧，需要先檢查所有頂點一遍，執(zhí)行時間為O(n)；在拓撲排序過程中，若AOV網(wǎng)無回路，則每個頂點入、出棧各一次，每個表結(jié)點被檢查一次，執(zhí)行時間是O(n+e)，所以，整個算法的時間復雜度是O(n+e)。167.6.2

關鍵路徑在帶權(quán)的有向圖中，以頂點表示事件，以有向邊表示活動，邊上的權(quán)值表示活動的開銷（如該活動持續(xù)時間），則此帶權(quán)的有向圖稱為邊表示活動的網(wǎng)（ActivityonEdgeNetwork），稱AOE網(wǎng)。17AOE網(wǎng)具有以下性質(zhì)：（1）只有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各有向邊所代表的活動才能開始。（2）只有在進入某一頂點的各有向邊所代表的活動都已經(jīng)結(jié)束，該頂點所代表的事件才能發(fā)生。（3）表示實際工程計劃的AOE網(wǎng):

應是有向無環(huán)的;

存在唯一的入度為0的開始頂點;

存在唯一的出度為0的完成頂點。18從開始頂點到完成頂點的多條路徑中，具有最大路徑長度的路徑稱為關鍵路徑。關鍵路徑上的所有活動是關鍵活動。如圖的AOE網(wǎng)中，（v1,v2,v5,v7,v9)是一條關鍵路徑，（v1,v2,v5,v8,v9)也是一條關鍵路徑，它們的路徑長度是16。整個工程至少需要16天才能完成。要縮短工期須加快關鍵活動的進度。19定義幾個變量

1.事件vj

可能的最早發(fā)生時間ve(j)。

2.事件vk允許的最遲發(fā)生時間vl(k)。

3.活動ai

的最早開始時間e(i)。

4.活動ai

的最遲開始時間l(i)。

有向圖的頂點代表一個事件（即一種狀態(tài)，例如：開工、竣工等）；

有向邊（?。┐硪粋€活動（即一個過程，例如：打地基、澆注混凝土等），常持續(xù)一段時間。201.事件的最早發(fā)生時間ve(j)事件vj

可能的最早發(fā)生時間ve(j)，是從開始頂點v1到頂點vj的最大路徑長度。因為事件vj

的發(fā)生表明了以vj

為起點的各條出邊表示的活動可立即開始，所以事件vj

的最早發(fā)生時間ve(j)也是所有以vj為起點的出邊<vj,vk>所表示活動ai

的最早開始時間e(i)，即ve(j)=e(i)。如圖。212.事件的最遲發(fā)生時間vl(k)

一個事件vk允許的最遲發(fā)生時間vl(k)，應該等于完成頂點vn的最早發(fā)生時間ve(n)減去vk到vn的最長路徑長度。因為事件vk的發(fā)生表明以vk為終點的各入邊所表示的活動均已完成，所以事件vk的最遲發(fā)生時間vl（k）也是所有以vk為終點的入邊<vj,vk>所表示的活動ai可以最遲完成的時間。223.活動ai的最早開始時間e(i

)由前文可知：ve(j)=e(i)

活動最早開始時間，就是該弧出發(fā)頂點（事件）的最早發(fā)生時間。234.活動ai的最遲開始時間l(i)

為不推遲工期，活動ai的最遲開始時間l(i)應該是ai的最遲完成時間減（等于事件vk的最遲發(fā)生時間vl(k)）去ai的持續(xù)時間，即:

l(i)=vl(k)?<vj,vk>的權(quán)。

24關鍵路徑和關鍵活動

通常把e(i)=l(i)的活動稱為關鍵活動.

而l(i)?e(i)表示完成活動ai的時間余量。它是在不延誤工期的前提下活動ai可以延遲的時間。顯然，關鍵路徑上的所有活動都是關鍵活動.縮短或延誤關鍵活動的持續(xù)時間，都將提前或推遲整個工程的進度。因此，分析關鍵路徑的目的是識別哪些是關鍵活動，提高關鍵活動的效率，縮短整個工期。25計算關鍵活動和關鍵路徑的步驟（1）從開始頂點v1出發(fā),令ve(1)

=0，按拓撲有序序列求其余各頂點的可能最早發(fā)生時間：

ve(k)

=

max{ve(j)+dut(<j，k>)} （7-1）j∈T其中T是以頂點vk為頭的所有弧的尾頂點的集合（2≤k≤n）。如果得到的拓撲有序序列中頂點的個數(shù)小于網(wǎng)中頂點個數(shù)n，則說明網(wǎng)中有環(huán)，不能求出關鍵路徑，算法結(jié)束。26計算關鍵活動和關鍵路徑的步驟（2）從完成頂點vn出發(fā)，令vl(n)

=

ve(n)，按逆拓撲有序求其余各頂點的允許的最晚發(fā)生時間：

vl(j)

=

min{vl(k)?dut(<j,k>)}

k∈SS是以頂點vj為弧尾的所有弧的弧頭頂點集合（1≤j≤n?1）。27計算關鍵活動和關鍵路徑的步驟（3）求每一項活動ai（1≤i≤m）的最早開始時間e(i)=

ve(j)，最晚開始時間l(i)

=

vl(k)?dut（<j,k>）。若某條弧滿足e(i)=l(i)，則它是關鍵活動。對于AOE網(wǎng)，按以上步驟的計算結(jié)果可得到a1，a4，a7，a8，a10，a11是關鍵活動。28求出AOE網(wǎng)中所有關鍵活動后，只要刪去AOE網(wǎng)中所有的非關鍵活動，即可得到AOE網(wǎng)的關鍵路徑。這時從開始頂點到達完成頂點的所有路徑都是關鍵路徑。一個AOE網(wǎng)的關鍵路徑可以不止一條，如圖所示AOE網(wǎng)中有2條關鍵路徑，即（v1,v2,