1、數據結構實驗報告HUNAN UNIVERSITY數據結構實驗報告題 目： 圖的遍歷問題 學生姓名 梁天 學生學號 201408010318 專業班級 計科1403 指導老師 夏艷 日 期 2016.05.14 背景 網絡蜘蛛即Web Spider，是一個很形象的名字。把互聯網比喻成一個蜘蛛網，那么Spider就是在網上爬來爬去的蜘蛛。網絡蜘蛛是通過網頁的鏈接地址來尋找網頁，從網站某一個頁面（通常是首頁）開始，讀取網頁的內容，找到在網頁中的其它鏈接地址，然后通過這些鏈接地址尋找下一個網頁，這樣一直循環下去，直到把這個網站所有的網頁都抓取完為止。如果把整個互聯網當成一個網站，那么網絡蜘蛛就可以用這

2、個原理把互聯網上所有的網頁都抓取下來。這樣看來，網絡蜘蛛就是一個爬行程序，一個抓取網頁的程序。在抓取網頁的時候，網絡蜘蛛一般有兩種策略：廣度優先和深度優先（如下面這張簡單化的網頁連接模型圖所示，其中A為起點也就是蜘蛛索引的起點）。深度優先顧名思義就是讓網絡蜘蛛盡量的在抓取網頁時往網頁更深層次的挖掘進去講究的是深度!也泛指: 網絡蜘蛛將會從起始頁開始，一個鏈接一個鏈接跟蹤下去，處理完這條線路之后再轉入下一個起始頁，繼續跟蹤鏈接! 則訪問的節點順序為=> A -> B -> E -> H -> I -> C -> D -> F -> K -&g

3、t; L -> G。深度爬行的優點是:網絡蜘蛛程序在設計的時候相對比較容易些；缺點是每次爬行一層總要向"蜘蛛老家" 數據庫訪問一下。問問老總有必要還要爬下一層嗎! 爬一層問一次. 如果一個蜘蛛不管3721不斷往下爬很可能迷路更有可能爬到國外的網站去，不僅增加了系統數據的復雜度更是增加的服務器的負擔。廣度優先在這里的定義就是層爬行，即一層一層的爬行， 按照層的分布與布局去索引處理與抓取網頁。則訪問的節點順序為=> A -> B -> C -> D -> E -> F -> G -> H -> I-> K -&g

4、t; L。廣度爬行的優點是對數據抓取更容易控制些，對服務器的負栽相應也明顯減輕了許多。問題描述 若用有向網表示網頁的鏈接網絡，其中頂點表示某個網頁，有向弧表示網頁之間的鏈接關系。試設計一個網絡蜘蛛系統，分別以廣度優先和深度優先的策略抓取網頁。 基本要求（1） 首先輸入頂點的數量，然后是各頂點對應的字母，再輸入各條弧（權值都置為1）。（2） 輸出從首個頂點開始的廣度優先遍歷序列和深度先遍歷序列。測試用例輸入輸入頂點數和弧數:8 9 輸入8個頂點. 輸入頂點0:a 輸入頂點1:b 輸入頂點2:c 輸入頂點3:d 輸入頂點4:e 輸入頂點5:f 輸入頂點6:g 輸入頂點7:h 輸入9條弧. 輸入弧0

5、:a b 1 輸入弧1:b d 1 輸入弧2:b e 1 輸入弧3:d h 1 輸入弧4:e h 1 輸入弧5:a c 1 輸入弧6:c f 1 輸入弧7:c g 1 輸入弧8:f g 1 輸出廣度優先遍歷: a b d h e c f g （寫反了 ）深度優先遍歷: a b c d e f g h實驗提示（1） 設圖的頂點大于1個，不超過30個，每個頂點用一個編號表示（如果一個圖有n個頂點，則它們的編號分別為0, 1, 2, 3, , n-1）。（2） 此題為求有向圖的遍歷問題，采用鄰接表存儲圖，實現圖的基本操作，并編寫DFS和BFS程序。選做內容使用鄰接矩陣存儲圖，編寫DFS和BFS程序。

