圖的搜索與應(yīng)用實(shí)驗(yàn)報告(附源碼)

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院實(shí)驗(yàn)報告課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程類型：必修實(shí)驗(yàn)項(xiàng)目名稱：圖的搜索與應(yīng)用實(shí)驗(yàn)題目：圖的深度和廣度搜索與拓?fù)渑判蛟O(shè)計(jì)成績報告成績指導(dǎo)老師實(shí)驗(yàn)?zāi)康?.掌握圖的鄰接表的存儲形式。2.熟練掌握圖的搜索策略，包括深度優(yōu)先搜索與廣度優(yōu)先搜索算法。3.掌握有向圖的拓?fù)渑判虻姆椒?。二、?shí)驗(yàn)要求及實(shí)驗(yàn)環(huán)境實(shí)驗(yàn)要求：以鄰接表的形式存儲圖。給出圖的深度優(yōu)先搜索算法與廣度優(yōu)先搜索算法。應(yīng)用搜索算法求出有向圖的拓?fù)渑判?。?shí)驗(yàn)環(huán)境：寢室+機(jī)房+編程軟件（NetBeansIDE6.9.1）。設(shè)計(jì)思想（本程序中的用到的所有數(shù)據(jù)類型的定義，主程序的流程圖及各程序模塊之間的調(diào)用關(guān)系）數(shù)據(jù)類型定義：template<classT>classNode{//定義邊public:intadjvex;//定義頂點(diǎn)所對應(yīng)的序號Node*next;//指向下一頂點(diǎn)的指針intweight;//邊的權(quán)重};template<classT>classVnode{public:Tvertex;Node<T>*firstedge;};template<classT>classAlgraph{public:Vnode<T>adjlist[Max];intn;inte;intmark[Max];intIndegree[Max];};template<classT>classFunction{public://創(chuàng)建有向圖鄰接表voidCreatNalgraph(Algraph<T>*G);//創(chuàng)建無向圖鄰接表voidCreatAlgraph(Algraph<T>*G);//深度優(yōu)先遞歸搜索voidDFSM(Algraph<T>*G,inti);voidDFS(Algraph<T>*G);//廣度優(yōu)先搜索voidBFS(Algraph<T>*G);voidBFSM(Algraph<T>*G,inti);//有向圖的拓?fù)渑判騰oidTopsort(Algraph<T>*G);/得到某個頂點(diǎn)內(nèi)容所對應(yīng)的數(shù)組序號intJudge(Algraph<T>*G,Tname);};主程序流程圖：程序開始程序開始選擇圖的類型選擇圖的類型無向圖有向圖無向圖有向圖深度優(yōu)先搜深度優(yōu)先搜索拓?fù)渑判驈V度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索程序結(jié)束程序結(jié)束調(diào)用關(guān)系：主函數(shù)調(diào)用五個函數(shù)CreatNalgraph(G)//創(chuàng)建有向圖DFS(G)//深度優(yōu)先搜索BFS(G)//廣度優(yōu)先搜索Topsort(G)//有向圖拓?fù)渑判駽reatAlgraph(G)//創(chuàng)建無向圖其中CreatNalgraph(G)調(diào)用Judge(Algraph<T>*G,Tname)函數(shù)；DFS(G)調(diào)用DFSM(Algraph<T>*G,inti)函數(shù)；BFS(G)調(diào)用BFSM(Algraph<T>*G,intk)函數(shù)；CreatAlgraph(G)調(diào)用Judge(Algraph<T>*G,Tname)函數(shù)。測試結(jié)果系統(tǒng)不足與經(jīng)驗(yàn)體會1.對錯誤輸入沒有處理2.友好性不是很好附錄：源代碼（帶注釋）/**File:ADJACENTYLIST.h*Author:Administrator**Createdon2011年12月1日,上午11:26*/#ifndefADJACENTYLIST_H#define ADJACENTYLIST_H#include<iostream>#include<queue>#defineMax100usingnamespacestd;template<classT>classNode{//邊結(jié)點(diǎn)public:intadjvex;Node*next;intweight;};template<classT>classVnode{//頂點(diǎn)結(jié)點(diǎn)public:Tvertex;Node<T>*firstedge;};template<classT>classAlgraph{public:Vnode<T>adjlist[Max];intn;inte;intmark[Max];intIndegree[Max];//頂點(diǎn)入度};template<classT>classFunction{public:voidCreatNalgraph(Algraph<T>*G);//創(chuàng)建有向圖voidCreatAlgraph(Algraph<T>*G);//創(chuàng)建無向圖voidDFSM(Algraph<T>*G,inti);voidDFS(Algraph<T>*G);//深度優(yōu)先搜索voidBFS(Algraph<T>*G);//廣度優(yōu)先搜索voidBFSM(Algraph<T>*G,inti);voidTopsort(Algraph<T>*G);//有向圖的拓?fù)渑判騣ntJudge(Algraph<T>*G,Tname);//得到頂點(diǎn)序號};template<classT>voidFunction<T>::CreatNalgraph(Algraph<T>*G){//創(chuàng)建有向圖inti,j,k;Ta;Tname1,name2;Node<T>*s;cout<<"請輸入頂點(diǎn)數(shù)和邊數(shù)："<<endl;cin>>i;cin>>j;G->n=i;G->e=j;for(inti=0;i<G->n;i++){G->Indegree[i]=0;}cout<<"請輸入頂點(diǎn)內(nèi)容："<<endl;for(i=0;i<G->n;i++){cin>>a;G->adjlist[i].vertex=a;G->adjlist[i].firstedge=NULL;}cout<<"請輸入兩個頂點(diǎn)構(gòu)成的邊，示例：12："<<endl;for(k=0;k<G->e;k++){cin>>name1;i=Judge(G,name1);cin>>name2;j=Judge(G,name2);s=(Node<T>*)malloc(sizeof(Node<T>));G->Indegree[j]++;s->adjvex=j;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;}}template<classT>intFunction<T>::Judge(Algraph<T>*G,Tname){//得到頂點(diǎn)序號for(inti=0;i<G->n;i++){if(G->adjlist[i].vertex==name){returni;break;}}}template<classT>voidFunction<T>::CreatAlgraph(Algraph<T>*G){//創(chuàng)建無向圖inti,j,k;Ta;Tname1,name2;Node<T>*s;cout<<"請輸入頂點(diǎn)數(shù)和邊數(shù)："<<endl;cin>>i;cin>>j;G->n=i;G->e=j;cout<<"請輸入頂點(diǎn)內(nèi)容："<<endl;for(i=0;i<G->n;i++){cin>>a;G->adjlist[i].vertex=a;G->adjlist[i].firstedge=NULL;}cout<<"請輸入兩個頂點(diǎn)構(gòu)成的邊，示例：12："<<endl;for(k=0;k<G->e;k++){cin>>name1;i=Judge(G,name1);cin>>name2;j=Judge(G,name2);s=(Node<T>*)malloc(sizeof(Node<T>));s->adjvex=j;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;s=(Node<T>*)malloc(sizeof(Node<T>));s->adjvex=i;s->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;}}template<classT>voidFunction<T>::DFSM(Algraph<T>*G,inti){Node<T>*p;cout<<G->adjlist[i].vertex<<"";G->mark[i]=1;p=G->adjlist[i].firstedge;while(p){if(G->mark[p->adjvex]==0)DFSM(G,p->adjvex);p=p->next;}}template<classT>voidFunction<T>::DFS(Algraph<T>*G){//深度優(yōu)先搜索for(inti=0;i<G->n;i++){G->mark[i]=0;}for(inti=0;i<G->n;i++){if(G->mark[i]==0)DFSM(G,i);}cout<<endl;}template<classT>voidFunction<T>::BFS(Algraph<T>*G){//廣度優(yōu)先搜索for(inti=0;i<G->n;i++){G->mark[i]=0;}for(inti=0;i<G->n;i++){if(G->mark[i]==0)BFSM(G,i);}cout<<endl;}template<classT>voidFunction<T>::BFSM(Algraph<T>*G,intk){intr=0;intj=0;Node<T>*p;intarray[Max];for(inti=0;i<Max;i++){array[i]=-1;}cout<<G->adjlist[k].vertex<<"";G->mark[k]=1;array[r]=k;G->mark[r]=1;while(array[r]!=-1){intu=array[r++];p=G->adjlist[u].firstedge;while(p){if(G->mark[p->adjvex]==0){cout<<G->adjlist[p->adjvex].vertex<<"";G->mark[p->adjvex]=1;array[++j]=p->adjvex;}p=p->next;}}}template<classT>voidFunction<T>::Topsort(Algraph<T>*G){//有向圖的拓?fù)渑判騠or(inti=0;i<G->n;i++)//初始化mark數(shù)組G->mark[i]=0;usingstd::queue;//使用STL中的隊(duì)列queue<int>Q;for(inti=0;i<G->n;i++)//入度為0的頂點(diǎn)入隊(duì)if(G->Indegree[i]==0)Q.push(i);while(!Q.empty()){//如果隊(duì)列非空intv=Q.front();//獲得隊(duì)列頂部元素Q.pop();//隊(duì)列頂部元素出隊(duì)cout<<G->adjlist[v].vertex<<"";//問頂點(diǎn)vG->mark[v]=1;//將標(biāo)記位設(shè)置為1Node<T>*e=G->adjlist[v].firstedge;while(e){G->Indegree[e->adjvex]--;//與該頂點(diǎn)相鄰的頂點(diǎn)入度減1if(G->Indegree[e->adjvex]==0)//如果頂點(diǎn)入度減為0則入隊(duì)Q.push(e->adjvex);e=e->next;}}for(inti=0;i<G->n;i++)//利用標(biāo)記位可以判斷圖中是否有環(huán)if(G->mark[i]==0){cout<<"此圖有環(huán)！";break;}}#endif /*ADJACENTYLIST_H*//**File:main.cpp*Author:Administrator**Creat