有向無(wú)環(huán)圖及其應(yīng)用(已修改)
2024-10-31 20:28 本頁(yè)面
【正文】 有向無(wú)環(huán)圖 ? 無(wú)環(huán)的有向圖稱為有向無(wú)環(huán)圖，簡(jiǎn)稱 DAG圖 ? P179 圖 ：有向樹(shù)、 DAG圖、有向圖 ? DAG圖可用于： 描述含有公共子式的表達(dá)式； 描述工程的進(jìn)行過(guò)程； ? 有向無(wú)環(huán)圖是描述一項(xiàng)工程進(jìn)行過(guò)程的有效工具，主要進(jìn)行拓?fù)渑判蚝完P(guān)鍵路徑的操作。 工程能否順利進(jìn)行 — 拓?fù)渑判? 完成整個(gè)工程所需的最短時(shí)間 — 關(guān)鍵路徑 活動(dòng)網(wǎng)絡(luò) (Activity Network) ? 計(jì)劃、施工過(guò)程、生產(chǎn)流程、程序流程等都是“ 工程 ”。除了很小的工程外，一般都可以將工程分為若干個(gè)稱作“ 活動(dòng) ”的子工程，完成了這些活動(dòng)，整個(gè)工程就可以完成了。 ? 例：計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門(mén)課程的學(xué)習(xí)就是整個(gè)工程的一個(gè)活動(dòng)，其中有些課程要求先修課程，有些則不要求，這樣在有的課程之間就存在領(lǐng)先關(guān)系，而有的課程則可以并行學(xué)習(xí)。 用頂點(diǎn)表示活動(dòng)的網(wǎng) (AOV網(wǎng) ) C1 高等數(shù)學(xué) C2 程序設(shè)計(jì)基礎(chǔ) 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 C8 大學(xué)物理 C1 C9 計(jì)算機(jī)原理 C8 學(xué)生課程學(xué)習(xí)工程圖 C8 C3 C5 C4 C9 C6 C7 C1 C2 ? 可以用 有向圖 表示一個(gè)工程。在這種有向圖中， 用頂點(diǎn)表示活動(dòng) ， 用有向邊 Vi, Vj表示 活動(dòng) Vi 必須先于活動(dòng) Vj 進(jìn)行 。這種有向圖稱作頂點(diǎn)表示活動(dòng)的 AOV網(wǎng) (Activity On Vertex)。 ? 在 AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路 ,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1