簡單路徑問題

-.z.背景簡單路徑：如果一條路徑上的頂點除了起點和終點可以一樣外，其它頂點均不一樣，則稱此路徑為一條簡單路徑。問題描述假設(shè)用無向圖表示高速公路網(wǎng)，其中頂點表示城市，邊表示城市之間的高速公路。試設(shè)計一個找路程序，獲取兩個城市之間的所有簡單路徑。一．需求分析1.根本要求輸入?yún)?shù)：結(jié)點總數(shù)，結(jié)點的城市編號〔3位長的數(shù)字，〕，連接城市的高速公路〔用高速公路連接的兩個城市編號標記〕。輸入要求取所有簡單路徑的兩個城市編號。將所有路徑〔有城市編號組成〕輸出到用戶指定的文件中。2.輸入輸出格形式：輸入：(1)要求用戶先輸入結(jié)點總數(shù)〔總城市數(shù)n〕，再輸入代表城市的編號〔三位數(shù)字〕。(2)屢次輸入兩個城市編號來確定城市之間的高速公路〔最多輸入n(n-1)/2次〕。(3)輸入兩個城市的編號來獲取簡單路徑。輸出：兩點中所有的簡單路徑。。3測試數(shù)據(jù) 輸入 節(jié)點數(shù)：5 城市編號：001002003004005006路徑： 001002001003002003002004003005004006005006查找路徑： 00010005輸出001-->003-->005001-->002-->003-->005001-->002-->004-->006-->005001-->003-->002-->004-->006->005二、概要設(shè)計抽象數(shù)據(jù)類型為實現(xiàn)上述程序的功能，應(yīng)以整數(shù)存儲用戶的每次輸入，根據(jù)輸入建立一個無向圖，用基于深度優(yōu)先搜索的方法找出簡單路徑。圖的ADT設(shè)計：數(shù)據(jù)對象：Graph=(V,R) 數(shù)據(jù)關(guān)系：VR＝{<v,w>|v,w∈V且P(v,w)} <v,w>表示從v到w的一條弧，并稱v為弧頭，w為弧尾。 謂詞P(v,w)定義了弧<v,w>的意義或信息。根本操作：classGraph{ //圖的定義類public:intGetVe*Num()//獲得圖中頂點的個數(shù) intLocate_Ve*(stringv)//獲得頂點在圖中的位置 voidDFS_Traverse()//深度優(yōu)先搜索圖};算法的根本思想對于用戶想要查找路徑的兩個頂點，創(chuàng)立一個用于記錄路徑的數(shù)組，路徑長度為0。以其中一個頂點為起點，訪問該頂點，將該頂點參加路徑，訪問下一個未被訪問的頂點，將其參加路徑，并將路徑長度加1。假設(shè)該頂點為終點，將該路徑輸出，然后從路徑中刪除該頂點，并將路徑長度減1，訪問下一個未被訪問的頂點。假設(shè)不為終點，則訪問下一個未被訪問的頂點，直到路徑長度不小于頂點個數(shù)。程序的流程程序由三個模塊組成：(1)建圖模塊：完成頂點數(shù)，邊數(shù)和頂點關(guān)系〔路徑〕的輸入，并依此建立一個無向圖。(2)遍歷模塊：深度優(yōu)先遍歷圖并打印與屏幕上，還可以在查找模塊中被調(diào)用進展簡單路徑的查找。(3)查找模塊：基于DFS的思想進展兩點之間固定路徑長度簡單路徑的查找，所以需要被調(diào)用N次〔N為圖頂點數(shù)減一〕以完成所有簡單路徑查找并輸出與屏幕上。三、詳細設(shè)計物理數(shù)據(jù)類型頂點上存儲的應(yīng)為該城市的編碼〔為三位數(shù)字〕，可以用三位的字符數(shù)組來存儲，并檢查是否屬于字符的0~9。邊上應(yīng)存儲有兩城市之間路徑長度〔此題只需求簡單路徑，所以全部設(shè)為1〕，無路徑則設(shè)為-1。以整型數(shù)來存儲。深度優(yōu)先遍歷圖的偽代碼：voidDFS_Traverse()//深度優(yōu)先遍歷圖，將所有頂點定義為未訪問{for(inti=0;i<ve*num;i++)visited[i]=false;for(i=0;i<ve*num;i++)if(!visited[i])DFS(i);}構(gòu)造無向圖的偽代碼voidCreate_NDGraph()//構(gòu)造無向圖{stringv1,v2;inti,j,k;cout<<"輸入頂點數(shù)和邊數(shù)：";cin>>ve*num>>arum;while(ve*num>20)//提示頂點個數(shù)的限制{cout<<"請輸入少于20個頂點(重新輸入頂點數(shù)和邊數(shù))：";cin>>ve*num>>arum;}cout<<"輸入頂點名稱：";for(i=0;i<ve*num;i++)//頂點賦值，并將頂點的第一條邊設(shè)置為空{(diào) cin>>vertices[i].data;vertices[i].firstarc=NULL; if(i>0) //第二次輸入時檢查是否輸入了和之前輸入一樣的頂點 { for(j=0;j<i;j++) if(vertices[i].data==vertices[j].data) //如果一樣，提示重新輸入 { cout<<"輸入重復(fù)的頂點：--"<<vertices[i].data<<"--請重新輸入："; i--; } }}for(k=0;k<arum;k++)//屢次輸入兩個頂點來構(gòu)造邊{cout<<"輸入每條邊對應(yīng)的兩個頂點：";cin>>v1>>v2;i=Locate_Ve*(v1);j=Locate_Ve*(v2);while(i==-1||j==-1||i==j)//當連個頂點中有一個不存在與該圖中或兩個頂點位于同一位置{cout<<"頂點中有不符合要求的，請重新輸入：";cin>>v1>>v2;i=Locate_Ve*(v1);j=Locate_Ve*(v2);} //將i和j連接起來Arode*p=newArode;p->adjve*=j;p->ne*tarc=vertices[i].firstarc;vertices[i].firstarc=p;//置對稱邊Arode*q=newArode;q->adjve*=i;q->ne*tarc=vertices[j].firstarc;vertices[j].firstarc=q;}cout<<"無向圖構(gòu)造完成"<<endl;}深度搜索路徑的偽代碼voidDFS(intv){visited[v]=true;cout<<vertices[v].data<<"";Arode*p;intw;for(p=vertices[v].firstarc;p;p=p->ne*tarc){w=p->adjve*;if(!visited[w])DFS(w);}}打印出所有簡單路徑的偽代碼：voidPrint_*_Y_Path(intu,intv,intd)//求出所有從u到v的路徑，d剛進來的時候是-1{intm;d++;visited[u]=true;path[d]=u;if(u==v)//找到一條路徑，輸出該路徑{for(inti=0;i<d;i++)cout<<vertices[path[i]].data<<"-->";cout<<vertices[path[i]].data<<endl;}else{Arode*p=vertices[u].firstarc;//繼續(xù)DFSwhile(p){m=p->adjve*;if(!visited[m])//如果該頂點未被訪問過Print_*_Y_Path(m,v,d);p=p->ne*tarc;}}//恢復(fù)環(huán)境，使頂點可重新使用//路徑長度減一 visited[u]=false;d--; }};算法的具體步驟對于用戶想要查找路徑的兩個頂點，創(chuàng)立一個用于記錄路徑的數(shù)組，路徑長度為0。以其中一個頂點為起點，訪問該頂點，將該頂點參加路徑，訪問下一個未被訪問的頂點，將其參加路徑，并將路徑長度加1。假設(shè)該頂點為終點，將該路徑輸出，然后從路徑中刪除該頂點，并將路徑長度減1，訪問下一個未被訪問的頂點。假設(shè)不為終點，則訪問下一個未被訪問的頂點，直到路徑長度不小于頂點個數(shù)。當輸入的頂點不在圖中則提示錯誤。算法的時空分析算法基于DFS實現(xiàn)，運行次數(shù)和找到的路徑數(shù)有關(guān)，假設(shè)找到的路徑數(shù)為0，則時間代價為，假設(shè)找到的路徑為N，則時間代價為。輸入輸出格式：cout<<〞請輸入節(jié)點數(shù)：〞cin>>cout<<〞輸入城市編號：〞cin>>cout<<〞請輸入路徑：〞<<endl;cin>>//路徑cout<<〞請輸入查找的路徑：〞cin>>>>cout<<〞輸出所有的簡單路徑〞四結(jié)果截圖五附錄〔代碼〕#include<iostream>#include<string>usingnamespacestd;classGraphm{//Implementadjacencymatri*private: intnumVerte*,numEdge;//Storenumberofverticesedges int**matri*;//Pointertoadjacencymatri* int*mark;//Pointertomarkarraypublic: Graphm(intnumVert) {//Makegraphw/numVertvertices inti; numVerte*=numVert; numEdge=0; mark=newint[numVert];//Initializemarkarray for(i=0;i<numVerte*;i++) mark[i]=0; matri*=(int**)newint*[numVerte*];//Makematri* for(i=0;i<numVerte*;i++) matri*[i]=newint[numVerte*]; for(i=0;i<numVerte*;i++)//Edgesstartw/0weight for(intj=0;j<numVerte*;j++)matri*[i][j]=0; } intfirst(intv) {//Returnv'sfirstneighbor inti; for(i=0;i<numVerte*;i++) if(matri*[v][i]!=0)returni; returni;//Returnnifnone } intne*t(intv1,intv2) { //Getv1'sneighborafterv2 inti; for(i=v2+1;i<numVerte*;i++) if(matri*[v1][i]!=0)returni; returni; } intn() { returnnumVerte*; } inte() { returnnumEdge; } //Setedge(v1,v2)towgt voidsetEdge(intv1,intv2,intwgt) { if(wgt<0)cout<<"Illegalweightvalue"<<endl; if(matri*[v1][v2]==0)numEdge++; matri*[v1][v2]=wgt; } voiddelEdge(intv1,intv2){//Deleteedge(v1,v2) if(matri*[v1][v2]!=0)numEdge--; matri*[v1][v2]=0; } intweight(intv1,intv2){returnmatri*[v1][v2];} intgetMark(intv){returnmark[v];} voidsetMark(intv,intval){mark[v]=val;}};voidPathAll(Graphm*G,intu,intv,int*path,string*str,int&d)//d是到當前為止已走過的路徑長度，調(diào)用時初值為-1{ intw,i; G->setMark(u,1); d++; //路徑長度增1 path[d]=u; //將當前頂點添加到路徑中 if(u==v&&d>=1) //輸出一條路徑 { cout<<"這兩個城市間一條的簡單路徑為:"; for(i=0;i<=d;i++) cout<<str[path[i]]<<""; cout<<endl; } for(w=G->first(u);w<G->n();w=G->ne*t(u,w)) { if(G->getMark(w)==0) PathAll(G,w,v,path,str,d); } G->setMark(u,0);//恢復(fù)，可以再尋找 d--;//去掉這個點}intmain(){ intn; string*str; int*path; cout<<"輸入城市個數(shù)："; cin>>n; GraphmG(n); str=newstring[n]; path=newint[n]; cout<<"輸入所有城市編號！"<<endl; for(inti=0;i<n;i++) { cin