aov網(wǎng)和拓?fù)渑判?ppt

1、第七章 圖（續(xù)）,有向無(wú)環(huán)圖 及應(yīng)用,有向無(wú)環(huán)圖的定義 有向圖中是否有環(huán)的檢查 有向無(wú)環(huán)圖的應(yīng)用: 工程能否順利進(jìn)行拓?fù)渑判?估算完成工程的最短時(shí)間關(guān)鍵路徑,有向無(wú)環(huán)圖,有向無(wú)環(huán)圖（DAG圖）：沒(méi)有回路(環(huán))的有向圖。,有向無(wú)環(huán)圖,有向圖（有環(huán)）,一、AOV-網(wǎng)(Activity On Vertices),表示工程的有向圖中，用頂點(diǎn)表示活動(dòng)，用有向邊表示活動(dòng)Vi 必須先于活動(dòng)Vj 進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動(dòng)的AOV網(wǎng)絡(luò)。 （用頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖）,在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路（即有向環(huán)）。 若出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。因此，對(duì)給定的A

2、OV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。,檢查有向圖中是否存在回路的方法之一，是對(duì)有向圖進(jìn)行拓?fù)渑判?。,何謂“拓?fù)渑判颉保?對(duì)有向圖進(jìn)行如下操作:,按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線(xiàn)性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。,由此所得頂點(diǎn)的線(xiàn)性序列稱(chēng)之為拓?fù)溆行蛐蛄?,拓?fù)渑判蚴菍?duì)有向無(wú)環(huán)圖的頂點(diǎn)的一種排序 。,拓?fù)渑判?舉例,課程編號(hào) 課程名稱(chēng) 先修課程 C1 高等數(shù)學(xué) 無(wú) C2 程序設(shè)計(jì)基礎(chǔ) 無(wú) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級(jí)語(yǔ)言程序設(shè)計(jì) C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C

3、8 普通物理 C1 C9 計(jì)算機(jī)原理 C8,表示教學(xué)計(jì)劃（課程之間）的優(yōu)先關(guān)系有向圖,對(duì)圖進(jìn)行拓?fù)渑判? 得到的拓?fù)溆行蛐蛄袨?C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7,或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6,構(gòu)造拓?fù)溆行蛐蛄?，即將各個(gè)頂點(diǎn) (代表各個(gè)活動(dòng))排列成一個(gè)線(xiàn)性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿(mǎn)足。,構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算稱(chēng)為拓?fù)渑判颉?如果通過(guò)拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個(gè)拓?fù)溆行?的序列中, 則該網(wǎng)絡(luò)中必定不會(huì)出現(xiàn)有向環(huán)。,如

4、果AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。,拓?fù)渑判蚍椒? 重復(fù)以上 、步, 直到 全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿桑换?圖中還有未輸出的頂點(diǎn), 但已跳出處理循環(huán)。說(shuō)明圖中還剩下一些頂點(diǎn), 它們都有直接前驅(qū)。這時(shí)網(wǎng)絡(luò)中必存在有向環(huán)。, 輸入AOV網(wǎng)絡(luò)；, 在AOV網(wǎng)絡(luò)中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn), 并輸出之;, 從圖中刪去該頂點(diǎn), 同時(shí)刪去所有它發(fā)出的有向邊;,a,b,h,c,d,g,f,e,得到的拓?fù)溆行蛐蛄袧M(mǎn)足圖中給出的所有前驅(qū)和后繼關(guān)系。,如何在計(jì)算機(jī)上實(shí)現(xiàn) 對(duì)有向圖的拓?fù)渑判颍?？,在算法中需要用定量的描述替代定性的概念,沒(méi)有前驅(qū)的頂點(diǎn) 入度為零的頂點(diǎn)

