圖的深度和廣度優(yōu)先搜索遍歷

《圖的深度和廣度優(yōu)先搜索遍歷》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、吉林工業(yè)職業(yè)技術(shù)學(xué)院（數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)報告）（2012~2013學(xué)年第1學(xué)期）實(shí)訓(xùn)地點(diǎn):軟件開發(fā)實(shí)訓(xùn)室指導(dǎo)教師:趙秀艷、劉文宏專業(yè)班級:計(jì)算機(jī)3111學(xué)生姓名:36號折春雨2012年12月13日目錄實(shí)訓(xùn)項(xiàng)目1實(shí)訓(xùn)目的1設(shè)計(jì)分析1設(shè)計(jì)方案2詳細(xì)設(shè)計(jì)4運(yùn)行調(diào)試12實(shí)訓(xùn)心得15參考文獻(xiàn)16數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)報告實(shí)訓(xùn)項(xiàng)目1.個人項(xiàng)目：圖的深度和廣度優(yōu)先搜索遍歷問題描述：給定一個無向圖，利用鄰接矩陣或鄰接表進(jìn)行存儲，然后按照深度和廣度進(jìn)行遍歷。要求：以吉林省的城市：白城、松原、長春、公主嶺、四平、遼源、吉林市、通化、白山、延吉所構(gòu)成的地理圖為無向圖。求以吉林市為出發(fā)點(diǎn)深度和廣度優(yōu)先搜索

2、遍歷序列。2.小組項(xiàng)目：學(xué)生成績管理系統(tǒng)問題描述：編寫一個學(xué)生成績管理系統(tǒng)，實(shí)現(xiàn)計(jì)算每個學(xué)生的總分、平均分，班級的總分、平均分，按分?jǐn)?shù)高低排序。包含插入、刪除、修改、查詢、顯示模塊。要求：成績包括本學(xué)期所開設(shè)的課程（數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)、數(shù)據(jù)庫原理、……），采用菜單程序編寫。包含插入、刪除、修改、查詢、顯示模塊。實(shí)訓(xùn)目的通過本次實(shí)訓(xùn)，能夠進(jìn)一步鞏固、掌握程序設(shè)計(jì)基礎(chǔ)和數(shù)據(jù)結(jié)構(gòu)課程的基本知識、基本技能。運(yùn)用算法分析與程序設(shè)計(jì)的一般方法進(jìn)行實(shí)際項(xiàng)目的開發(fā)。本項(xiàng)目需要具備熟練的數(shù)組和線性表知識，具備程序編寫、調(diào)試的基本能力，具有一定的文字表達(dá)和報告撰寫能力，具備辦公軟件使

3、用能力。設(shè)計(jì)分析1.個人項(xiàng)目：圖的深度和廣度優(yōu)先搜索遍歷圖示一種較線性表和樹更復(fù)雜的結(jié)構(gòu)，在無向圖圖的結(jié)構(gòu)中，節(jié)點(diǎn)之間的關(guān)系可以使任意的，無向圖是指任意兩個定點(diǎn)之間的連線時沒有方向的，圖中兩個數(shù)據(jù)元素之間都可以相關(guān)。所以，首先選擇適合的存儲結(jié)構(gòu)完成圖的建立，我們采用棧來存儲。其次是建立圖的鄰接矩陣存儲，鄰接矩陣表示法也稱為數(shù)組表示法，就是用一位數(shù)組存儲途中的定點(diǎn)信息。最后，完成圖的深度和廣度優(yōu)先遍歷。深度優(yōu)先遍歷就是從某個頂點(diǎn)出發(fā)，沿著它的一條路徑不斷深入地訪問圖上的頂點(diǎn)，并按訪問的次序輸出所有頂點(diǎn)。廣度優(yōu)先遍歷類似于圖的按層次遍歷的過程。然后輸出遍歷序列。2.小組

