隊列應用——廣度優(yōu)先搜索.doc

《隊列應用——廣度優(yōu)先搜索.doc》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、隊列應用——廣度優(yōu)先搜索如圖：求出從節(jié)點1到節(jié)點8的最短路徑的長度（1到8最少的邊數(shù)）。使用計算機求解的問題中，有許多問題是無法用數(shù)學公式進行計算推導找出答案的。就像這一題，需窮舉從節(jié)點1到節(jié)點8的所有路徑才能找到答案。窮舉是最樸素的搜索。窮舉所有路徑，面對大規(guī)模數(shù)據(jù)將是很可怕的，采用廣度優(yōu)先搜索法(BFS)，就不必窮舉所有路徑，大大提高效率。用廣度優(yōu)先搜索法解答此題的過程：1.先搜索所有節(jié)點中距節(jié)點1最近的點——節(jié)點1（距離為0）；2.再搜索與節(jié)點1距離為1的節(jié)點——2，3，5；3.然后搜索與節(jié)點

2、1距離為2的節(jié)點——與節(jié)點2，3，5中某點距離為1且尚未搜索過的節(jié)點——6，7，4，9；4.再搜索距節(jié)點1距離為3的節(jié)點——與節(jié)點6，7，4，9中的某點距離為1且尚未搜索過的節(jié)點——8；由以上過程可以確定1到8的最短距離為3（可以用反證法證明此結論的正確性）。整個過程如下圖：可以看出搜索的過程是“一層一層”的，從第一層開始，每層的節(jié)點都會被“用”來產生下一層的節(jié)點，當這一層的節(jié)點被“用完”后，才用它們所產生的下一層節(jié)點來產生新的節(jié)點層，而同一層的節(jié)點可以按任意順序“使用”，一般采用的原則是先生成的結

3、點先“使用”。對“使用”一詞，更恰當?shù)恼f法是“擴展”。廣度優(yōu)先搜索算法中，為了便于進行搜索，要設置一個表存儲所有的節(jié)點，為了滿足先生成的節(jié)點層（節(jié)點）先擴展的原則，存儲節(jié)點的表一般設計成隊列的數(shù)據(jù)結構。搜索過程中不斷地從隊列頭取出節(jié)點進行擴展。對生成的新節(jié)點，要檢查它是否已在隊列中存在，還要檢查它是否目標節(jié)點。如果新節(jié)點是目標節(jié)點，則搜索成功，程序結束；若新節(jié)點不是目標節(jié)點，并且未曾在隊列中出現(xiàn)過，則將它加入到隊列尾，否則將它丟棄，再從隊列頭取出節(jié)點進行擴展......。最終可能產生兩種結果：找到目

4、標節(jié)點，或擴展完所有節(jié)點有找到目標節(jié)點。題一：求兩點間的最短路徑長度在一由n（1<=n<=100）個節(jié)點，m(1<=m<=n*(n-1)/2)條邊構成的圖中，求出節(jié)點s到t的最短路徑長度。輸入（input.txt）：第一行n,m,s,t;接下來m行，每行兩個整數(shù)i，j（1<=i,j<=n)，表示i，j間有一條邊。輸出(output.txt)：S到t的最短路徑的長度（從s到t經過的最少邊數(shù)），若從s無法到達t，輸出-1.分析：布爾數(shù)組bVisited[i]非零表示節(jié)點i已在隊列中，為零表示尚未入隊；布

5、爾數(shù)組bAdj[i][j]非零表示節(jié)點i與節(jié)點j之間有一條邊，否則無邊；隊列q[],隊首iH,隊尾iT;step[i]表示起點到節(jié)點i的最短距離。（數(shù)據(jù)見習題）源代碼：#includeusingnamespacestd;ifstreamfin("input.txt");ofstreamfout("output.txt");constintLQ=110,N=110;intbNoAns,bVisited[N]={0},bAdj[N][N]={0};intn,m,s,t,iH,iT,q[

6、LQ],step[N]={0};intInputDataAndInitialize(void);intBFS(void);intOutputAnswer(void);intmain(intargc,char*argv[]){InputDataAndInitialize();BFS();OutputAnswer();return0;}intInputDataAndInitialize(void){fin>>n>>m>>s>>t;inti,j;for(;m--;){fin>>i>>j;bAdj[i][j

7、]=bAdj[j][i]=1;}for(i=1;i<=n;++i)bAdj[i][i]=0;iH=0;iT=1;q[0]=s;bVisited[s]=1;bNoAns=1;return1;}intBFS(void){if(q[0]==t){bNoAns=0;return1;}inti,j;while(iH

8、ted[j]=1;if(j==t){bNoAns=0;return1;}}}}return1;}intOutputAnswer(void){if(bNoAns){fout<<"-1";return1;}fout<