5、,刪除頂點(diǎn)及以它為尾的弧 弧頭頂點(diǎn)的入度減1,拓?fù)渑判蛩惴?拓?fù)渑判蚍椒?拓?fù)渑判蜻^(guò)程中涉及的數(shù)據(jù)和操作：,（1） 選擇一入度為0頂點(diǎn)v，輸出；,（2） 將v鄰接到的頂點(diǎn)的入度減1；,（3）重復(fù)（1）、（2）， 直到輸出全部頂點(diǎn)， 或，有向圖沒(méi)有入度為0的頂點(diǎn)。,數(shù)據(jù)：有向圖、頂點(diǎn)的入度；,操作： （1） 選擇一入度為0頂點(diǎn)v，輸出； （2） 將v鄰接到的頂點(diǎn) u 的入度減1。,為算法的有關(guān)數(shù)據(jù)選擇設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)(圖用鄰接表表示),數(shù)組indegree：記錄各頂點(diǎn)入度,對(duì)于入度為零的頂點(diǎn)即無(wú)前驅(qū)頂點(diǎn)，刪除該頂點(diǎn)及以它為尾的弧的操作，則可換以弧頭頂點(diǎn)的入度減1來(lái)實(shí)現(xiàn)。,棧S：存儲(chǔ)入度為0的頂點(diǎn)的編

6、號(hào).,初始時(shí)，只有v2,v4 兩頂點(diǎn)的入度為0,為避免每次都要搜索入度為零的頂點(diǎn)，在算法中設(shè)置一個(gè)“棧”，以保存“入度為零”的頂點(diǎn)。,如果輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù), 則報(bào)告網(wǎng)絡(luò)中存在有向環(huán)。,拓?fù)渑判蛩惴枋觯?建立入度為零的頂點(diǎn)棧;,當(dāng)入度為零的頂點(diǎn)棧不空時(shí), 重復(fù)執(zhí)行：,從頂點(diǎn)棧中退出一個(gè)頂點(diǎn), 并輸出之；,從AOV網(wǎng)絡(luò)中刪去這個(gè)頂點(diǎn)和它發(fā)出的邊, 邊的終頂點(diǎn)入度減1；,如果邊的終頂點(diǎn)入度減至0, 則該頂點(diǎn)進(jìn)入度為零的頂點(diǎn)棧。,Status TopologicalSort(ALGraph G) /若G無(wú)回路，則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K，否則ERROR FindInD

7、egree(G, indegree); /求各頂點(diǎn)入度indegree0.vexnum-1 InitStack(S); for(i=0; iG. vexnum; +i) if (! indegreei) Push(S, i); /入度為0頂點(diǎn)的下標(biāo)進(jìn)棧 count = 0; /對(duì)輸出頂點(diǎn)計(jì)數(shù),1 3 0 1 0 3,while(! StackEmpty(S) Pop(S, i); printf(i, G. verticesi.data); +count; for (p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; if ( !(- -i

8、ndegreek) ) Push(S, k); /for /while,i=4,4, C4,count=1,p,k=0,0,0,k=1,2,k=5,2,p=NULL,while(! StackEmpty(S) Pop(S, i); printf(i, G. verticesi.data); +count; for (p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; if ( !(- -indegreek) ) Push(S, k); /for /while,i=0,0, C0,count=2,p,k=1,1,3,k=3,0,p=NULL

9、,while(! StackEmpty(S) Pop(S, i); printf(i, G. verticesi.data); +count; for (p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; if ( !(- -indegreek) ) Push(S, k); /for /while,i=3,3, C3,count=3,p,p=NULL,while(! StackEmpty(S) Pop(S, i); printf(i, G. verticesi.data); +count; for (p=G.verticesi.first

10、arc; p; p=p-nextarc) k = p-adjvex; if ( !(- -indegreek) ) Push(S, k); /for /while,i=2,2, C2,count=4,p,k=1,0,1,k=5,1,p=NULL,while(! StackEmpty(S) Pop(S, i); printf(i, G. verticesi.data); +count; for (p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; if ( !(- -indegreek) ) Push(S, k); /for /while,

11、i=1,1, C1,count=5,p,k=5,0,5,p=NULL,while(! StackEmpty(S) Pop(S, i); printf(i, G. verticesi.data); +count; for (p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; if ( !(- -indegreek) ) Push(S, k); /for /while,i=5,5, C5,count=6,p,p=NULL,拓?fù)湫蛄校篊4, C0, C3, C2, C1, C5,Status TopologicalSort(ALGraph G) FindInDegree(G, indegree); /求各頂點(diǎn)入度indegree0.vexnum-1 InitStack(S); for(i=0; inextarc) k = p-adjvex; if ( !(- -indegreek) ) Push(S, k); /對(duì)