圖的遍歷問題背景若用有向網表示網頁的鏈接網絡，其中頂點表示某個網頁，有向弧表示網頁之間的鏈接關系。試設計一個網絡蜘蛛系統，分別以廣度優先和深度優先的策略抓取網頁。需求分析首先輸入頂點的數量，然后是各頂點對應的字母，再輸入各條?。嘀刀贾脼?）；輸出從首個頂點開始的廣度優先遍歷序列和深度先遍歷序列；為了達到任意圖的遍歷（結點名稱不一定是數字，可以是任意可見字符），可以自定義一個數組類型，保存該結點的名稱和記錄是否被訪問；圖使用相鄰矩陣來實現；測試數據：輸入 輸入頂點數和弧數:89輸入8個頂點.輸入頂點0:a輸入頂點1:b輸入頂點2:c輸入頂點3:d輸入頂點4:e輸入頂點5:f輸入頂點6:g輸入頂點7:h輸入9條弧.輸入弧0:ab1輸入弧1:bd1輸入弧2:be1輸入弧3:dh1輸入弧4:eh1輸入弧5:ac1輸入弧6:cf1輸入弧7:cg1輸入弧8:fg1輸出廣度優先遍歷:abdhecfg深度優先遍歷:abcdefgh概要設計抽象數據類型為了遍歷任意圖，定義了如下數據類型，用于存儲該結點的名稱和記錄是否被訪問過。classNode//基本抽象數據類型{public: charch;//記錄名稱，如果將這里改成數組，結點名稱可以是多個字符 intflag;//記錄結點是否被訪問};classGraph//圖類，此類中，封裝了圖的一些成員和一些必須的成員函數{private: intgetSub(char);//獲取某名稱的下標 Node*arrNode;//記錄名稱和是否訪問的數組 intnumVertex,numEdge;//記錄圖的頂點數和邊數 int**matrix;//用一個二維數組記錄兩點間是否相連，1相連，0斷開public: voidsetCh(char,int);//將數組的arrNode的每一個單元設置一個結點名稱 Graph(int); ~Graph(); intgetNumVertex();//獲得圖的頂點數 charfirst(charch);//獲得相鄰結點 charnext(charch1,charch2);//獲得隔著ch2，但與ch2相鄰的結點 voidsetEdge(char,char,intw=1);//設置兩頂點的邊和權重（權重默認為1） intgetMark(char);//獲取是否被訪問的記錄，已訪問返回1，未訪問返回0 voidsetMark(char);//把已訪問的結點，設置標記};算法的基本思想用一個自定義類型的數組，記錄每個結點的信息（包括名稱、是否被訪問），且此數組作為圖的成員變量之一；用一個類，對數組進行相應的操作，以便獲得所需的信息。深度優先采取的遞歸思想。首先，將從起點，沿某條邊，順勢遍歷下去，直到不能繼續遍歷下去。這時，又從起點的另一結點開始，遍歷下去。如此往復，知道將所有結點遍歷完。廣度優先得使用隊列。首先，將起點入隊，并標為已訪問。進入循環，當隊列不為空時，出隊，輸出，并將與出隊的元素相鄰的且未訪問的結點全部放入隊列，標為已訪問。一次循環，只有一個結點出隊，大于等于0個結點入隊。voidDFS(Graph*G,charch)//深度優先遍歷圖{ inti=0; cout<<ch<<""; G->setMark(ch); for(charw=G->first(ch);i<G->getNumVertex();w=G->next(ch,w)) { if(G->getMark(w)==0) DFS(G,w); i++; }}voidBFS(Graph*G,charch,myQueue*q)//廣度優先遍歷圖{ charv,w; q->enqueue(ch); G->setMark(ch); while(q->length()!=0) { q->dequeue(v); cout<<v<<""; inti=0; for(w=G->first(v);i<G->getNumVertex();w=G->next(v,w)) { if(G->getMark(w)==0) { G->setMark(w); q->enqueue(w); } i++; } }}

