《圖有向無環(huán)圖》PPT課件

《《圖有向無環(huán)圖》PPT課件》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、7.5有向無環(huán)圖及其應(yīng)用1、何為有向無環(huán)圖（DAG圖）實例BEFGLFGBEFGLFGBEFGLFG有向樹DAG圖有向圖（含環(huán)）用途：描述工程項目或系統(tǒng)進(jìn)行的工具AOV網(wǎng)絡(luò)：定義結(jié)點為活動，有向邊的指向表示活動執(zhí)行的次序。AOE網(wǎng)絡(luò)：定義結(jié)點為事件，有向邊的指向表示事件的執(zhí)行次序。單位是時間（時刻）。有向邊定義為活動，它的權(quán)值定義為活動進(jìn)行所需要的時間。ABAB102、拓?fù)渑判颍═opologicalSort）偏序：若集合X上的關(guān)系R是傳遞的、自反的、反對稱的，則稱R是集合X上的偏序關(guān)系。全序：若關(guān)系R是集合X上的偏序關(guān)系，

2、如果對于每個x,y屬于X，必有xRy或yRx，則稱R是集合X上的全序關(guān)系。復(fù)習(xí)：拓?fù)渑判颍喝绻幸粋€序列A=a1,a2,a3…………an是集合X上的元素的一個序列，且當(dāng)i

3、向表示活動執(zhí)行的次序。實例：下述集合M代表課程的集合，其中，1代表數(shù)學(xué)，2代表程序設(shè)計，3代表離散數(shù)學(xué)，4代表匯編程序設(shè)計，5代表數(shù)據(jù)結(jié)構(gòu)，6代表結(jié)構(gòu)程序設(shè)計,7代表編譯原理。關(guān)系R課程學(xué)習(xí)的先后關(guān)系，如數(shù)學(xué)必須在離散數(shù)學(xué)之前學(xué)習(xí)。要求排一張學(xué)習(xí)的先后次序表。1327564第一個輸出的結(jié)點：必須無前件。后件：必須等到它的前件輸出之后輸出。無前件及后件的結(jié)點：任何時候都可輸出。序列：1、3、2、4、6、5、7合乎拓?fù)渑判虻囊笮蛱?、2、3、4、5、6、7合乎拓?fù)渑判虻囊笮蛄校?、1、2、4、6、5、7不合乎拓?fù)渑判虻囊笤?/p>

4、素3的序號1（后件）<元素1（前件）的序號2132756413246571327564可交換可交換可交換算法（使用鄰接矩陣）：1327564011000000001110000101000000000000010000001000000012345671234567算法的執(zhí)行步驟：1、找到全為零的第j列，輸出j2、將第j行的全部元素置為零3、找到全為零的第k列，輸出k4、將第k行的全部元素置為零…………………反復(fù)執(zhí)行3、4；直至所有元素輸出完畢。0000000000011100001010000000000000100000

5、010000000算法（使用鄰接表）：1327564算法的執(zhí)行步驟：1、用一個數(shù)組記錄每個結(jié)點的入度。將入度為零的結(jié)點進(jìn)棧。2、將棧中入度為零的結(jié)點V輸出。3、根據(jù)鄰接表找到結(jié)點V的所有的鄰接結(jié)點，并將這些鄰接結(jié)點的入度減一。如果某一結(jié)點的入度變?yōu)榱悖瑒t進(jìn)棧。4、反復(fù)執(zhí)行2、3；直至?？諡橹?。…………………次序執(zhí)行結(jié)束，如果輸出結(jié)點數(shù)等于圖的結(jié)點總數(shù)，則有向圖有環(huán)，否則有向圖有環(huán)。12120123456null34463455nullnullnull6763nullnullnullnull01012345611213inde

6、gree0棧1327564算法（使用鄰接表）：StatusTopologicalsort（ALGraphG）{findinDegree（G，indegree）;Initstack（S）；for（i=0;inextarc）;{k=p

7、->adjnexr;if（!（--indegree[k]））Push（S,k）;}}if（count

8、件先發(fā)生，而終止結(jié)點事件才能發(fā)生。B10A關(guān)鍵活動：最早開始時間＝最遲開始時間的活動關(guān)鍵路徑：從源點到匯點的最長的一條路徑，或者全部由關(guān)鍵活動構(gòu)成的路徑。kjdut(j,k)ai術(shù)語：事件的最早發(fā)生時間（Ve(j)）：從起點到本結(jié)點的最長的路徑。意味著事件最早能夠發(fā)生的時刻。事件的最遲發(fā)生