西安郵電大學(xué)（計(jì)算機(jī)學(xué)院）數(shù)據(jù)結(jié)構(gòu)課內(nèi)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：圖的建立與遍歷專業(yè)名稱：網(wǎng)絡(luò)工程班級(jí)：網(wǎng)絡(luò)1502學(xué)生姓名：李軒學(xué)號(hào)（8位）：04152044指導(dǎo)教師：王春梅實(shí)驗(yàn)日期：2016年12月13日實(shí)驗(yàn)?zāi)康募皩?shí)驗(yàn)環(huán)境1、理解并掌握?qǐng)D的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)——鄰接矩陣、鄰接表2、掌握?qǐng)D的構(gòu)造方法3、掌握?qǐng)D的鄰接矩陣、鄰接表存儲(chǔ)方式下基本操作的實(shí)現(xiàn)算法4、掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先原理5.實(shí)驗(yàn)環(huán)境：MicrosoftVisualC++6.0實(shí)驗(yàn)內(nèi)容以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先和廣度優(yōu)先遍歷以指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問(wèn)序列：1、輸入頂點(diǎn)數(shù)、邊數(shù)、每個(gè)頂點(diǎn)的值以及每一條邊的信息，構(gòu)造一個(gè)無(wú)向圖G，并用鄰接矩陣存儲(chǔ)改圖。2、輸入頂點(diǎn)數(shù)、邊數(shù)、每個(gè)頂點(diǎn)的值以及每一條邊的信息，構(gòu)造一個(gè)無(wú)向圖G，并用鄰接表存儲(chǔ)該圖3、深度優(yōu)先遍歷第一步中構(gòu)造的圖G，輸出得到的節(jié)點(diǎn)序列4、廣度優(yōu)先遍歷第一步中構(gòu)造的圖G，輸出得到的節(jié)點(diǎn)序列三．方案設(shè)計(jì)深度優(yōu)先算法：計(jì)算機(jī)程序的一種編制原理，就是在一個(gè)問(wèn)題出現(xiàn)多種可以實(shí)現(xiàn)的方法和技術(shù)的時(shí)候，應(yīng)該優(yōu)先選擇哪個(gè)更合適的，也是一種普遍的邏輯思想，此種思想在運(yùn)算的過(guò)程中，用到計(jì)算機(jī)程序的一種遞歸的思想。度優(yōu)先搜索算法：又稱廣度優(yōu)先搜索，是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹(shù)算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開(kāi)并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說(shuō)，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。以臨接鏈表作為存儲(chǔ)結(jié)構(gòu)，結(jié)合其存儲(chǔ)特點(diǎn)和上面兩種算法思想，給出兩種遍歷步驟：（1）既然圖中沒(méi)有確定的開(kāi)始頂點(diǎn)，那么可從圖中任一頂點(diǎn)出發(fā)，不妨按編號(hào)的順序，先從編號(hào)小的頂點(diǎn)開(kāi)始。（2）要遍歷到圖中所有頂點(diǎn)，只需多次調(diào)用從某一頂點(diǎn)出發(fā)遍歷圖的算法。所以，下面只考慮從某一頂點(diǎn)出發(fā)遍歷圖的問(wèn)題。（3）為了在遍歷過(guò)程中便于區(qū)分頂點(diǎn)是否已經(jīng)被訪問(wèn)，設(shè)置一個(gè)訪問(wèn)標(biāo)志數(shù)組visited[n]，n為圖中頂點(diǎn)的個(gè)數(shù)，其初值為0，當(dāng)被訪問(wèn)過(guò)后，其值被置為1。（4）這就是遍歷次序的問(wèn)題，圖的遍歷通常有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方式，這兩種遍歷次序?qū)o(wú)向圖和有向圖都適用。深度優(yōu)先遍歷從圖中某頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷的基本思想是：五．總結(jié)（1）通過(guò)這次實(shí)驗(yàn)，使我基本上掌握了圖的存儲(chǔ)和遍歷，讓我弄清楚了如何用鄰接矩陣和鄰接鏈表對(duì)圖進(jìn)行存儲(chǔ)（2）深度優(yōu)先遍歷和廣度優(yōu)先遍歷都有著各自的優(yōu)點(diǎn)，通過(guò)程序逐步調(diào)試，可以慢慢的理解這兩種遍歷方法的內(nèi)涵和巧妙之處。（3）)實(shí)驗(yàn)過(guò)程中，總體來(lái)說(shuō)還算順暢，但在編寫過(guò)程中，要養(yǎng)成良好的編程習(xí)慣，以免出錯(cuò)后浪費(fèi)大量的時(shí)間在查錯(cuò)上。（4）圖的存儲(chǔ)結(jié)構(gòu)相比表和樹(shù)都要復(fù)雜，其操作過(guò)程也較難進(jìn)行掌握。僅僅是創(chuàng)建圖的存儲(chǔ)結(jié)構(gòu)便分為矩陣、臨接鏈表、十字鏈表等，對(duì)于每一種存儲(chǔ)結(jié)構(gòu)又分為有向與無(wú)向之分。然而，深度優(yōu)先和廣度優(yōu)先是兩種算法，其算法思想并不依賴與元素的存儲(chǔ)方式，也就是說(shuō)算法思想不會(huì)因?yàn)榇鎯?chǔ)結(jié)構(gòu)的改變而發(fā)生改