程序的流程輸入頂點數、邊數——>完成圖的初始化——>輸入頂點名稱、設置邊——>輸入遍歷起點——>深度優先遍歷，輸出結果——>廣度優先遍歷，輸出結果算法的時空分析因為此程序追求結點的個性化（可以不按ABCD……的順序來命名，可以用任意可見字符），使得程序的時間代價比較大。不管是設置頂點名稱，還是遍歷，這都與圖的頂點個數相關，包括根據結點名稱獲得下標的函數也是用循環實現的，時間復雜度為Θ(n)?？傊瑫r間開銷比較大。輸入和輸出的格式輸入 輸入頂點數和弧數://提示輸入 等待輸入輸入8個頂點.//提示輸入頂點0://提示輸入等待輸入……輸入9條弧.//提示輸入弧0://提示輸入等待輸入運行截圖實驗心得（可選）這個實驗，總的難度不大。但我在追求結點名稱的個性化的時候，沒注意到這帶來的時間開銷，在寫實驗報告時才發現。實驗中，大量使用了循環，所以比較適合于密集圖，稀疏圖用此，那就是程序，那就是浪費時間了。發現這個程序，還存在不完善的地方。如果圖不是連通的，那么將不能把所有的點遍歷完。附錄（源碼）/*********************各類定義******************************/classNode//基本抽象數據類型{public: charch;//記錄名稱，如果將這里改成數組，結點名稱可以是多個字符 intflag;//記錄結點是否被訪問};classGraph//圖類，此類中，封裝了圖的一些成員和一些必須的成員函數{private: intgetSub(char);//獲取某名稱的下標 Node*arrNode;//記錄名稱和是否訪問的數組 intnumVertex,numEdge;//記錄圖的頂點數和邊數 int**matrix;//用一個二維數組記錄兩點間是否相連，1相連，0斷開public: voidsetCh(char,int);//將數組的arrNode的每一個單元設置一個結點名稱 Graph(int); ~Graph(); intgetNumVertex();//獲得圖的頂點數 charfirst(charch);//獲得相鄰結點 charnext(charch1,charch2);//獲得隔著ch2，但與ch2相鄰的結點 voidsetEdge(char,char,intw=1);//設置兩頂點的邊和權重（權重默認為1） intgetMark(char);//獲取是否被訪問的記錄，已訪問返回1，未訪問返回0 voidsetMark(char);//把已訪問的結點，設置標記};/*************各函數的函數體*****************************/Graph::Graph(intn){ inti,j; arrNode=newNode[n]; numVertex=n; numEdge=0; for(i=0;i<numVertex;i++) arrNode[i].flag=0; matrix=newint*[numVertex]; for(i=0;i<numVertex;i++) matrix[i]=newint[numVertex]; for(i=0;i<numVertex;i++) for(j=0;j<numVertex;j++) matrix[i][j]=0;}Graph::~Graph(){ delete[]arrNode; for(inti=0;i<numVertex;i++) delete[]matrix[i]; delete[]matrix;}intGraph::getSub(charch)//獲取下標{ for(inti=0;i<numVertex;i++) if(ch==arrNode[i].ch) returni;}intGraph::getNumVertex()//獲取頂點數{ returnnumVertex;}charGraph::first(charch)//獲取相鄰結點{ for(inti=0;i<numVertex;i++) if(matrix[getSub(ch)][i]!=0) returnarrNode[i].ch; returnch;}charGraph::next(charch1,charch2)//獲取與ch2相鄰的結點{ for(inti=getSub(ch2)+1;i<numVertex;i++) if(matrix[getSub(ch1)][i]!=0) returnarrNode[i].ch; returnch1;}voidGraph::setEdge(charch1,charch2,intw)//設置邊{ if(matrix[getSub(ch1)][getSub(ch2)]==0) { numEdge++; matrix[getSub(ch1)][getSub(ch2)]=1; }}intGraph::getMark(charch)//獲取訪問信息{ for(inti=0;i<numVertex;i++) if(ch==arrNode[i].ch) returnarrNode[i].flag; return-1;}voidGraph::setMark(charch)//設置標記{ for(inti=0;i<numVertex;i++) if(ch==arrNode[i].ch) arrNode[i].flag=1;}voidGraph::setCh(charch,intn)//將結點名稱設置在字符中{ arrNode[n].ch=ch;}/***************主函數*********************/voidDFS(Graph*,char);//深度優先遍歷函數聲明voidBFS(Graph*,char,myQueue*);//廣度優先遍歷函數聲明intmain(){ intnumVer,numE,i; chartemp1,temp2;//temp1,temp2作臨時變量，記錄輸入的值 myQueue*q=newmyQueue; cout<<"輸入定點數和弧數："; cin>>numVer>>numE; GraphmyGraph1(numVer); GraphmyGraph2(numVer); cout<<"請輸入"<<numVer<<"個頂點：\n"; for(i=0;i<numVer;i++)//將結點名稱設置在數組中 { cout<<"輸入頂點"<<i<<":"; cin>>temp1; myGraph1.setCh(temp1,i); myGraph2.setCh(temp1,i); } cout<<"請輸入"<<numE<<"條?。篭n"; for(i=0;i<numE;i++)//設置邊 { cout<<"輸入弧"<<i<<":"; cin>>temp1>>temp2; myGraph1.setEdge(temp1,temp2); myGraph2.setEdge(temp1,temp2); } cout<<"深度優先結果:"; DFS(&myGraph1,'a'); cout<<"\n廣度優先結果:"; BFS(&myGraph2,'a',q); cout<<endl; return0;}voidDFS(Graph*G,charch)//深度優先遍歷函數體{ inti=0; cout<<ch<<""; G->setMark(ch); for(charw=G->first(ch);i<G->getNumVertex();w=G->next(ch,w),i++) if(G->getMark(w)==0) DFS(G,w);}voidBFS(Graph