6、 課后題目求圖的最大連通子圖。一、需求分析1.首先輸入頂點的數量，然后是各頂點對應的字母，再輸入各條弧（權值都置為1）；輸出從首個頂點開始的廣度優先遍歷序列和深度先遍歷序列；2.為了達到任意圖的遍歷（結點名稱不一定是數字，可以是任意可見字符），可以自定義一個字符數組類型，保存該結點的名字；3.圖使用相鄰矩陣來實現；4.測試數據：輸入輸入頂點數和弧數:8 9 輸入8個頂點. 輸入頂點0:a 輸入頂點1:b 輸入頂點2:c 輸入頂點3:d 輸入頂點4:e 輸入頂點5:f 輸入頂點6:g 輸入頂點7:h 輸入9條弧. 輸入弧0:a b 1 輸入弧1:b d 1 輸入弧2:b e 1 輸入弧3:d h

7、 1 輸入弧4:e h 1 輸入弧5:a c 1 輸入弧6:c f 1 輸入弧7:c g 1 輸入弧8:f g 1 輸出廣度優先遍歷: a b c d e f g h （這才是正確的結果）深度優先遍歷: a b d h e c f g二、概要設計抽象數據類型class Queue/循環順序隊列，為廣度優先遍歷設計；圖類基本操作：Graph(int numVert) bool prior(struct patient x,struct patient y)；/圖的構造函數void init (int n)/初始化矩陣int n()return numVertex;/返回頂點數目int e()re

8、turn numEdge;/返回邊數int first(int v)/返回結點v的第一個鄰接結點int next(int v,int w)/返回v的在w之后的第一個鄰接結點void setEdge(int v1, int v2, int wt =1)/設置一條邊void delEdge(int v1 ,int v2)/刪除一條邊bool isEdge(int i,int j)/判斷兩個頂點是否有邊連接int weight (int v1,int v2) return matrixv1v2;/返回V1 V2 相連的邊權值int getMark(int v) return markv;/返回V頂點

9、是否已經訪問的標志int getSub(char c)/獲取頂點名字的下標void setMark(int v,int val) markv = val;/設置標志char getName (int v)return Namev;/獲取頂點名字void setName(int v,char name)Namev = name;/設置頂點名字圖的遍歷函數：void DFS(Graph* G,int v) /深度優先遍歷函數體void BFS(Graph* G,int start,Queue<int>* Q) /廣度優先遍歷函數體算法的基本思想用自定義類型的數組，記錄每個結點的信息（包

10、括名稱Name、是否被訪問Mark），這兩個數組作為圖的私有成員； 深度優先采取的遞歸思想。首先，將從起點，沿某條邊，順勢遍歷下去，直到不能繼續遍歷下去。這時，回溯，接著從未訪問的邊遍歷下去。如此往復，直到將所有結點遍歷完。廣度優先搜索需要使用隊列。首先，將起點入隊，并標為已訪問。進入循環，當隊列不為空時，將隊首元素出隊，輸出到屏幕上，并將與隊首元素相鄰的且未訪問的結點全部放入隊列，（一般按照序號由小到大入隊）標為已訪問。繼續隊首元素出隊，將與隊首元素相連的未訪問元素入隊，直到隊空；三、程序的流程：輸入頂點數、邊數>完成圖的初始化>輸入頂點名稱、設置邊>輸入遍歷起點>深

11、度優先遍歷，輸出結果>廣度優先遍歷，輸出結果。四、詳細設計：物理數據類型根據用戶的輸入結點數初始化圖void init (int n)/初始化矩陣int i;numVertex = n;numEdge = 0;mark = new intn;Name = new charn;for(i=0; i < numVertex;i+)marki = UNVISITED;/全部標志設為未訪問Namei = NULL;/頂點名字全部設為空matrix = (int *)new int*numVertex;for( i=0;i < numVertex;i+)matrixi = new in

12、tnumVertex;for( i=0;i < numVertex;i+)for(int j=0;j < numVertex;j+)matrixij =0;2.根據用戶輸入的邊信息用鄰接矩陣存儲邊權值；3.用深度優先和廣度優先遍歷圖，輸出結果；算法的時空分析對于具有n個頂點e條邊的無向圖，當圖采用鄰接矩陣存儲時，算法的總時間為O（）。四、調試分析本算法代碼為書本上的代碼稍微修改得來，理解起來較容易，但是鄰接表的創建我一直都搞不懂，所以用了鄰接矩陣來創建圖；五、測試結果七、附錄程序源代碼（c+）/*圖的遍歷*/#include<iostream>using namespa

