數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--圖的遍歷(編輯修改稿)
2025-07-12 01:27 本頁面
【文章內(nèi)容簡介】 aph()。 //輸出圖 intfirstAdjvex(int v)。 //輸出 v 的第一個鄰接頂點 intnextAdjvex(int v, int w)。 //輸出下一個鄰接頂點 void dfsTravel()。 //深度優(yōu)先遍歷 voiddfs(int v)。 void bfsTravel()。 //廣度優(yōu)先遍歷 private: bool visited[MAX_VERTEX_NUM]。 //頂點訪問標志 int vexs[MAX_VERTEX_NUM]。 //頂點集 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 //鄰接矩陣 intvexNum。 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 8 intarcNum。 }。 Queue 類的設(shè)計 Queue 類 作為一個輔助的功能類，主要包括入隊，出隊及隊列的判空。 具體如下： class Queue { public: Queue (){ for(inti = 0。 i MAX_VERTEX_NUM。 i++){ ques[i] = 1。 } }。 void add(intele)。 //入隊 int get()。 //出隊 boolisEmpty()。 //判斷隊列是否為空 private: intques[MAX_VERTEX_NUM]。 }。 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 9 第 五 章 詳細設(shè)計 工程視圖 和類視圖 本程序運行時的工程視圖及類視圖如圖 , 所示。 圖 工程視圖 圖 類視圖 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 10 主要算法的流程圖 主函數(shù)的流程圖 本程序的主函數(shù)中，首先定義及初始化所需變量，實例化對象，然后輸出菜單界面供用戶選擇，通過 switch 函數(shù)實現(xiàn)選擇功能，選擇項目包括創(chuàng)建無向圖，輸出無向圖，輸出頂點 V 的第一個鄰接點，輸出頂點 V 的下一個鄰接點，深搜，廣搜以及退出。具體如圖 所示。 開 始判 斷 操 作 號創(chuàng) 建 無 向圖1輸 出 頂 點 v 的 第一 個 鄰 接 頂 點輸 出 無 向圖輸 出 頂 點 v 的 下一 個 鄰 接 頂 點深 度 優(yōu) 先遍 歷 圖廣 度 優(yōu) 先遍 歷 圖23456用 戶 輸 入操 作 號O t h e rg r a p . c r e a t e ( )g r a p . f i r s t A d j v e x (v e x 1 ) + 1g r a p . n e x t A d j v e x( v e x 1 , w 1g r a p . d f s T r a v e l ( ) g r a p . b f s T r a v e l ( )g r a p . s h o w G r a p h( )初 始 化 變 量f l a g , s e l e c t , v e x , w , r e su l t實 例 化 對 象 g r u p圖 主函數(shù)流程圖 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 11 深搜流程圖 深度優(yōu)先遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程，具體如圖 所示： 開始初始化訪問標志v i s i t e d判斷頂點 i是否被訪問 是 結(jié)束否V i s i t e d [ i ] 賦值 t r ue訪問 i頂點獲取v e x s [ i ] d 的第一個鄰接頂點 w判斷是否被訪問是獲取v e x s [ i ] d 的下一個鄰接頂點 w否V i s i t e d [ w ]賦值 t r ue訪問 w 頂點 圖 深度優(yōu)先算法遍歷流程圖 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 12 廣搜流程圖 廣度優(yōu)先遍歷的過程實質(zhì)上就是 通過邊找鄰接點的過程 ，具體如圖 所示： 開始訪問標志 vi s i t e d [] 初始化 ， 實例化隊列q u e判斷頂點是否被訪問否V is it e d [ i ]置 t r u e輸出頂點頂點入隊隊列是否為空出隊并賦值給 u獲取第一個鄰接頂點判斷鄰接頂點是否存在存在判斷是否被訪問否V is it e d [ i ]置 t r u e輸出頂點頂點入隊是 結(jié)束不存在是 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 13 圖 廣度優(yōu)先算法遍歷流程圖 第 六 章 測試 菜單界面 當運行程序后，首先出現(xiàn)菜單界面，包括程序提供的六個功能，用戶通過選擇功能前的數(shù)字，即可實現(xiàn)相應(yīng)的功能。具體如圖 所示。 圖 菜單界面 創(chuàng)建無向網(wǎng) 接下來應(yīng)當創(chuàng)建一個圖，通過輸入頂點數(shù)，邊數(shù)，鄰接點及權(quán)值即可實現(xiàn)。在本次測試中，建立的是一個 8 個頂點， 9 條邊的且所有邊的權(quán)值均為 1 的無向網(wǎng)。輸入如圖 所示 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 14 圖 創(chuàng)建圖 輸出圖 當輸入圖以后，實際圖是以鄰接矩陣的形式存在的，所以輸出圖的時候輸出的就是鄰接矩陣，為方便理解，還輸出了鄰接點及對應(yīng)邊的權(quán)值。輸出結(jié)果如圖 所示。 圖 輸出圖 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 15 輸出 頂點 V 的第一個鄰接點 實際上輸出頂點 V 的第一個鄰接點并無太大的意義，因為這個函數(shù)主要是為了實現(xiàn)深搜和廣搜功能 而編寫的，但在此處，為了更加便于普通用戶理解此程序，特意添加了此操作，具體操作及結(jié)果如圖 所示。 圖 輸出 V 的第一個鄰接點 輸出 頂點 V 的下一個鄰接點 如同 節(jié)所述，輸出頂點 V 的下一個鄰接點也并無太大意義，同樣是為了便于普通用戶理解，具體操作及結(jié)果如圖 所示。 圖 輸出 V 的下一個鄰接點 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 16 深搜 深度優(yōu)先遍歷圖相當于樹的先序遍歷，具體原理見 所述，針對本次測試所創(chuàng)建的圖，它的深度優(yōu)先遍歷結(jié)果如 圖 所示。 圖 深度優(yōu)先搜索 廣搜 廣度優(yōu)先遍歷圖相當于樹的層次遍歷，具體原理見 所述，針對本次測試所創(chuàng)建的圖，它的廣度優(yōu)先遍歷結(jié)果如圖 所示。 圖 廣度優(yōu)先搜索 內(nèi)蒙古科技大學(xué)課程設(shè)計論文 17 第 七 章 總結(jié) 轉(zhuǎn)眼之間，為期兩周的課程設(shè)計就結(jié)束了，通過這兩個星期的課程設(shè)計，我發(fā)現(xiàn)了自己很多不足的地方，知識點也存在很多漏洞，還接觸了一些以前沒有了解的東西，讓我明白了基礎(chǔ)知識的重要性，以及實踐能力的重要性！因為基礎(chǔ)知識的不扎實讓我在這次課
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1