圖的遍歷問題

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

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

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

4、t; L。廣度爬行的優(yōu)點(diǎn)是對(duì)數(shù)據(jù)抓取更容易控制些，對(duì)服務(wù)器的負(fù)栽相應(yīng)也明顯減輕了許多。問題描述 若用有向網(wǎng)表示網(wǎng)頁的鏈接網(wǎng)絡(luò)，其中頂點(diǎn)表示某個(gè)網(wǎng)頁，有向弧表示網(wǎng)頁之間的鏈接關(guān)系。試設(shè)計(jì)一個(gè)網(wǎng)絡(luò)蜘蛛系統(tǒng)，分別以廣度優(yōu)先和深度優(yōu)先的策略抓取網(wǎng)頁。 基本要求（1） 首先輸入頂點(diǎn)的數(shù)量，然后是各頂點(diǎn)對(duì)應(yīng)的字母，再輸入各條?。?quán)值都置為1）。（2） 輸出從首個(gè)頂點(diǎn)開始的廣度優(yōu)先遍歷序列和深度先遍歷序列。測(cè)試用例輸入輸入頂點(diǎn)數(shù)和弧數(shù):8 9 輸入8個(gè)頂點(diǎn). 輸入頂點(diǎn)0:a 輸入頂點(diǎn)1:b 輸入頂點(diǎn)2:c 輸入頂點(diǎn)3:d 輸入頂點(diǎn)4:e 輸入頂點(diǎn)5:f 輸入頂點(diǎn)6:g 輸入頂點(diǎn)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 輸出廣度優(yōu)先遍歷: a b d h e c f g （寫反了 ）深度優(yōu)先遍歷: a b c d e f g h實(shí)驗(yàn)提示（1） 設(shè)圖的頂點(diǎn)大于1個(gè)，不超過30個(gè)，每個(gè)頂點(diǎn)用一個(gè)編號(hào)表示（如果一個(gè)圖有n個(gè)頂點(diǎn)，則它們的編號(hào)分別為0, 1, 2, 3, , n-1）。（2） 此題為求有向圖的遍歷問題，采用鄰接表存儲(chǔ)圖，實(shí)現(xiàn)圖的基本操作，并編寫DFS和BFS程序。選做內(nèi)容使用鄰接矩陣存儲(chǔ)圖，編寫DFS和BFS程序。

6、 課后題目求圖的最大連通子圖。一、需求分析1.首先輸入頂點(diǎn)的數(shù)量，然后是各頂點(diǎn)對(duì)應(yīng)的字母，再輸入各條?。?quán)值都置為1）；輸出從首個(gè)頂點(diǎn)開始的廣度優(yōu)先遍歷序列和深度先遍歷序列；2.為了達(dá)到任意圖的遍歷（結(jié)點(diǎn)名稱不一定是數(shù)字，可以是任意可見字符），可以自定義一個(gè)字符數(shù)組類型，保存該結(jié)點(diǎn)的名字；3.圖使用相鄰矩陣來實(shí)現(xiàn)；4.測(cè)試數(shù)據(jù)：輸入輸入頂點(diǎn)數(shù)和弧數(shù):8 9 輸入8個(gè)頂點(diǎn). 輸入頂點(diǎn)0:a 輸入頂點(diǎn)1:b 輸入頂點(diǎn)2:c 輸入頂點(diǎn)3:d 輸入頂點(diǎn)4:e 輸入頂點(diǎn)5:f 輸入頂點(diǎn)6:g 輸入頂點(diǎn)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 輸出廣度優(yōu)先遍歷: a b c d e f g h （這才是正確的結(jié)果）深度優(yōu)先遍歷: a b d h e c f g二、概要設(shè)計(jì)抽象數(shù)據(jù)類型class Queue/循環(huán)順序隊(duì)列，為廣度優(yōu)先遍歷設(shè)計(jì)；圖類基本操作：Graph(int numVert) bool prior(struct patient x,struct patient y)；/圖的構(gòu)造函數(shù)void init (int n)/初始化矩陣int n()return numVertex;/返回頂點(diǎn)數(shù)目int e()re

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

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

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

