數(shù)據(jù)結(jié)構(gòu)實驗報告圖的遍歷

《數(shù)據(jù)結(jié)構(gòu)實驗報告圖的遍歷》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、HUNANUNIVERSITY課程實習(xí)報告題目：圖的遍歷問題學(xué)生姓名：學(xué)生學(xué)號：專業(yè)班級：指導(dǎo)老師：完成日期：一、需求分析把互聯(lián)網(wǎng)比喻成一個蜘蛛網(wǎng)，那么Spider就是在網(wǎng)上爬來爬去的蜘蛛。網(wǎng)絡(luò)蜘蛛是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁，從網(wǎng)站某一個頁面（通常是首頁）開始，讀取網(wǎng)頁的內(nèi)容，找到在網(wǎng)頁中的其它鏈接地址，然后通過這些鏈接地址尋找下一個網(wǎng)頁，這樣一直循環(huán)下去，直到把這個網(wǎng)站所有的網(wǎng)頁都抓取完為止。如果把整個互聯(lián)網(wǎng)當(dāng)成一個網(wǎng)站，那么網(wǎng)絡(luò)蜘蛛就可以用這個原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁都抓取下來。這樣看來，網(wǎng)絡(luò)蜘蛛就是一個爬行程序，一個

2、抓取網(wǎng)頁的程序。在抓取網(wǎng)頁的時候，網(wǎng)絡(luò)蜘蛛一般有兩種策略：廣度優(yōu)先和深度優(yōu)先。二、概要設(shè)計抽象數(shù)據(jù)類型以鄰接表的形式存儲圖的數(shù)據(jù)，也就是用將用戶的數(shù)據(jù)存入鏈表中。算法的基本思想深度優(yōu)先：采用回溯法的算法，運用遞歸的方法，以深度優(yōu)先為原則對圖進行遍歷。廣度優(yōu)先：采用隊列的數(shù)據(jù)結(jié)構(gòu)保存頂點，然后根據(jù)隊列先進先出的原則對圖進行廣度優(yōu)先遍歷。程序的流程程序由三個模塊構(gòu)成：1、輸入模塊：將數(shù)據(jù)存入鏈表中，并初始化各數(shù)組的值，根據(jù)頂點和權(quán)值構(gòu)建圖。1、深度優(yōu)先模塊：將圖以深度優(yōu)先為原則開始遍歷。2、廣度優(yōu)先模塊：將圖以廣度優(yōu)先為原則開始遍

3、歷。三、詳細設(shè)計算法的具體步驟先將用戶的輸入的頂點和邊的數(shù)量，根據(jù)這些信息構(gòu)建出圖的結(jié)構(gòu)，最后采取深度優(yōu)先和廣度優(yōu)先的方法遍歷該圖。輸入和輸出的格式輸入：首先輸入頂點的數(shù)量，然后是各頂點對應(yīng)的字母，再輸入各條弧（權(quán)值都置為1）。輸出：輸出從首個頂點開始的廣度優(yōu)先遍歷序列和深度先遍歷序列。五、測試結(jié)果