有向無環(huán)圖及其應(yīng)用-文庫吧資料
2024-10-25 20:28本頁面
【正文】 的邊 , 邊的終頂點(diǎn)入度減一 。 拓?fù)渑判蛩惴擅枋鋈缦拢? ? 建立入度為零的頂點(diǎn)棧 。 入度為零的頂點(diǎn)即無前驅(qū)頂點(diǎn) 。 它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點(diǎn)，如 C4和 C2，也排出了先后次序關(guān)系。這時網(wǎng)絡(luò)中必存在有向環(huán)。 ④ 重復(fù)以上 ② 、 ③ 步 , 直到 ? 全部頂點(diǎn)均已輸出 ，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿?；? ? 圖中還有未輸出的頂點(diǎn) , 但已跳出處理循環(huán) 。 ② 在 AOV網(wǎng)絡(luò)中選一個 沒有直接前驅(qū) 的頂點(diǎn) , 并輸出之 。 ? 如果 AOV網(wǎng)絡(luò)中存在有向環(huán)，此 AOV網(wǎng)絡(luò)所代表的工程是不可行的。 ? 這種構(gòu)造 AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判颉? ? 檢測有向環(huán)的一種方法是對 AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄小Ｈ绻霈F(xiàn)了有向環(huán)，則意味著某項(xiàng)活動應(yīng)以自己作為先決條件。這種有向圖稱作頂點(diǎn)表示活動的 AOV網(wǎng) (Activity On Vertex)。 用頂點(diǎn)表示活動的網(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 高級語言程序設(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 ? 可以用 有向圖 表示一個工程。除了很小的工程外，一般都可以將工程分為若干個稱作“ 活動 ”的子工程，完成了這些活動，整個工程就可以完成了。有向無環(huán)圖 ? 無環(huán)的有向圖稱為有向無環(huán)圖，簡稱 DAG
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1