13、ce std;#include<assert.h>enumUNVISITED,VISITED;const int MAX=100;/隊列最大元素個數template <typename E>class Queue/循環順序隊列private:int maxsize;/隊列的最大值int front;/指向隊首int rear;/指向隊尾E * array;/隊列數組指針public:Queue(int size = MAX)/構造函數，同時初始化隊列maxsize = size +1;/空出一個位置不存放元素，方便判斷空隊列和滿隊列rear =0; front =1;a

14、rray = new Emaxsize;/開辟一個大小為maxsize的隊列Queue()delete array;void enqueue(const E & it)/元素進隊函數assert(rear+2) %maxsize != front, "Queue is full");/判斷隊是否滿array(+rear) %maxsize = it;/在隊尾插入新元素E dequeue()/出隊函數assert(length() !=0 , "Queue is empty");/判斷隊是否空E it = arrayfront;/取出隊首元素fro

15、nt = (front+1) % maxsize;/隊首下標后移一個位置return it;virtual int length() const/隊列長度return (rear + maxsize) - front +1) % maxsize;class Graph/圖類private:int numVertex, numEdge;/頂點數量和邊數；int * matrix;/二維數組指針；int *mark;/標志數組指針char *Name;/頂點名字；public:Graph(int numVert)init(numVert);/初始化圖Graph()delete mark;delet

16、e Name;for (int i=0; i < numVertex ;i+)delete matrixi;delete matrix;void init (int n)/初始化矩陣int i;numVertex = n;numEdge = 0;mark = new intn;Name = new charn;for(i=0; i < numVertex;i+)marki = UNVISITED;/全部標志設為未訪問Namei = NULL;/頂點名字全部設為空matrix = (int *)new int*numVertex;for( i=0;i < numVertex;i

17、+)matrixi = new intnumVertex;for( i=0;i < numVertex;i+)for(int j=0;j < numVertex;j+)matrixij =0;int n()return numVertex;/返回頂點數目int e()return numEdge;/返回邊數int first(int v)/返回結點v的第一個鄰接結點for(int i=0;i < numVertex;i+)if(matrixvi != 0) return i;return numVertex;int next(int v,int w)/返回v的在w之后的第一個

18、鄰接結點for(int i=w+1;i < numVertex;i+)if(matrixvi != 0) return i;return numVertex;void setEdge(int v1, int v2, int wt =1)/設置一條邊assert(wt >0, "Illegal weight value");if(matrixv1v2 = 0) numEdge+;matrixv1v2 =wt;void delEdge(int v1 ,int v2)/刪除一條邊if(matrixv1v2 != 0) numEdge-;matrixv1v2 =0;bo

19、ol isEdge(int i,int j)/判斷兩個頂點是否有邊連接return matrixij !=0;int weight (int v1,int v2) return matrixv1v2;/返回權值int getMark(int v) return markv;/返回標志int getSub(char c)/獲取頂點名字的下標for (int i =0;i < numVertex; i+)if(Namei = c) return i;void setMark(int v,int val) markv = val;/設置標志char getName (int v)return

20、Namev;/獲取頂點名字void setName(int v,char name)Namev = name;/設置頂點名字;void DFS(Graph* G,int v) /深度優先遍歷函數體cout << G->getName(v) <<" "G ->setMark(v, VISITED);for(int w = G->first(v); w < G->n(); w = G->next(v,w)if(G->getMark(w) = UNVISITED)DFS(G,w);void BFS(Graph* G

21、,int start,Queue<int>* Q) /廣度優先遍歷函數體int v,w;Q->enqueue(start);G->setMark(start, VISITED);while(Q->length()!=0)v = Q->dequeue();cout << G->getName(v) <<" "for(w=G->first(v); w<G->n();w=G->next(v,w)if(G->getMark(w)=UNVISITED)G->setMark(w,VISITED);Q->enqueue(w);/*主函數*/int main()int numVertex,numEdge,weight,i=0;/頂點數，邊數，權值，循環控制值ichar Name1,Name2;/頂點名字變量Queue<int> *Q = new Queue<int>30;/開辟一個隊列用來存放BFS搜索的數據cout << "輸入頂點數和弧數:"cin >> numVertex >> numEdge;Graph G(numVertex);/根據輸入的頂點數初始化圖cout