20拓撲排序和關(guān)鍵路徑-展示頁
2024-08-09 15:49本頁面
【正文】 for (v=0。 拓撲排序 方法 2 a c g b d h f e b h a c d g f e 此圖的一個拓撲序列為： 退出 DFS函數(shù)順序： e f g d c a h b 拓撲排序 方法 2 最先退出 DFS函數(shù)的頂點是出度為零的頂點，為拓撲排序序列中最后一個頂點。 // 弧頭頂點的入度減 1 if (!indegree[w]) Push(S, w)。 w。 printf(v)。 } 拓撲排序 算法 Status ToplogicalSort(ALGragh G){ ……………… while (!EmptyStack(S)) { Pop(S, v)。 //對輸出頂點計數(shù) while (!EmptyStack(S)) { ………… }//while if (count) return ERROR。i++){if(!indegree[i]) push(S,i)。 for(i=0。 拓撲排序 方法 1 a c g b d h f e b h a c d g f e 拓撲序列 ： 在算法中需要用定量的描述替代定性的概念 沒有前驅(qū)的頂點 入度為零的頂點 刪除頂點及以它為尾的弧 弧頭頂點的入度減 1 拓撲排序 方法 1 Status ToplogicalSort(ALGragh G){ FindInDegree(G, indegree)。 從有向圖中刪去此頂點以及所有以它為尾的弧 。 AOV網(wǎng)（ Activity On Vertex NetWork） AOV網(wǎng)中不應該出現(xiàn)有向環(huán)：如果存在環(huán)，則某項活動以自己為先決條件， 拓撲排序 B D A C 可求得拓撲有序序列 ： A B C D 或 A C B D B D A C 不能求得它的拓撲有序序列。 偏序 全序 拓撲排序 按照有向圖給出的次序關(guān)系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點，則可以人為加上任意的次序關(guān)系。 } // DFST 公用表達式 用樹表示表達式： ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) * * * * * + + + + + c c c d d d e e b b a 公用表達式 多次出現(xiàn)的變量和表達式通過共用，減少出現(xiàn)次數(shù) * * * * * + + + + + c c c d d d e e b b a * * * * + + + c d e b a 拓撲排序 一、定義 由集合上的一個偏序關(guān)系得到集合的全序關(guān)系的操作 偏序：自反的、反對稱的、傳遞的 全序： R是集合 X上的偏序，對于集合 X中的任何元素 x,y，如果都有 xRy或者 yRx,則稱 R是全序關(guān)系 拓撲排序 B D A C B D A C ?偏序就是集合中的部分成員可以比較。 } Pop(S, v)。 w=NextAdjVex(G,v,w)){ {if (w in S) then return(FALSE)。 for(w=FirstA
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1