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