【正文】 現(xiàn)對相同子式的共享，節(jié)省存儲空間。 有向無環(huán)圖 例子見 p179圖 另一用途： 有向無環(huán)圖是描述工程或系統(tǒng)的進行過程的有效工具。： 幾乎所有 工程 都可分為若干個稱為活動的 子工程 ，而這些子工程之間，通常受著一定條件的約束，如某些子工程的開始 必須在 另一子工程完成 之后。 關心兩方面問題： 工程能否順利進行。 估算整個工程完成必須的最短時間。 檢查有向圖是否存在環(huán)：從有向圖上某個頂點 v出發(fā)遍歷，在 dfs結束之前出現(xiàn)一條從頂點 u到頂點 v的回邊，由于 u在生成樹是 v的子孫，則有向圖中必存在包含頂點 v和 u的環(huán)。 ? 拓撲排序 – 問題提出：學生選修課程問題 頂點 ——表示課程 有向弧 ——表示先決條件，若課程 i是課程 j的先決條件，則圖中有弧 i,j 學生應按怎樣的順序學習這些課程，才能無矛盾、順利地完成學業(yè) ——拓撲排序 – 定義 ? AOV網(wǎng) ——用頂點表示活動，用弧表示活動間優(yōu)先關系的有向圖稱為頂點表示活動的網(wǎng) (Activity On Vertex work)，簡稱 AOV網(wǎng) – 若 vi,vj是圖中有向邊，則 vi是 vj的直接前驅； vj是 vi的直接后繼 – AOV網(wǎng)中不允許有回路，這意味著某項活動以自己為先決條件 ? 拓撲排序： ? 由某個集合上的一個偏序得到該集合上的一個全序 ? 由偏序定義得到拓撲有序（全序）的操作 ? 拓撲排序 ——把 AOV網(wǎng)絡中各頂點按照它們相互之間的優(yōu)先關系排列成一個線性序列的過程叫 ~ – 檢測 AOV網(wǎng)中是否存在環(huán)方法：對有向圖構造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán) – 拓撲排序的方法 ? 在有向圖中選一個沒有前驅的頂點且輸出之 ? 從圖中刪除該頂點和所有以它為尾的弧 ? 重復上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止 例 課程代號 課程名稱 先修棵 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 無 C1 C1,C2 C1 C3,C4 C11 C3,C6 無 C9 C9 C1,C9,C10 程序設計基礎 離散數(shù)學 數(shù)據(jù)結構 匯編語言 語言的設計和分析 計算機原理 編譯原理 操作系統(tǒng) 高等數(shù)學 線性代數(shù) 普通物理 數(shù)值分析 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓撲序列： C1C2C3C4C5C7C9C10C11C6C12C8 或 ： C9C10C11C6C1C12C4C2C3C5C7C8 一個 AOV網(wǎng)的拓撲序列不是唯一的 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓撲序列： C1 （ 1） C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓撲序列： C1C2 （ 2） C4 C5 C6 C7 C8 C9 C10 C11 C12 拓撲序列： C1C2C3 （ 3） C5 C6 C7 C8 C9 C10 C11 C12 拓撲序列： C1C2C3C4 （ 4） C6 C8 C10 C11 C12 拓撲序列： C1C2C3C4C5C7C9 C6 C8 C11 C12 拓撲序列： C1C2C3C4C5C7C9 C10 （ 8） C6 C7 C8 C9 C10 C11 C12 拓撲序列： C1C2C3C4C5 （ 5） C6 C8 C9 C10 C11 C12 拓撲序列： C1C2C3C4C5C7 （ 6） C6 C8 C12 拓撲序列： C1C2C3C4C5C7C9 C10C11 （ 9） C8 C12 拓撲序列： C1C2C3C4C5C7C9 C10C11C6 （ 10） C8 拓撲序列： C1C2C3C4C5C7C9 C10C11C6C12 （ 11） 拓撲序列： C1C2C3C4C5C7C9 C10C11C6C12C8 （ 12） – 算法實現(xiàn) ? 以鄰接表作存儲結構 ? 把鄰接表中所有入度為 0的頂點進棧 ? 棧非空時，輸出棧頂元素 Vj并退棧；在鄰接表中查找 Vj的直接后繼 Vk， 把 Vk的入度減 1；若 Vk的入度為 0則進棧 ? 重復上述操作直至?？諡橹埂Ｈ魲？諘r輸出的頂點個數(shù)不是 n， 則有向圖有環(huán)；否則，拓撲排序完畢 在算法中需用定量的描述替代定性的概念： 沒有前驅的頂點 ?? 入度為零的頂點 刪除頂點及以它為尾的弧 ?? 弧頭頂點的入度減 1 為避免每次都要搜索入度為零的頂點，在算法中設置一個“?！?，以保存“入度為零”的頂點。 鄰接表結點： typedef struct node { int vex。 //頂點域 struct node *next。 //鏈域 }JD。 表頭結點： typedef struct tnode { int in。 //入度域 struct node *link。 //鏈域 }TD。 TD g[M]。 //g[0]不用 掃描頂點表，將入度為 0 的頂點入棧； while ( 棧非空 ) { 將棧頂頂點 v彈出并輸出之； 檢查 v的出邊，將每條出邊 v,u終點 u的入度減 1， 若 u的入度變?yōu)?0，則把 u推入棧； } 若輸出的頂點數(shù)小于 n，則輸出“有回路”；否則拓撲 排序正常結束。 拓撲排序算法框架 Status TopologicalSort(ALGraph G){ //有向圖 G采用鄰接表存儲結構 //若 G無回路，則輸出 G的頂點的一個拓撲序列并返回//OK，否則 ERROR。 FindInDegree(G,indegree)。 //對各頂點求入度 indegree[0..vernum1] InitStack(S)。 for ( i=0。 i。 ++i) //建零入度頂點棧 S if (!indegree[i]) Push(S, i)。//入度為零的頂點入棧 count=0。 //對輸出頂點計數(shù) while (! StackEmpty (S)) { Pop(S, i)。 printf(i, [i].data)。 ++count。 //輸出 i號頂點并計數(shù) for (p=[i].Firstarc。 p。 p=pnextarc){ k=padjvex。 // 對 i號頂點的每個鄰接點的 入度減一 if (!(indegree[k])) Push(S,k)。 //若入度為零，則入棧 }//for }//while if (count ) return ERROR。//該有向圖有回路 Else return OK。 }//TopologicalSort – 算法分析 建鄰接表： T(n)=O(e) 搜索入度為 0的頂點的時間： T(n)=O(n) 拓撲排序： T(n)=O(n+e) 3 2 1 0 4 – 算法描述 例 1 2 3 4 5 6 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 3 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ top 1 6 top top 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 3 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 6 top top 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 3 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 0 1 2 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 3 2 1 0 4 1 top p=NULL 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 1 top top 0 1 1 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 top p 0 1 0 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 top p 4 0 1 0 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 p 4 top 0 1 0 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 p 4 top 0 0 0 2 in link 5 5 4 3 ^ ^ ^ vex next 2 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 1 0 4 p 4 top 3 0 0 0 2 in link 5