拓撲排序和關(guān)鍵路徑(編輯修改稿)
2025-06-14 00:41 本頁面
【文章內(nèi)容簡介】 ∧ 2 3 ∧ 3 5 ∧ A B C D E F B E 0 C2 1 AOV網(wǎng)應用：拓撲排序 25 拓撲排序 0 1 2 3 4 5 in vertex firstarc 3 A ∧ 0 B 0 C 2 D 0 E 1 F ∧ 0 3 ∧ 0 0 5 ∧ 2 3 ∧ 3 5 ∧ A B C D F B C 2 1 AOV網(wǎng)應用：拓撲排序 26 拓撲排序 0 1 2 3 4 5 in vertex firstarc 2 A ∧ 0 B 0 C 1 D 0 E 1 F ∧ 0 3 ∧ 0 0 5 ∧ 2 3 ∧ 3 5 ∧ A B D F B D0 1 AOV網(wǎng)應用：拓撲排序 27 拓撲排序 0 1 2 3 4 5 in vertex firstarc 1 A ∧ 0 B 0 C 0 D 0 E 1 F ∧ 0 3 ∧ 0 0 5 ∧ 2 3 ∧ 3 5 ∧ A D F 0 0 A F AOV網(wǎng)應用：拓撲排序 28 拓撲排序 0 1 2 3 4 5 in vertex firstarc 0 A ∧ 0 B 0 C 0 D 0 E 0 F ∧ 0 3 ∧ 0 0 5 ∧ 2 3 ∧ 3 5 ∧ A F A F AOV網(wǎng)應用：拓撲排序 29 1. ?；蜿犃?S初始化；累加器 count初始化； 2. 掃描頂點表 ， 將沒有前驅(qū)的頂點壓?；蛉腙牐? 3. 當?；蜿犃?S非空時循環(huán) 退出 vj棧頂或隊首元素；輸出 vj；累加器加 1 將頂點 vj的各個鄰接點的入度減 1； 將新的入度為 0的頂點入?；蛉腙?； 4. if (countvertexNum) 輸出有回路信息； 拓撲排序算法 —— 偽代碼 AOV網(wǎng)應用：拓撲排序 作業(yè) : 請編程求 AOV網(wǎng)的拓撲排序。 30 template class ElemType StatusCode TopSort(const AdjMatrixDirGraphElemType amp。g) // 初始條件：存在有向圖 g // 操作結(jié)果：如 g無回路 ,則輸出 g的頂點的一個拓撲序列 , // 并返回 SUCCESS,否則返回 FAIL { int *indegree = new int[()]。 //入度數(shù)組 LinkQueueint q。 // 隊列 int count = 0。 StatIndegree(g, indegree)。 // 統(tǒng)計頂點的入度 for (int v = 0。 v ()。 v++) { // 遍歷頂點 if (indegree[v] == 0) (v)。// 建立入度為 0的頂點隊列 } 31 while (!()) { // 隊列非空 int v1。 (v1)。 // 取出一個入度為 0的頂點 cout v1 。 count++。 // 對輸出頂點進行記數(shù) for (int v2 = (v1)。 v2 != 1。 v2 = (v1, v2)) { // v2為 v1的一個鄰接點 if (indegree[v2] == 0)//鄰接點入度減 1 (v2)。//入度為 0,v2入隊 }。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1