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