【正文】 例 已知若干個(gè)城市的地圖，求從一個(gè)城市到另一個(gè)城市 的路徑，要求路徑中經(jīng)過的城市最少。從圖中可以看出，從城市 A到城市 H要經(jīng)過若干個(gè)城市。 33 2 廣度優(yōu)先搜索的應(yīng)用 例 圖的廣度優(yōu)先搜索類似與樹的層次遍歷，逐層搜索正好可以盡快找到一個(gè)結(jié)點(diǎn)與另一個(gè)結(jié)點(diǎn)相對而言最直接的路徑。 2)將隊(duì)首所指的城市所有可直通的城市入隊(duì) (如果這個(gè)城市在隊(duì)中出現(xiàn)過就不入隊(duì) ),然后將隊(duì)首加 1，得到新的隊(duì)首城市。當(dāng)搜到城市 H時(shí)，搜索結(jié)束。 2 廣度優(yōu)先搜索的應(yīng)用 例 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 A B C D E F G H A B C D E F G H 35 1） 二維數(shù)組 jz[][]作為鄰接矩陣的存儲空間 。 3） 隊(duì)列的每個(gè)結(jié)點(diǎn)有兩個(gè)成員： sq[i].city記錄入隊(duì)的城市 ， sq[i].pre記錄該城市的前趨城市在隊(duì)列中的下標(biāo) ， 這樣通過 sq[i].pre就可以倒推出最短線路 。 2 廣度優(yōu)先搜索的應(yīng)用 例 36 2 廣度優(yōu)先搜索的應(yīng)用 例 search( ) { qh=0。 sq[1].city=1。 visited[1]=1。 //結(jié)點(diǎn)出隊(duì) for(i=1。 //結(jié)點(diǎn)入隊(duì) sq[qe].city=i。 visited[i]=1。 return。 } 37 算法分析： 時(shí)間復(fù)雜度是 O(n)；空間復(fù)雜性為 (n2)，包括圖本身的存儲空間和搜索時(shí)輔助空間“隊(duì)”的存儲空間。 while(sq[qe].pre0) { qe=sq[qe].pre。39。 } } 2 廣度優(yōu)先搜索的應(yīng)用 例 38 ? 例 迷宮是許多小方格構(gòu)成的矩形，在每個(gè)小方格中有的是墻（圖中的“ 1”），有的是路（圖中的“ 0”）。設(shè)迷宮的入口是在左上角 (1,1)，出口是右下角 (8,8)。 2 廣度優(yōu)先搜索的應(yīng)用 例 39 2 廣度優(yōu)先搜索的應(yīng)用 例 (1,1) (3,3) ? 確定圖結(jié)構(gòu) ? 本問題的原始描述，與顯式圖的標(biāo)準(zhǔn)形象有差別。 40 2 例 ? 問題 1：如何用所學(xué)過的知識來表示現(xiàn)實(shí)中的迷宮？ 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 (1,1) (3,3) ? 鄰接表？ ? 鄰接矩陣？ ? 利用 原有的迷宮數(shù)據(jù) ，檢查兩點(diǎn)之間是否存在邊相連；這樣就不必查詢?nèi)魏纹渌拇鎯Y(jié)構(gòu)了。 規(guī)律性強(qiáng)，驗(yàn)證簡單 ? 為了構(gòu)造循環(huán)體，用數(shù)組 fx[ ]={1,1 0,0},fy[ ]={0,0,1,1}模擬上下左右搜索時(shí)下標(biāo)的變化過程。 42 2 例 ? 問題 3：在尋找路徑過程中，如何實(shí)現(xiàn)所遇到的尋找策略和返回策略的解決？ 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 隊(duì)的實(shí)現(xiàn)：數(shù)組 ? 隊(duì)中結(jié)點(diǎn)有三個(gè)成員：行號、列號、前一個(gè)方格在隊(duì)列中的下標(biāo)。} sq[100]。 ? 用迷宮原有的存儲空間置元素值為“ 1”時(shí)，標(biāo)識已經(jīng)訪問過該方格。 int fx[4]={1,1,0,0},fy[4]={0,0,1,1,}。} sq[100]。 main( ) { search( )。 qe=1。 //代表訪問過 sq[1].pre=0。 sq[1].y=1。 //出隊(duì) for(k=1。 j=sq[qh].y+fy[k]。 //入隊(duì) sq[qe].x=i。 sq[qe].pre=qh。 if (sq[qe].x=8 and sq[qe].y=8) out( )。 } } print(―No avaliable way.‖)。 if (i1 or i8 or j1 or j8) flag=0。 //是否可行 return(flag)。 while(sq[qe].pre0) { qe=sq[qe].pre。} } 算法分析： 時(shí)間復(fù)雜度是 O(n)；空間復(fù)雜性為 (n2)，包括圖本身的存儲空間和搜索時(shí)輔助空間“隊(duì)”的存儲空間。若 W為曾訪問過，則以 W為新的出發(fā)點(diǎn)繼續(xù)深度優(yōu)先搜索，直至和 V有路徑相通的點(diǎn)全部訪問。 V1 V2 V4 V5 V3 V7 V6 V8 49 ? 深度優(yōu)先與廣度優(yōu)先的策略比較： ? 區(qū)別在于擴(kuò)展結(jié)點(diǎn)的過程； ? 廣度優(yōu)先搜索，擴(kuò)展 E結(jié)點(diǎn)的所有鄰接點(diǎn)， E結(jié)點(diǎn)就成為一個(gè)死結(jié)點(diǎn)。 ? 深度優(yōu)先搜索，擴(kuò)展的是 E結(jié)點(diǎn)的鄰接結(jié)點(diǎn)中的一個(gè)，并將其作為新的 E結(jié)點(diǎn)繼續(xù)擴(kuò)展；當(dāng)前 E結(jié)點(diǎn)仍為活結(jié)點(diǎn)，待搜索完其子結(jié)點(diǎn)后，回溯到該結(jié)點(diǎn)擴(kuò)展它的其它未搜索的鄰接結(jié)點(diǎn)。 1 深度優(yōu)先搜索 50 2 深度優(yōu)先搜索的應(yīng)用 例 2 (1,1) (3,3) ? 確定圖結(jié)構(gòu) ? 本問題的原始描述，與顯式圖的標(biāo)準(zhǔn)形象有差別。若行不通時(shí)，則返回上一個(gè)方格，繼續(xù)搜索其他方向。最后存儲為“ 3”的方格為可行的方格。 約束條件 52 2 深度優(yōu)先搜索的應(yīng)用 例 2 int maze[8][8]={{0,0,0,0,0,0,0,0},{0,11,1,1,0,1,0},{0,0,0,0,1,0,1, 0},{0,1,0,0,0,0,1,0},{0,1,0,1,1,0,1,0},{0,1,0,0,0,0,1,1},{0,1,0,0,1,0,0,0},{0,1,1,1,1,1,1,0}}。 int i,j,k,total。 maze[1][1]=3。 print(―Total is‖,total)。 for(k=1。k++) //搜索可達(dá)的方格 if(check(i,j,k)=1) { newi=i+fx[k]。 maze[newi][newj]=3。 else search(newi,newj)。 //某一方格只能走入死胡同 } 2 深度優(yōu)先搜索的應(yīng)用 例 2 54 Out( ) { int i,j。i=8。 for(j=1。j++) if (maze[i][j]=3) {print(―V‖)。} //統(tǒng)計(jì)總步數(shù) else print(―*‖)。 i=i+fx[k]。 //是否在迷宮內(nèi) if(i1or i8 or j1 or j8) flag=0。 return(flag)。