【正文】 return(flag)。 i=i+fx[k]。j++) if (maze[i][j]=3) {print(―V‖)。i=8。 else search(newi,newj)。k++) //搜索可達(dá)的方格 if(check(i,j,k)=1) { newi=i+fx[k]。 print(―Total is‖,total)。 int i,j,k,total。最后存儲(chǔ)為“ 3”的方格為可行的方格。 1 深度優(yōu)先搜索 50 2 深度優(yōu)先搜索的應(yīng)用 例 2 (1,1) (3,3) ? 確定圖結(jié)構(gòu) ? 本問題的原始描述，與顯式圖的標(biāo)準(zhǔ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)。} } 算法分析： 時(shí)間復(fù)雜度是 O(n)；空間復(fù)雜性為 (n2)，包括圖本身的存儲(chǔ)空間和搜索時(shí)輔助空間“隊(duì)”的存儲(chǔ)空間。 //是否可行 return(flag)。 } } print(―No avaliable way.‖)。 sq[qe].pre=qh。 j=sq[qh].y+fy[k]。 sq[1].y=1。 qe=1。} sq[100]。 ? 用迷宮原有的存儲(chǔ)空間置元素值為“ 1”時(shí)，標(biāo)識(shí)已經(jīng)訪問過該方格。 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è)成員：行號(hào)、列號(hào)、前一個(gè)方格在隊(duì)列中的下標(biāo)。 40 2 例 ? 問題 1：如何用所學(xué)過的知識(shí)來表示現(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)魏纹渌拇鎯?chǔ)結(jié)構(gòu)了。設(shè)迷宮的入口是在左上角 (1,1)，出口是右下角 (8,8)。39。 } 37 算法分析： 時(shí)間復(fù)雜度是 O(n)；空間復(fù)雜性為 (n2)，包括圖本身的存儲(chǔ)空間和搜索時(shí)輔助空間“隊(duì)”的存儲(chǔ)空間。 visited[i]=1。 //結(jié)點(diǎn)出隊(duì) for(i=1。 sq[1].city=1。 3） 隊(duì)列的每個(gè)結(jié)點(diǎn)有兩個(gè)成員： sq[i].city記錄入隊(duì)的城市 ， sq[i].pre記錄該城市的前趨城市在隊(duì)列中的下標(biāo) ， 這樣通過 sq[i].pre就可以倒推出最短線路 。當(dāng)搜到城市 H時(shí)，搜索結(jié)束。 33 2 廣度優(yōu)先搜索的應(yīng)用 例 圖的廣度優(yōu)先搜索類似與樹的層次遍歷，逐層搜索正好可以盡快找到一個(gè)結(jié)點(diǎn)與另一個(gè)結(jié)點(diǎn)相對(duì)而言最直接的路徑。} //訪問過的 vj入隊(duì) } } 32 例 已知若干個(gè)城市的地圖，求從一個(gè)城市到另一個(gè)城市 的路徑，要求路徑中經(jīng)過的城市最少。jGn。 //訪問源點(diǎn) vk visited[k]=1。 } //找 vi的下一鄰接點(diǎn) } 31 1 廣度優(yōu)先搜索 鄰接矩陣表示圖的算法 bfsm(int k, graph g[][100],int n) { int i,j。 //取 vi的邊表頭指針 while(pnull) //擴(kuò)展 E結(jié)點(diǎn) { if(visited[padjvex]=0) //若 vj未訪問過 { print (―visit vertex‖,padjvex)。 visited[k]=1。 //n 為結(jié)點(diǎn)個(gè)數(shù) bfs(int k,graph head[]) { int i。 //從頂點(diǎn) v 開始的廣度優(yōu)先搜索 把頂點(diǎn) v標(biāo)記為已到達(dá)頂點(diǎn)； 初始化隊(duì)列 Q，其中僅包含一個(gè)元素 v。實(shí)際應(yīng)用中，用數(shù)組或鏈表實(shí)現(xiàn)隊(duì)列。 問題狀態(tài) 狀態(tài)空間 解狀態(tài) 答案狀態(tài) ● ● ● ● ● ● ● 25 二、廣度優(yōu)先搜索 ? 1 圖的廣度優(yōu)先遍歷 /搜索算法 ? 2 廣度優(yōu)先搜索的應(yīng)用 ? 例 求經(jīng)過城市最少的路線問題 ? 例 走迷宮問題 26 1 廣度優(yōu)先搜索 ? 廣度優(yōu)先搜索 ? 首先訪問出發(fā)點(diǎn) V，接著依次訪問 V的所有鄰接點(diǎn){Wi}，再依次訪問分別與 {Wi}鄰接的所有未曾訪問過的頂點(diǎn)， …… ，直至與 V相通的頂點(diǎn)都已訪問，若此時(shí)還有未訪問的頂點(diǎn)，則按相同的過程繼續(xù)。 24 3 圖搜索術(shù)語 amp。 23 3 圖搜索術(shù)語 amp。 ? 狀態(tài)空間 :由根結(jié)點(diǎn)到其它結(jié)點(diǎn)的所有路徑（分支），就確定了這個(gè)問題的狀態(tài)空間。 ? 啟發(fā)式搜索 是利用一些啟發(fā)信息，提前判斷出先搜索哪些狀態(tài)可能盡快找到問題的解或某些情況不可能取到最優(yōu)解，從而可以提前舍棄對(duì)這些狀態(tài)的嘗試。若表示為樹形就是一個(gè) n度樹，這樣的樹有 n! 個(gè)葉結(jié)點(diǎn)，所以每一個(gè)遍歷樹中所有節(jié)點(diǎn)的算法都必須耗時(shí) O(n! ) 20 2 顯式圖 amp。隱式圖 子集樹 ? 共 2n 個(gè)狀態(tài)。 ? 兩種典型的隱式圖：子集樹，排列樹 17 2 顯式圖 amp。重復(fù)上述過程，直到全部頂點(diǎn)都訪問完畢 。 13 從圖的任意指定頂點(diǎn)出發(fā)，依照某種規(guī)則去訪問圖中所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問一次，此過程叫做 圖的遍歷 。 找出度易，找入度難。 ? 無向圖中頂點(diǎn) vi 的度為第 i 個(gè)單鏈表中的結(jié)點(diǎn)數(shù)。 頂點(diǎn) vi的 入 度 是鄰接矩陣中第 i列 1的個(gè)數(shù)。 ? 有向圖鄰接矩陣不一定對(duì)稱；有 n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為 n178。 v2 v1 v3 v4 強(qiáng)連通分量： 有向圖的極大強(qiáng)連通子圖；任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即其本身；非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。是連通的 。 簡(jiǎn)單路徑： 序列中頂點(diǎn) (兩端點(diǎn)除外 )不重復(fù)出現(xiàn)的路徑。)， 滿足 (vi, j1, vi, j)?VR 或 vi, j1, vi, j ?VR (1 ? j ? m)。 度： 入度和出度之和，即： TD(v) = ID(v) + OD(v)?；?是頂點(diǎn)的有序?qū)Γ? 邊是頂點(diǎn)的無序?qū)?。 把根結(jié)點(diǎn)刪除樹就變成了森林。 有序樹： 樹中結(jié)點(diǎn)的各子樹從左至右有次序 (最左邊的為第一個(gè)孩子