【正文】 }//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。 //若入度為零，則入棧 }//for }//while if (count ) return ERROR。 p=pnextarc){ k=padjvex。 //輸出 i號(hào)頂點(diǎn)并計(jì)數(shù) for (p=[i].Firstarc。 printf(i, [i].data)。//入度為零的頂點(diǎn)入棧 count=0。 i。 //對(duì)各頂點(diǎn)求入度 indegree[0..vernum1] InitStack(S)。 拓?fù)渑判蛩惴蚣? Status TopologicalSort(ALGraph G){ //有向圖 G采用鄰接表存儲(chǔ)結(jié)構(gòu) //若 G無回路，則輸出 G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷?/OK，否則 ERROR。 TD g[M]。 //入度域 struct node *link。 //鏈域 }JD。 鄰接表結(jié)點(diǎn)： typedef struct node { int vex。 ? 拓?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ǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該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ù)上述操作直至?？諡橹埂?估算整個(gè)工程完成必須的最短時(shí)間。： 幾乎所有 工程 都可分為若干個(gè)稱為活動(dòng)的 子工程 ，而這些子工程之間，通常受著一定條件的約束，如某些子工程的開始 必須在 另一子工程完成 之后。實(shí)現(xiàn)對(duì)相同子式的共享，節(jié)省存儲(chǔ)空間。 且 k++。 檢查邊集 E 中 第 i 條權(quán)值最小的邊 (u,v)。 k = i = 0。 考慮問題的出發(fā)點(diǎn) : 為使生成樹上 邊的權(quán)值之和達(dá)到最小 ，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。 ++j) //修改其它頂點(diǎn)的最小邊 if ([k][j].adj closedge[j].lowcost) closedge[j] = { [k], [k][j].adj }。 // 第 k頂點(diǎn)并入 U集 for (j=0。 // 求出加入生成樹的下一個(gè)頂點(diǎn) (k) printf(closedge[k].adjvex, [k])。 ++i) { } 繼續(xù)向生成樹上添加頂點(diǎn) 。 // 初始， U＝ {u} for (i=1。 ++j ) // 輔助數(shù)組初始化 if (j!=k) closedge[j] = { u, [k][j].adj }。 for ( j=0。 // 邊的權(quán)值 } closedge[MAX_VERTEX_NUM]。 一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件 : 2022/3/13 107 設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前 V－ U集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集 U中頂點(diǎn)相連接的代價(jià)最小的邊： struct { VertexType adjvex。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有 n1 個(gè)頂點(diǎn)為止。 算法一：普里姆 （ Prim） 算法 算法二：克魯斯卡爾 ( Kruskal)算法 2022/3/13 104 取圖中任意一個(gè)頂點(diǎn) v 作為生成樹的根，之后往生成樹上添加新的頂點(diǎn) w。 該問題等價(jià)于： 2022/3/13 103 最小樹 MST性質(zhì) ? 假設(shè) N=(V,{E})是一個(gè)連通圖， U是頂點(diǎn)集 V的一個(gè)非空子