數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--圖的遍歷-在線(xiàn)瀏覽
2025-08-09 01:27本頁(yè)面
【正文】 V4 的鄰接點(diǎn) V8。得到的頂點(diǎn)訪(fǎng)問(wèn)序列為： V1— V2— V3— V4— V5— V6— V7— V8 第二章 需求分析 要求設(shè)計(jì)類(lèi)（或類(lèi)模板）來(lái)描述圖，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)： ? 輸入圖、輸出圖 ? 求圖中頂點(diǎn) V 的第一個(gè)鄰接點(diǎn) ? 求圖中頂點(diǎn) V 的下一個(gè)鄰接點(diǎn) ? 深度優(yōu)先遍歷圖 ? 廣度優(yōu)先遍歷圖 并設(shè)計(jì)主函數(shù)測(cè)試該類(lèi)（或類(lèi)模板）。 輸入圖： 首先需輸入頂點(diǎn)數(shù)及邊數(shù)，然后根據(jù)頂點(diǎn)數(shù)確定矩陣大小，再根據(jù)邊數(shù)輸入對(duì)應(yīng)的兩點(diǎn)及權(quán)值 。 求圖中頂點(diǎn) V的第一個(gè)鄰接點(diǎn)： 通過(guò)輸入頂點(diǎn) v就可以輸出其第一個(gè)鄰接點(diǎn) 。 深度優(yōu)先遍歷圖： 由 所述可知，圖的深度優(yōu)先遍歷顯然是一個(gè)遞歸的過(guò)程。 廣度優(yōu)先遍歷圖： 由 所述可知，和深度優(yōu)先遍歷類(lèi)似，在廣度優(yōu)先遍歷的過(guò)程中也需要一個(gè)訪(fǎng)問(wèn)標(biāo)志數(shù)組。 功能視圖 本程序主要包含六個(gè)功能，即圖的創(chuàng)建，輸出，訪(fǎng)問(wèn) 頂點(diǎn) V 的第一個(gè)和下一個(gè)鄰接點(diǎn)，以及深搜和廣搜。 無(wú)向圖的實(shí)現(xiàn)創(chuàng)建無(wú)向圖 輸出無(wú)向圖訪(fǎng)問(wèn)鄰接頂點(diǎn)訪(fǎng)問(wèn)下一個(gè)鄰接頂點(diǎn)深度優(yōu)先遍歷廣度優(yōu)先遍歷 圖 功能 視 圖 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)論文 7 第四 章 類(lèi)的設(shè)計(jì) GraphUDN 類(lèi)的設(shè)計(jì) GraphUDN 類(lèi)包括： ，其中有頂點(diǎn)訪(fǎng)問(wèn)標(biāo)志，頂點(diǎn)集，鄰接矩陣，頂點(diǎn)數(shù)就邊數(shù) ，其中有創(chuàng)建輸出圖，輸出頂點(diǎn) V 的第一個(gè)和下一個(gè)鄰接點(diǎn)，以及深搜和廣搜。 void create()。 //輸出圖 intfirstAdjvex(int v)。 //輸出下一個(gè)鄰接頂點(diǎn) void dfsTravel()。 void bfsTravel()。 //頂點(diǎn)訪(fǎng)問(wèn)標(biāo)志 int vexs[MAX_VERTEX_NUM]。 //鄰接矩陣 intvexNum。 }。 具體如下： class Queue { public: Queue (){ for(inti = 0。 i++){ ques[i] = 1。 void add(intele)。 //出隊(duì) boolisEmpty()。 }。 圖 工程視圖 圖 類(lèi)視圖 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)論文 10 主要算法的流程圖 主函數(shù)的流程圖 本程序的主函數(shù)中，首先定義及初始化所需變量，實(shí)例化對(duì)象，然后輸出菜單界面供用戶(hù)選擇，通過(guò) switch 函數(shù)實(shí)現(xiàn)選擇功能，選擇項(xiàng)目包括創(chuàng)建無(wú)向圖，輸出無(wú)向圖，輸出頂點(diǎn) V 的第一個(gè)鄰接點(diǎn)，輸出頂點(diǎn) V 的下一個(gè)鄰接點(diǎn)，深搜，廣搜以及退出。 開(kāi) 始判 斷 操 作 號(hào)創(chuàng) 建 無(wú) 向圖1輸 出 頂 點(diǎn) v 的 第一 個(gè) 鄰 接 頂 點(diǎn)輸 出 無(wú) 向圖輸 出 頂 點(diǎn) v 的 下一 個(gè) 鄰 接 頂 點(diǎn)深 度 優(yōu) 先遍 歷 圖廣 度 優(yōu) 先遍 歷 圖23456用 戶(hù) 輸 入操 作 號(hào)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í) 例 化 對(duì) 象 g r u p圖 主函數(shù)流程圖 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)論文 11 深搜流程圖 深度優(yōu)先遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程，具體如圖 所示： 開(kāi)始初始化訪(fǎng)問(wèn)標(biāo)志v i s i t e d判斷頂點(diǎn) i是否被訪(fǎng)問(wèn) 是 結(jié)束否V i s i t e d [ i ] 賦值 t r ue訪(fǎng)問(wèn) i頂點(diǎn)獲取v e x s [ i ] d 的第一個(gè)鄰接頂點(diǎn) w判斷是否被訪(fǎng)問(wèn)是獲取v e x s [ i ] d 的下一個(gè)鄰接頂點(diǎn) w否V i s i t e d [ w ]賦值 t r ue訪(fǎng)問(wèn) w 頂點(diǎn) 圖 深度優(yōu)先算法遍歷流程圖 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)論文 12 廣搜流程圖 廣度優(yōu)先遍歷的過(guò)程實(shí)質(zhì)上就是 通過(guò)邊找鄰接點(diǎn)的過(guò)程 ，具體如圖 所示： 開(kāi)始訪(fǎng)問(wèn)標(biāo)志 vi s i t e d [] 初始化 ， 實(shí)例化隊(duì)列q u e判斷頂點(diǎn)是否被訪(fǎng)問(wèn)否V is it e d [ i ]置 t r u e輸出頂點(diǎn)頂點(diǎn)入隊(duì)隊(duì)列是否為空出隊(duì)并賦值給 u獲取第一個(gè)鄰接頂點(diǎn)判斷鄰接頂點(diǎn)是否存在存在判斷是否被訪(fǎng)問(wè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)先算法遍歷流程圖 第 六 章 測(cè)試 菜單界面 當(dāng)運(yùn)行程序后，首先出現(xiàn)菜單界面，包括程序提供的六個(gè)功能，用戶(hù)通過(guò)選擇功能前的數(shù)字，即可實(shí)現(xiàn)相應(yīng)的功能。 圖 菜單界面 創(chuàng)建無(wú)向網(wǎng) 接下來(lái)應(yīng)當(dāng)創(chuàng)建一個(gè)圖，通過(guò)輸入頂點(diǎn)數(shù)，邊數(shù)，鄰接點(diǎn)及權(quán)值即可實(shí)現(xiàn)。輸入如圖 所示 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)論文 14 圖 創(chuàng)建圖 輸出圖 當(dāng)輸入圖以后，實(shí)際圖是以鄰接矩陣的形式存在的，所以輸出圖的時(shí)候輸出的就是鄰接矩陣，為方便理解，還輸出了鄰接點(diǎn)及對(duì)應(yīng)邊的權(quán)值。 圖 輸出圖 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)論文 15 輸出 頂點(diǎn) V 的第一個(gè)鄰接點(diǎn) 實(shí)際上輸出頂點(diǎn) V 的第一個(gè)鄰接點(diǎn)并無(wú)太大的意義，因?yàn)檫@個(gè)函數(shù)主要是為了實(shí)現(xiàn)深搜和廣搜功能 而編寫(xiě)的，但在此處，為了更加便于普通用戶(hù)理解此程序，特意添加了此操作，具體操作及結(jié)果如圖 所示。 圖 輸出 V 的下一個(gè)鄰接點(diǎn) 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)論文 16 深搜 深度優(yōu)先遍歷圖相當(dāng)于樹(shù)的先序遍歷，具體原理見(jiàn) 所述，針對(duì)本次測(cè)試所創(chuàng)建的圖，它的深度優(yōu)先遍歷結(jié)果如 圖 所示。 圖 廣度優(yōu)先搜索 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)論文 17 第 七 章 總結(jié) 轉(zhuǎn)眼之間，為期兩周的課程設(shè)計(jì)就結(jié)束了，通過(guò)這兩個(gè)星期的課程設(shè)計(jì)，我發(fā)現(xiàn)了自己很多不足的地方，知識(shí)點(diǎn)也存在很多漏洞，還接觸了一些以前沒(méi)有了解的東西，讓我明白了基礎(chǔ)知識(shí)的重要性，以及實(shí)踐能力的重要性！因?yàn)榛A(chǔ)知識(shí)的不扎實(shí)讓我在這次課程設(shè)計(jì)中走了許多彎路，不過(guò)我認(rèn)為是值得的，至少它讓我明白了，付出與回報(bào)是成
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1