拓撲排序(算法與數(shù)據(jù)結(jié)構(gòu)課程設計)

1、拓撲排序 拓撲排序一、問題描述 一、問題描述在 AOV 網(wǎng)中為了更好地完成工程，必須滿足活動之間先后關系，需要將各活動排一個先后次序即為拓撲排序。拓撲排序可以應用于教學計劃的安排，根據(jù)課程之間的依賴關系，制定課程安排計劃。按照用戶輸入的課程數(shù)，課程間的先后關系數(shù)目以及課程間兩兩間的先后關系，程序執(zhí)行后會給出符合拓撲排序的課程安排計劃。二、基本要求 二、基本要求1、選擇合適的存儲結(jié)構(gòu)，建立有向無環(huán)圖，并輸出該圖；2、實現(xiàn)拓撲排序算法；3、

2、運用拓撲排序?qū)崿F(xiàn)對教學計劃安排的檢驗。三、算法思想 三、算法思想1、采用鄰接表存儲結(jié)構(gòu)實現(xiàn)有向圖；有向圖需通過頂點數(shù)、弧數(shù)、頂點以及弧等信息建立。2、拓撲排序算法 void TopologicalSort(ALGraph G) 中，先輸出入度為零的頂點，而后輸出新的入度為零的頂點，此操作可利用棧或隊列實現(xiàn)?？紤]到教學計劃安排的實際情況，一般先學基礎課（入度為零），再學專業(yè)課（入度不為零），與隊列先進先出的特點相符，故采用隊列實現(xiàn)。3、拓

3、撲排序算法 void TopologicalSort(ALGraph G)，大體思想為：1)遍歷有向圖各頂點的入度，將所有入度為零的頂點入隊列；2)隊列非空時，輸出一個頂點，并對輸出的頂點數(shù)計數(shù)；3)該頂點的所有鄰接點入度減一，若減一后入度為零則入隊列；4)重復 2)、3)，直到隊列為空，若輸出的頂點數(shù)與圖的頂點數(shù)相等則該圖可拓撲排序，否則圖中有環(huán)。4、要對教學計劃安排進行檢驗，因此編寫了檢測用戶輸入的課程序列是否是拓撲序列的算法 vo

4、id TopSortCheck(ALGraph G)，大體思想為：1)用戶輸入待檢測的課程序列，將其存入數(shù)組；2)檢查課程序列下一個元素是否是圖中的頂點（課程），是則執(zhí)行 3)，否則輸出“課程 XX 不存在”并跳出；3)判斷該頂點的入度是否為零，是則執(zhí)行 4)，否則輸出“入度不為零”并跳出；4)該頂點的所有鄰接點入度減一；5)重復 2)、3)、4)直到課程序列中所有元素均被遍歷，則該序列是拓撲序列，否則不是拓撲序列。功能：元素出隊列參數(shù)

5、：*Q 待操作的隊列；*e 記錄出隊列元素的變量2、有向圖 、有向圖(DAG) (DAG)鄰接表存儲結(jié)構(gòu) 鄰接表存儲結(jié)構(gòu)(ALG) (ALG)的操作 的操作1) int LocateVex(ALGraph G,VertexType v)功能：頂點在頭結(jié)點數(shù)組中的定位參數(shù)：G 待操作的圖；v 要在圖中定位的頂點返回值：頂點存在則返回在頭結(jié)點數(shù)組中的下標；否則返回圖的頂點數(shù)2) int CreateGraph(ALGraph *G)功能：建

6、立圖函數(shù)內(nèi)包含了由用戶輸入頂點數(shù)、弧數(shù)、頂點以及弧的操作參數(shù)：*G 待操作的圖返回值：圖建立成功返回 1；圖建立失敗返回 0錯誤判斷：包含頂點數(shù)、弧數(shù)是否正確的判斷；包含用戶輸入的弧的頂點是否存在的判斷3) void PrintGraph(ALGraph G)功能：輸出有向圖參數(shù)：G 待輸出的圖4) int CreateGraph2(ALGraph *G)功能：建立預置課程圖（輸出函數(shù)內(nèi)預置課程信息，并自動建立有向圖）參數(shù)：*G 待操作

7、的圖返回值：圖建立成功返回 1；圖建立失敗返回 0錯誤判斷：包含頂點數(shù)、弧數(shù)是否正確的判斷包含弧的頂點是否存在的判斷5) void PrintGraph2(ALGraph G)功能：輸出預置課程圖參數(shù)：G 待輸出的圖3、拓撲排序及拓撲檢測算法 、拓撲排序及拓撲檢測算法1) void TopologicalSort(ALGraph G)功能：實現(xiàn)拓撲排序參數(shù)：G 待進行拓撲排序的圖錯誤判斷：包含有向圖是否有環(huán)的判斷2) void TopS