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

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

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

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

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

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

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

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

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