4、項(xiàng)目：學(xué)生成績管理系統(tǒng)學(xué)生成績管理系統(tǒng)主要功能是對學(xué)生信息進(jìn)行加工和處理，根據(jù)任務(wù)要求，系統(tǒng)要完成學(xué)生信息的采集，信息的維護(hù)，信息查詢和報表輸出等操作，因此可將系統(tǒng)的開發(fā)過程分為系統(tǒng)設(shè)計(jì)，學(xué)生數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，設(shè)計(jì)系統(tǒng)框架，學(xué)生數(shù)據(jù)的存儲與重用，系統(tǒng)維護(hù)設(shè)計(jì)，數(shù)據(jù)查詢，數(shù)據(jù)統(tǒng)計(jì)，報表輸出八個任務(wù)。首先確定要處理的對象并對其進(jìn)行描述，即畫出數(shù)據(jù)結(jié)構(gòu)列表，班級學(xué)生成績管理系統(tǒng)要處理的對象是學(xué)生。然后按照系統(tǒng)功能的總體要求進(jìn)行程序編制。整個系統(tǒng)還需要具有以下功能：維護(hù)功能，查詢功能，統(tǒng)計(jì)功能，報表輸出功能，存儲和重用功能。設(shè)計(jì)方案1.個人項(xiàng)目：圖的深度和廣度優(yōu)先搜索遍歷把問題

5、分成三個部分：一是建立無向圖，運(yùn)用棧來建立；二是將無向圖進(jìn)行鄰接矩陣存儲；三是將圖進(jìn)行深度和廣度優(yōu)先遍歷。實(shí)現(xiàn)第一個算法思想：建立一個隊(duì)列，將無向圖的節(jié)點(diǎn)數(shù)和邊數(shù)輸入，再將節(jié)點(diǎn)的內(nèi)容和邊指針輸入，建立無向圖。實(shí)現(xiàn)第二個算法思想：將建立好的無向圖進(jìn)行鄰接矩陣存儲，即矩陣的形式。實(shí)現(xiàn)第三個算法思想：無向圖的深度優(yōu)先遍歷是選定任意一個節(jié)點(diǎn)作為起點(diǎn)，依次遍歷和此節(jié)點(diǎn)有聯(lián)系的節(jié)點(diǎn)，直至最后沒有在與此節(jié)點(diǎn)有聯(lián)系的節(jié)點(diǎn)為止。如果圖中還有未被訪問的節(jié)點(diǎn)，則選定任意未被遍歷的節(jié)點(diǎn)作為起始點(diǎn)，直至圖中所有節(jié)點(diǎn)都被遍歷。無向圖的廣度優(yōu)先遍歷類似于二叉樹的按層次遍歷。假設(shè)從圖中某定點(diǎn)V出發(fā)

6、，在訪問了V之后一次訪問V的哥哥未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)一次訪問它們的鄰接點(diǎn)，直至圖中所有節(jié)點(diǎn)均被訪問2.小組項(xiàng)目：學(xué)生成績管理系統(tǒng)如圖1所示學(xué)生管理系統(tǒng)錄入學(xué)生成績導(dǎo)入學(xué)生成績查詢學(xué)生成績刪除學(xué)生記錄追加學(xué)生記錄顯示學(xué)生成績統(tǒng)計(jì)學(xué)生成績保存輸入記錄成績進(jìn)行排序退出個人總分和平均分單科平均分總分最高分總分最低分按學(xué)生學(xué)號排序按學(xué)生姓名排序按數(shù)據(jù)結(jié)構(gòu)成績進(jìn)行排序按計(jì)算機(jī)成績排序按數(shù)據(jù)庫成績排序圖一學(xué)生成績管理界面（1）建立一個明了的管理菜單。<1>錄入學(xué)生成績<2>導(dǎo)入學(xué)生成績<3>查詢學(xué)生成績<4>刪除學(xué)生記錄、追加學(xué)生記錄<5>顯示學(xué)生記錄<6

7、>統(tǒng)計(jì)學(xué)生成績<7>保存輸入記錄<8>成績進(jìn)行排序<9>退出。（2）使操作人員很容易的完成對學(xué)生成績的查詢、修改、添加、保存和導(dǎo)入。（3）在統(tǒng)計(jì)與排序這一模塊中又可分為多個可操作模塊，大大增加了此系統(tǒng)的功能，如統(tǒng)計(jì)學(xué)生成績中可分為按個人總分和平均分統(tǒng)計(jì)、按單科平均分統(tǒng)計(jì)、按總分最高分和總分最低分統(tǒng)計(jì)；而在排序這一模塊中又分為按學(xué)生學(xué)號、學(xué)生姓名、學(xué)生各單科成績排序，大大減少了工作量。（4）和以往系統(tǒng)不同，在它的模塊中新增加拉保存與導(dǎo)入記錄這兩個模塊，運(yùn)用這兩個模塊可以將外界數(shù)據(jù)導(dǎo)入系統(tǒng)中或?qū)⒈鞠到y(tǒng)中的數(shù)據(jù)導(dǎo)入外界進(jìn)行保存工作，以防數(shù)據(jù)丟失。（5）對要查詢的數(shù)據(jù)要