11、度優(yōu)先遍歷，輸出結(jié)果>廣度優(yōu)先遍歷，輸出結(jié)果。四、詳細(xì)設(shè)計(jì)：物理數(shù)據(jù)類型根據(jù)用戶的輸入結(jié)點(diǎn)數(shù)初始化圖void init (int n)/初始化矩陣int i;numVertex = n;numEdge = 0;mark = new intn;Name = new charn;for(i=0; i < numVertex;i+)marki = UNVISITED;/全部標(biāo)志設(shè)為未訪問Namei = NULL;/頂點(diǎn)名字全部設(shè)為空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.根據(jù)用戶輸入的邊信息用鄰接矩陣存儲(chǔ)邊權(quán)值；3.用深度優(yōu)先和廣度優(yōu)先遍歷圖，輸出結(jié)果；算法的時(shí)空分析對(duì)于具有n個(gè)頂點(diǎn)e條邊的無向圖，當(dāng)圖采用鄰接矩陣存儲(chǔ)時(shí)，算法的總時(shí)間為O（）。四、調(diào)試分析本算法代碼為書本上的代碼稍微修改得來，理解起來較容易，但是鄰接表的創(chuàng)建我一直都搞不懂，所以用了鄰接矩陣來創(chuàng)建圖；五、測(cè)試結(jié)果七、附錄程序源代碼（c+）/*圖的遍歷*/#include<iostream>using namespa

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

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

15、nt = (front+1) % maxsize;/隊(duì)首下標(biāo)后移一個(gè)位置return it;virtual int length() const/隊(duì)列長度return (rear + maxsize) - front +1) % maxsize;class Graph/圖類private:int numVertex, numEdge;/頂點(diǎn)數(shù)量和邊數(shù)；int * matrix;/二維數(shù)組指針；int *mark;/標(biāo)志數(shù)組指針char *Name;/頂點(diǎn)名字；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;/全部標(biāo)志設(shè)為未訪問Namei = NULL;/頂點(diǎn)名字全部設(shè)為空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;/返回頂點(diǎn)數(shù)目int e()return numEdge;/返回邊數(shù)int first(int v)/返回結(jié)點(diǎn)v的第一個(gè)鄰接結(jié)點(diǎn)for(int i=0;i < numVertex;i+)if(matrixvi != 0) return i;return numVertex;int next(int v,int w)/返回v的在w之后的第一個(gè)

18、鄰接結(jié)點(diǎn)for(int i=w+1;i < numVertex;i+)if(matrixvi != 0) return i;return numVertex;void setEdge(int v1, int v2, int wt =1)/設(shè)置一條邊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)/判斷兩個(gè)頂點(diǎn)是否有邊連接return matrixij !=0;int weight (int v1,int v2) return matrixv1v2;/返回權(quán)值int getMark(int v) return markv;/返回標(biāo)志int getSub(char c)/獲取頂點(diǎn)名字的下標(biāo)for (int i =0;i < numVertex; i+)if(Namei = c) return i;void setMark(int v,int val) markv = val;/設(shè)置標(biāo)志char getName (int v)return

20、Namev;/獲取頂點(diǎn)名字void setName(int v,char name)Namev = name;/設(shè)置頂點(diǎn)名字;void DFS(Graph* G,int v) /深度優(yōu)先遍歷函數(shù)體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) /廣度優(yōu)先遍歷函數(shù)體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);/*主函數(shù)*/int main()int numVertex,numEdge,weight,i=0;/頂點(diǎn)數(shù)，邊數(shù)，權(quán)值，循環(huán)控制值ichar Name1,Name2;/頂點(diǎn)名字變量Queue<int> *Q = new Queue<int>30;/開辟一個(gè)隊(duì)列用來存放BFS搜索的數(shù)據(jù)cout << "輸入頂點(diǎn)數(shù)和弧數(shù):"cin >> numVertex >> numEdge;Graph G(numVertex);/根據(jù)輸入的頂點(diǎn)數(shù)初始化圖cout