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

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

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

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

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

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

5、010000000算法（使用鄰接表）：1327564算法的執(zhí)行步驟：1、用一個(gè)數(shù)組記錄每個(gè)結(jié)點(diǎn)的入度。將入度為零的結(jié)點(diǎn)進(jìn)棧。2、將棧中入度為零的結(jié)點(diǎn)V輸出。3、根據(jù)鄰接表找到結(jié)點(diǎn)V的所有的鄰接結(jié)點(diǎn)，并將這些鄰接結(jié)點(diǎn)的入度減一。如果某一結(jié)點(diǎn)的入度變?yōu)榱?，則進(jìn)棧。4、反復(fù)執(zhí)行2、3；直至?？諡橹?。…………………次序執(zhí)行結(jié)束，如果輸出結(jié)點(diǎn)數(shù)等于圖的結(jié)點(diǎn)總數(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é)點(diǎn)事件才能發(fā)生。B10A關(guān)鍵活動(dòng)：最早開始時(shí)間＝最遲開始時(shí)間的活動(dòng)關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的最長(zhǎng)的一條路徑，或者全部由關(guān)鍵活動(dòng)構(gòu)成的路徑。kjdut(j,k)ai術(shù)語(yǔ)：事件的最早發(fā)生時(shí)間（Ve(j)）：從起點(diǎn)到本結(jié)點(diǎn)的最長(zhǎng)的路徑。意味著事件最早能夠發(fā)生的時(shí)刻。事件的最遲發(fā)生