7.5 有向無環圖

01有向無環圖

1、一個無環的有向圖稱做有向無環圖（directed acycline graph），簡稱DAG圖，DAG圖是一類較有向樹更一般的特殊有向圖。

2、有向無環圖是描述含有公共子式的表達式的有效工具。

3、若利用有向無環圖，則可實現對相同子式的共享，從而節省存儲空間。

4、檢查一個有向圖是否存在環要比無向圖復雜。對于無向圖來說，若深度優先遍歷過程中遇到回邊，則必定存在環，而對于有向圖來說，這條回邊有可能是指向深度優先生成森林中另一棵生成樹上頂點的弧。

5、有向無環圖也是描述一項工程或系統的進行過程的有效工具。

6、幾乎所有的工程都可分為若干個稱做活動的子工程，而這些子工程之間，通常受著一定條件的約束。

7、拓撲排序：由某個集合上的一個偏序得到該集合上的一個全序。

8、路徑長度最長的路徑叫做關鍵路徑。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。