《有向無(wú)環(huán)圖的應(yīng)用》PPT課件

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

1、第7章圖7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問(wèn)題7.5有向無(wú)環(huán)圖及其應(yīng)用7.6最短路徑7.5有向無(wú)環(huán)圖及其應(yīng)用有向無(wú)環(huán)圖(directedacyclinegraph)簡(jiǎn)稱DAG圖，是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過(guò)程的有效工具。對(duì)整個(gè)工程和系統(tǒng)，人們關(guān)心的是兩個(gè)方面的問(wèn)題：一是工程能否順利進(jìn)行；二是估算整個(gè)工程完成所必須的最短時(shí)間。有向無(wú)環(huán)圖的應(yīng)用：拓?fù)渑判蜿P(guān)鍵路徑在工程實(shí)踐中，一個(gè)工程項(xiàng)目往往由若干個(gè)子項(xiàng)目組成，這些子項(xiàng)目間往往有多種關(guān)系：①先后關(guān)系，即必須在一子項(xiàng)目完成后，才能開(kāi)始實(shí)施另一個(gè)子項(xiàng)目；②子項(xiàng)目之間無(wú)次序要求，即兩個(gè)子項(xiàng)目可以同時(shí)進(jìn)行，互不影響。

2、我們用一種有向圖來(lái)表示上述問(wèn)題。在這種有向圖中，頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)的優(yōu)先關(guān)系，這種有向圖叫做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(ActivityOnVertexNetwork)簡(jiǎn)稱為AOV網(wǎng)。7.5.1拓?fù)渑判蛘n程編號(hào)課程名稱先導(dǎo)課程編號(hào)C1程序設(shè)計(jì)基礎(chǔ)無(wú)C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1，C2C4匯編語(yǔ)言C1C5算法分析與設(shè)計(jì)C3，C4C6計(jì)算機(jī)組成原理C11C7編譯原理C5，C3C8操作系統(tǒng)C3，C6C9高等數(shù)學(xué)無(wú)C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C9，C10，C1課程先后關(guān)系如圖：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6

3、c7c8c2在AOV網(wǎng)絡(luò)中，如果頂點(diǎn)Vi的活動(dòng)必須在頂點(diǎn)Vj的活動(dòng)以前進(jìn)行，則稱Vi為Vj的前趨頂點(diǎn)，而稱Vj為Vi的后繼頂點(diǎn)。這種前趨后繼關(guān)系有傳遞性。此外，任何活動(dòng)i不能以它自己作為自己的前驅(qū)或后繼，這叫做反自反性。從前驅(qū)和后繼的傳遞性和反自反性來(lái)看，AOV網(wǎng)中不能出現(xiàn)回路(有向環(huán))，回路表示頂點(diǎn)之間的先后關(guān)系進(jìn)入了死循環(huán)。判斷AOV網(wǎng)是否有有向環(huán)的方法是對(duì)該AOV網(wǎng)進(jìn)行拓?fù)渑判?，將AOV網(wǎng)中頂點(diǎn)排列成一個(gè)線性有序序列，若該線性序列中包含AOV網(wǎng)全部頂點(diǎn)，則AOV網(wǎng)無(wú)環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該AOV網(wǎng)所代表的工程是不可行的。何謂“拓?fù)渑判颉保客負(fù)湫蛄校涸贏OV網(wǎng)中，若不存在回

4、路，則所有活動(dòng)可排列成一個(gè)線性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，我們把此序列叫做拓?fù)湫蛄?。拓?fù)渑判蛴葾OV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^(guò)程叫拓?fù)渑判?。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?，滿足上述定義的任一線性序列都稱為它的拓?fù)湫蛄小Ｍ負(fù)溆行蛐蛄校海–1，C2，C3，C4，C5，C8，C9，C7，C6）（C2，C5，C1，C8，C3，C9，C4，C7，C6）如何進(jìn)行拓?fù)渑判?？解決方法：1）從有向圖中選取一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，并輸出之；2）從有向圖中刪去此頂點(diǎn)以及所有以它為尾的?。?）重復(fù)上述兩步，直至圖空，或者圖不空但找不到無(wú)前驅(qū)的頂點(diǎn)為止。后一種情況說(shuō)明有向圖中存在環(huán)。如何在計(jì)算機(jī)中實(shí)現(xiàn)拓

5、撲排序呢？拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?，?duì)給定的有向圖可采用鄰接表作為它的存儲(chǔ)結(jié)構(gòu)。將每個(gè)鏈表的表頭結(jié)點(diǎn)構(gòu)成一個(gè)順序表，各表頭結(jié)點(diǎn)的Data域存放相應(yīng)頂點(diǎn)的入度值。每個(gè)頂點(diǎn)入度初值可隨鄰接表動(dòng)態(tài)生成過(guò)程中累計(jì)得到。在拓?fù)渑判蜻^(guò)程中，凡入度為零的頂點(diǎn)即是沒(méi)有前趨的頂點(diǎn)，可將其取出列入有序序列中，同時(shí)將該頂點(diǎn)從圖中刪除掉不再考慮。刪去一個(gè)頂點(diǎn)時(shí)，所有它的直接后繼頂點(diǎn)入度均減1，表示相應(yīng)的有向邊也被刪除掉。設(shè)置一個(gè)堆棧，將已檢驗(yàn)到的入度為零的頂點(diǎn)標(biāo)號(hào)進(jìn)棧，當(dāng)再出現(xiàn)新的無(wú)前趨頂點(diǎn)時(shí)，也陸續(xù)將其進(jìn)棧。每次選入度為零的頂點(diǎn)時(shí)，只要取棧頂頂點(diǎn)即可。4∧0∧04∧21003∧14∧AOV網(wǎng)絡(luò)

6、的鄰接表01234頂點(diǎn)的入度數(shù)組下標(biāo)用鄰接表存儲(chǔ)AOV網(wǎng)絡(luò)，拓?fù)渑判蛩惴枋觯?1)把鄰接表中所有入度為零的頂點(diǎn)進(jìn)棧；(2)在棧不空時(shí)：①退棧并輸出棧頂?shù)捻旤c(diǎn)j；②在鄰接表的第j個(gè)單鏈表中，查找頂點(diǎn)為j的所有直接后繼頂點(diǎn)k，并將k的入度減1。若頂點(diǎn)k的入度為零，則頂點(diǎn)k進(jìn)棧；③若?？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖中有環(huán)路，否則拓?fù)渑判蛲戤?。拓?fù)渑判蛩惴⊿tatusTopologicalSort(ALGraphG){//有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無(wú)回路，//則輸出G的頂點(diǎn)的1個(gè)拓?fù)湫蛄胁⒎祷豋K，否則ERRORFindInDegree(G，indegree)；//對(duì)各頂點(diǎn)求入度in

7、degree[0..vernum-1]InitStack(S)；for(i=0；i