圖的遍歷實驗報告

1、課程實驗報告 課 程 名 稱： 數(shù)據(jù)結(jié)構(gòu) 實驗項目名稱： 圖的遍歷問題 專 業(yè) 班 級： 姓 名： 學 號： 完 成 時 間： 2015 年 05 月 31 日實驗5圖的遍歷問題一、背景網(wǎng)絡蜘蛛即Web Spider，是一個很形象的名字。把互聯(lián)網(wǎng)比喻成一個蜘蛛網(wǎng)，那么Spider就是在網(wǎng)上爬來爬去的蜘蛛。網(wǎng)絡蜘蛛是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁，從網(wǎng)站某一個頁面（通常是首頁）開始，讀取網(wǎng)頁的內(nèi)容，找到在網(wǎng)頁中的其它鏈接地址，然后通過這些鏈接地址尋找下一個網(wǎng)頁，這樣一直循環(huán)下去，直到把這個網(wǎng) 站所有的網(wǎng)頁都抓取完為止。如果把整個互聯(lián)網(wǎng)當成一個網(wǎng)站，那么網(wǎng)絡蜘蛛就可以用這個原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁都

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

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

4、。廣度爬行的優(yōu)點是對數(shù)據(jù)抓取更容易控制些，對服務器的負栽相應也明顯減輕了許多。二、問題描述若用有向網(wǎng)表示網(wǎng)頁的鏈接網(wǎng)絡，其中頂點表示某個網(wǎng)頁，有向弧表示網(wǎng)頁之間的鏈接關(guān)系。試設計一個網(wǎng)絡蜘蛛系統(tǒng)，分別以廣度優(yōu)先和深度優(yōu)先的策略抓取網(wǎng)頁。三、實驗要求基本要求（1） 首先輸入頂點的數(shù)量，然后是各頂點對應的字母，再輸入各條?。?quán)值都置為1）。（2） 輸出從首個頂點開始的廣度優(yōu)先遍歷序列和深度先遍歷序列。實現(xiàn)提示（1） 設圖的頂點大于1個，不超過30個，每個頂點用一個編號表示（如果一個圖有n個頂點，則它們的編號分別為0, 1, 2, 3, , n-1）。（2） 此題為求有向圖的遍歷問題，采用鄰接表存儲

5、圖，實現(xiàn)圖的基本操作，并編寫DFS和BFS程序。四、源代碼#include <iostream> #include <windows.h>#define INFINITY 32767 #define MAX_VEX 20#define QUEUE_SIZE (MAX_VEX+1)using namespace std;bool *visited;typedef struct char *vexs; int arcsMAX_VEXMAX_VEX; int vexnum,arcnum;Graph;class Queuepublic: void InitQueue() bas

6、e=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; void DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear;int Locate(Graph G,char c) for(int i=0;i<G.vexnum;i+) if(G.vexsi=c) return i; re

7、turn -1; void CreateUDN(Graph &G) int i,j,w,s1,s2; char a,b,temp; cout<<"輸入頂點數(shù)和弧數(shù):" cin>>G.vexnum>>G.arcnum; temp=getchar(); G.vexs=(char *)malloc(G.vexnum*sizeof(char); cout<<"輸入頂點："<<endl; for(i=0;i<G.vexnum;i+) cout<<"輸入頂點"&

8、lt;<i<<":" cin>>G.vexsi; temp=getchar(); for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+) G.arcsij=INFINITY; cout<<"輸入弧:"<<endl; for(i=0;i<G.arcnum;i+) cout<<"輸入弧"<<i<<":" cin>>a>>b>>w; temp=

9、getchar(); s1=Locate(G,a); s2=Locate(G,b); G.arcss1s2=G.arcss2s1=w; int FirstVex(Graph G,int k) if(k>=0 && k<G.vexnum) for(int i=0;i<G.vexnum;i+) if(G.arcski!=INFINITY) return i; return -1; int NextVex(Graph G,int i,int j) if(i>=0 && i<G.vexnum && j>=0 &

10、& j<G.vexnum) for(int k=j+1;k<G.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1;void BFS(Graph G,int k) int i; if(k=-1) for(i=0;i<G.vexnum;i+) if(!visitedi) BFS(G,i); else visitedk=true; cout<<G.vexsk; for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i) if(!visitedi) BFS(G,i); void

11、 DFS(Graph G) int k; Queue Q; Q.InitQueue(); for(int i=0;i<G.vexnum;i+) if(!visitedi) visitedi=true; cout<<G.vexsi; Q.EnQueue(i); while(Q.front!=Q.rear) Q.DeQueue(k); for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w) if(!visitedw) visitedw=true; cout<<G.vexsw; Q.EnQueue(w); int main() int i; Graph G; CreateUDN(G); visited=(bool *)malloc(G.vexnum*sizeof(bool); cout<<"深度優(yōu)先遍歷: " for(i=0;i<G.vexnum;i+) visitedi=false; BFS(G,-