算法設(shè)計(jì)實(shí)例教程 課件 第4章 查 找-算法設(shè)計(jì)實(shí)例教程

算法設(shè)計(jì)實(shí)例教程教學(xué)分析目錄CONCENTS123456789第4章查找第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第3章排序算法第5章字符串和高精度運(yùn)算第6章圖論算法第7章動(dòng)態(tài)規(guī)劃算法第8章計(jì)算幾何基礎(chǔ)第9章高級(jí)算法查找也稱搜索，搜索算法是利用計(jì)算機(jī)的高性能來有目的的窮舉一個(gè)問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。現(xiàn)階段一般有枚舉算法、深度優(yōu)先搜索、廣度優(yōu)先搜索、A*算法、回溯算法、蒙特卡洛樹搜索、散列函數(shù)等算法。在大規(guī)模實(shí)驗(yàn)環(huán)境中，通常通過在搜索前，根據(jù)條件降低搜索規(guī)模；根據(jù)問題的約束條件進(jìn)行剪枝；利用搜索過程中的中間解，避免重復(fù)計(jì)算這幾種方法進(jìn)行優(yōu)化。第4章查找4.1.1順序查找的基本概念

順序查找算法又稱順序搜索算法或者線性搜索算法，是所有查找算法中最基本、最簡(jiǎn)單的，對(duì)應(yīng)的時(shí)間復(fù)雜度為O(n)。順序查找算法適用于絕大多數(shù)場(chǎng)景，既可以在有序序列中查找目標(biāo)元素，也可以在無序序列中查找目標(biāo)元素。其基本思想是從線性表的第1個(gè)元素開始，通過逐個(gè)比較表中的關(guān)鍵字，直到找到符合要求的關(guān)鍵字，完成查找，或搜索整個(gè)表，沒有找到符合要求的關(guān)鍵字，則表示查找失敗。但是這種查找方法的效率較低，主要針對(duì)數(shù)量較少，無規(guī)則的數(shù)據(jù)。如果查找表中的數(shù)據(jù)已經(jīng)按順序排列，則可以使用一種稱為二分查找的方法。。4.1順序查找時(shí)間限制：1000ms內(nèi)存限制：65535KB問題描述輸入10個(gè)數(shù)，要求輸出其中的最大值。輸入說明測(cè)試數(shù)據(jù)有多組，每組10個(gè)數(shù)。輸出說明對(duì)于每組輸入,請(qǐng)輸出其最大值（有回車）。輸入樣例102223152657985963240輸出樣例max=1524.1.2順序查找的應(yīng)用舉例1：找最大值

算法分析創(chuàng)建一個(gè)數(shù)組以及創(chuàng)建一個(gè)變量max，給變量max賦初值為然后跟數(shù)組中每個(gè)元素一一進(jìn)行判斷，如果數(shù)組中的數(shù)比max大那么把這個(gè)數(shù)賦給max，以此類推，直到查找完數(shù)組中的所有元素即可完成查找，停止運(yùn)算。實(shí)現(xiàn)的代碼如下：intmain(){intd[10],i,max;for(i=0;i<10;i++)scanf("%d",&d[i]);max=d[0];for(i=1;i<10;i++){if(max<d[i])max=d[i];}printf("max=%d\n",max);return0;}時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述輸入一行字符串，計(jì)算其中A-Z大寫字母出現(xiàn)的次數(shù)。輸入說明案例可能有多組，每個(gè)案例輸入為一行字符串。輸出說明對(duì)每個(gè)案例按A-Z的順序輸出其中大寫字母出現(xiàn)的次數(shù)。輸入樣例DFJEIWFNQLEF0395823048+_+JDLSFJDLSJFKK4.1.3順序查找的應(yīng)用舉例2：字母統(tǒng)計(jì)

輸出樣例A:0B:0C:0D:3E:2F:5G:0H:0I:1J:4K:2L:3M:0N:1O:0P:0Q:1R:0S:2T:0U:0V:0W:1X:0Y:0Z:04.1.3順序查找的應(yīng)用舉例2：字母統(tǒng)計(jì)

算法分析該問題的策略就是建立一個(gè)長(zhǎng)度為26的整型數(shù)組用來統(tǒng)計(jì)每個(gè)字母的出現(xiàn)次數(shù)，然后依次遍歷字符串中的每一個(gè)字符，對(duì)字符進(jìn)行判斷，如果該字符是某個(gè)字母，就將該字母對(duì)應(yīng)的統(tǒng)計(jì)數(shù)據(jù)加1。代碼如下：intmain(){charstr[10000]={0};intcount[26]={0};inti;while(scanf("%s",str)!=EOF){for(i=0;i<strlen(str);i++){if('A'<=str[i]&&str[i]<='Z'){count[str[i]-'A']++;}}for(i=0;i<26;i++){printf("%c:%d\n",'A'+i,count[i]);}}return0;}4.2.1二分查找的基本概念二分查找又稱折半查找、二分搜索、折半搜索等，是一種采用了分治策略的查找算法。二分查找只能用于有序線性表的查找。假設(shè)在一個(gè)長(zhǎng)度為n的有序數(shù)組中查找一個(gè)數(shù)字，如果使用順序查找的方式逐一檢查數(shù)組中的每個(gè)數(shù)字，那么需要O（n）的時(shí)間復(fù)雜度，而如果使用二分查找，時(shí)間復(fù)雜度可以優(yōu)化到O（logn）。隨著線性表的規(guī)模n越大，二分查找在時(shí)間性能上的優(yōu)越性就會(huì)越明顯。4.2二分查找

4.2.1二分查找的基本概念二分查找的查找策略是：每次將位于線性表中間的數(shù)字和目標(biāo)數(shù)字比較。如果中間數(shù)字正好等于目標(biāo)數(shù)字，那么就找到了目標(biāo)數(shù)字。如果中間數(shù)字大于目標(biāo)數(shù)字，那么下一次查找的時(shí)候只需要在線性表的前半部分找，這是因?yàn)榫€性表是排序的，后半部分的數(shù)字都大于或等于中間數(shù)字，所以一定都大于目標(biāo)數(shù)字，也就沒有必要再在后半部分查找。如果中間數(shù)字小于目標(biāo)數(shù)字，那么接下來只需要查找線性表的后半部分，這是因?yàn)榕判驍?shù)組的前半部分的數(shù)字都小于或等于中間數(shù)字，所以一定都小于目標(biāo)數(shù)字，也就沒有必要再在前半部分查找。從查找的過程可以看出，二分查找是一種遞歸的過程。由于二分查找算法每次都將查找范圍減少一半，對(duì)于包含n個(gè)元素的列表，用二分查找最多需要log2n步。但是由于二分查找要求待查找的數(shù)據(jù)必須是線性有序的，對(duì)于沒有經(jīng)過排序的數(shù)據(jù)，可以通過排序算法進(jìn)行預(yù)排序，然后進(jìn)行二分查找的操作。4.2二分查找

時(shí)間限制：1000ms內(nèi)存限制：65535KB問題描述有n個(gè)已經(jīng)從小到大排序好的數(shù)據(jù)（不重復(fù)），從鍵盤輸入一個(gè)數(shù)，用二分查找方法，判斷target是否在這n個(gè)數(shù)中。輸入說明第1行，數(shù)組的長(zhǎng)度length第2行，n個(gè)整數(shù)（int范圍內(nèi)，不重復(fù)），中間用空格分隔；第3行，整數(shù)target。輸出說明如果找到target，輸出其位置；否則輸出-1。4.2.2二分查找的應(yīng)用舉例1：查找元素x

輸入樣例10102030405060708090100906-10359122輸出樣例8-1算法分析使用二分查找算法在一個(gè)已排序（升序）的數(shù)組中查找一個(gè)指定的元素，首先將這個(gè)待查找元素與數(shù)列中位于中間位置的元素進(jìn)行比較，如果比中間位置的元素大，則繼續(xù)在后半部分的數(shù)列中進(jìn)行二分查找；如果比中間位置的元素小，則在數(shù)列的前半部分進(jìn)行比較；如果相等，則找到了元素的位置。每次比較的數(shù)列長(zhǎng)度都會(huì)是之前數(shù)列的一半，直到找到相等元素的位置或者最終沒有找到要找的元素。1.循環(huán)方式intsearch_loop(inta[],intsize,inttarget){intleft=0,mid;intright=size-1;while(left<=right){mid=left+(right-left)/2;//定位查找區(qū)間的中間元素if(a[mid]>target)right=mid-1;//待查元素在mid元素的左邊區(qū)域elseif(a[mid]<target)left=mid+1;//待查找元素在mid元素的右邊區(qū)域else//a[mid]就是要查找的元素returnmid;}return-1;//沒有找到目標(biāo)值}4.2.2二分查找的應(yīng)用舉例1：查找元素x

在上面的函數(shù)定義中，分別使用了left和right兩個(gè)變量記住查找的范圍。初始情況下left為0，right為數(shù)組長(zhǎng)度-1，分別指向數(shù)組的起始和結(jié)束位置。隨著查找的推進(jìn)，每次都根據(jù)判斷的結(jié)果，更新left或者right的值，直到left>right就結(jié)束循環(huán)。如果直到循環(huán)結(jié)束都沒有找到目標(biāo)值，則輸出-1。2.遞歸方式由于每次查找的方法是一樣的，不一樣的僅僅是查找的數(shù)組的范圍，因此遞歸是一種很直觀的實(shí)現(xiàn)方式。用一對(duì)整數(shù)變量表示目標(biāo)元素的查找區(qū)間的起始和結(jié)束位置，并作為參數(shù)傳遞給遞歸函數(shù)。隨著查找范圍的不斷縮小，直到查找區(qū)間包含的元素個(gè)數(shù)少于或等于1個(gè)，查找就停止了。實(shí)現(xiàn)代碼如下：intsearch_recur(inta[],intleft,intright,inttarget){intmid;if(left>right)return-1;//沒有找到目標(biāo)值mid=left+(right-left)/2;//定位查找區(qū)間的中間元素if(a[mid]>target)search_recur(a,left,mid-1,target);//遞歸地查找mid左邊區(qū)域elseif(a[mid]<target)search_recur(a,mid+1,right,target);//遞歸地查找mid右邊區(qū)域else//a[mid]就是要查找的元素returnmid;}4.2.2二分查找的應(yīng)用舉例1：查找元素x

4.2.2二分查找的應(yīng)用舉例1：查找元素

遞歸的優(yōu)勢(shì)就是代碼簡(jiǎn)潔，且能夠直觀的對(duì)應(yīng)解決問題的思路，但存在的問題是內(nèi)存消耗太大。main函數(shù)實(shí)現(xiàn)如下：intmain(){intlength,target,i;while(scanf("%d",&length)!=EOF){for(i=0;i<length;i++)scanf("%d",&a[i]);scanf("%d",&target);printf("%d\n",search_recur(a,0,length-1,target));}return0;}時(shí)間限制：1000ms內(nèi)存限制：65535KB問題描述統(tǒng)計(jì)一個(gè)數(shù)字在一個(gè)有序數(shù)組中出現(xiàn)的次數(shù)。比如輸入一個(gè)有序數(shù)組{1,2,2,2,3,3,3,4,5}和數(shù)字2，由于2在數(shù)組中出現(xiàn)了3次，因此程序的輸出結(jié)果為3。輸入說明第1行，數(shù)組的長(zhǎng)度第2行，一個(gè)有序數(shù)組{1,2,2,2,3,3,3,4,5}第3行，1個(gè)待查找的整數(shù)target。輸出說明如果數(shù)組中包含target，則輸出其在數(shù)組中出現(xiàn)的次數(shù)位置；否則輸出0。輸入樣例1012223334552輸出樣例34.2.3二分查找的應(yīng)用舉例2：統(tǒng)計(jì)數(shù)字在有序數(shù)組中出現(xiàn)的次數(shù)

4.2.3二分查找的應(yīng)用舉例2：統(tǒng)計(jì)數(shù)字在有序數(shù)組中出現(xiàn)的次數(shù)

算法分析一種直觀的方式是使用順序查找的方式遍歷整個(gè)數(shù)組，只要找到某個(gè)元素目標(biāo)元素target相等，則統(tǒng)計(jì)值加1。由于對(duì)數(shù)組的n個(gè)元素都進(jìn)行了一次檢查，所以該算法的時(shí)間復(fù)雜度為O(n)。使用二分查找在數(shù)組中查找元素target在數(shù)組中的位置，由于數(shù)組是有序的，因此所有相等的值在數(shù)組中的位置是連續(xù)的，因此可以繼續(xù)在該位置的前后查找與target相等的元素。前面已經(jīng)分析過，二分查找能夠快速的縮小查找的范圍，將算法的時(shí)間復(fù)雜度降低到O(logn)。使用二分查找法進(jìn)行數(shù)字統(tǒng)計(jì)的函數(shù)實(shí)現(xiàn)如下：intnum(inta[],intsize,inttarget){intleft=0,right=size-1,mid,sum=0;inti;while(left<=right){mid=left+(right-left)/2;//定位查找區(qū)間的中間元素if(a[mid]>target)right=mid-1;//待查元素在mid元素的左邊區(qū)域elseif(a[mid]<target)left=mid+1;//待查找元素在mid元素的右邊區(qū)域else//a[mid]就是要查找的元素{sum=1;//找到了一個(gè)目標(biāo)元素break;}}for(i=mid+1;i<size&&a[i]==target;i++)//向左統(tǒng)計(jì)sum++;for(i=mid-1;i>0&&a[i]==target;i--)//向右統(tǒng)計(jì)sum++;returnsum;4.2.3二分查找的應(yīng)用舉例2：統(tǒng)計(jì)數(shù)字在有序數(shù)組中出現(xiàn)的次數(shù)

在順序查找和二分查找中，算法要處理的數(shù)據(jù)以線性表的形式表示。在線性表中，數(shù)據(jù)元素之間是線性關(guān)系，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。但是在圖中，任意兩個(gè)數(shù)據(jù)元素之間都可能存在直接的關(guān)系，通常用節(jié)點(diǎn)表示數(shù)據(jù)元素，用連接兩個(gè)節(jié)點(diǎn)的邊表示數(shù)據(jù)元素之間的關(guān)系。圖的搜索算法通常用來解決基于狀態(tài)空間的搜索問題。所謂狀態(tài)就是為了區(qū)分不同事物而引入的一組數(shù)據(jù)元組，如X=[x1,x2,x3...xn]，其中每一個(gè)元素xi被稱為狀態(tài)分量。首先把問題表示轉(zhuǎn)化為一個(gè)由多個(gè)狀態(tài)組成的集合，如果可以通過一些定義好的運(yùn)算使得某個(gè)狀態(tài)跳轉(zhuǎn)到下一個(gè)狀態(tài)，那么這兩個(gè)狀態(tài)之間就形成了一個(gè)關(guān)聯(lián)關(guān)系。所有的狀態(tài)，以及狀態(tài)之間的關(guān)聯(lián)關(guān)系就形成了一個(gè)拓?fù)鋱D。解題的過程就是對(duì)圖的搜索。對(duì)一個(gè)圖進(jìn)行搜索意味著從圖中的一個(gè)節(jié)點(diǎn)開始，按照某種特定的順序依次遍歷圖中的邊，從而找到一條從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，或是遍歷圖中所有的節(jié)點(diǎn)，找到符合檢索要求的節(jié)點(diǎn)。按照搜索順序的不同，可以將搜索算法分為廣度優(yōu)先算法和深度優(yōu)先搜索。4.3圖的搜索

DFS（DepthFirstSearch），即深度優(yōu)先搜索。其搜索策略是：從圖中某節(jié)點(diǎn)v出發(fā)，沿著一條路徑一直搜索下去，當(dāng)無法搜索時(shí)，回退到剛剛訪問過的節(jié)點(diǎn)。具體說來包括以下幾個(gè)步驟：4.3.1DFS的基本概念

（1）初始化圖中的所有節(jié)點(diǎn)，將它們都標(biāo)記為未被訪問。（2）從圖中的某個(gè)節(jié)點(diǎn)v出發(fā)，訪問v并標(biāo)記其已被訪問。（3）依次檢查v的所有鄰接點(diǎn)w，如果w未被訪問，則從w出發(fā)進(jìn)行深度優(yōu)先遍歷（遞歸調(diào)用，重復(fù)步驟2～3），這一過程一直進(jìn)行到已發(fā)現(xiàn)從出發(fā)節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。（4）如果當(dāng)前已經(jīng)沒有未被訪問的鄰接節(jié)點(diǎn)時(shí)，則回退到上一步剛剛訪問過的節(jié)點(diǎn)，繼續(xù)重復(fù)步驟2~3。按照深度優(yōu)先搜索，當(dāng)搜索到某一步時(shí)，發(fā)現(xiàn)原先的選擇并不是最優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)被稱為回溯法，而滿足回溯條件的某個(gè)狀態(tài)被稱為“回溯點(diǎn)”。4.3.1DFS的基本概念

按照深度優(yōu)先搜索算法遍歷圖中的節(jié)點(diǎn)，我們會(huì)發(fā)現(xiàn)后被訪問的節(jié)點(diǎn)，其鄰接點(diǎn)先被訪問，這是典型的后來者先服務(wù)，可以借助于棧的結(jié)構(gòu)來實(shí)現(xiàn)。由于遞歸本身就是使用棧實(shí)現(xiàn)的，因此使用遞歸的方法更方便。深度優(yōu)先搜索算法可以用以下偽代碼來表示：voidDFS(GraphG,nodev){nodew;visit(v);visited[v]=True;for(w=FirstNeighbor(G,v);w!=null;w=NextNeighbor(G,v))if(!visited[w])DFS(G,w);}從圖G中的某一個(gè)節(jié)點(diǎn)v開始，首先訪問節(jié)點(diǎn)v，并將v的狀態(tài)設(shè)置為已訪問。隨后依次對(duì)v的所有鄰接節(jié)點(diǎn)w進(jìn)行遍歷，如果w是一個(gè)未被訪問過的節(jié)點(diǎn)，則繼續(xù)使用深度優(yōu)先搜索算法以w為出發(fā)節(jié)點(diǎn)進(jìn)行搜索。由于算法是遞歸調(diào)用的，當(dāng)v的某個(gè)鄰接節(jié)點(diǎn)w訪問不下去的時(shí)候，函數(shù)返回到v，繼續(xù)對(duì)v的下一個(gè)鄰接節(jié)點(diǎn)使用DFS展開搜索。。4.3.1DFS的基本概念

下面以下圖為例模擬深度優(yōu)先搜索算法的搜索路線。4.3.1DFS的基本概念

圖4-1二叉樹樹是圖的一種特殊形式，是連通且沒有回路的圖。圖中所示的是一棵二叉樹，即每個(gè)父節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)，其中一個(gè)是左子節(jié)點(diǎn)，一個(gè)是右子節(jié)點(diǎn)?，F(xiàn)在我們要使用深度優(yōu)先算法遍歷樹中的每一個(gè)節(jié)點(diǎn)，那么節(jié)點(diǎn)編號(hào)所組成的序列就是遍歷的順序。假設(shè)我們規(guī)定對(duì)每一個(gè)節(jié)點(diǎn)來說，先訪問其左子節(jié)點(diǎn)，后訪問其右子節(jié)點(diǎn)。按照深度優(yōu)先搜索算法：（1）從根節(jié)點(diǎn)1開始（2）先訪問1的左子節(jié)點(diǎn)2，然后以遞歸的方式遍歷以2為根節(jié)點(diǎn)的子樹，以此類推，得到1→2→4→7遍歷序列。（3）到達(dá)節(jié)點(diǎn)7后，發(fā)現(xiàn)其沒有左子節(jié)點(diǎn)，也沒有右子節(jié)點(diǎn)，于是返回到節(jié)點(diǎn)4，節(jié)點(diǎn)4的也沒有右子節(jié)點(diǎn)，于是繼續(xù)向上返回到節(jié)點(diǎn)2，節(jié)點(diǎn)2有右子節(jié)點(diǎn)，于是訪問節(jié)點(diǎn)5，更新遍歷序列為1→2→4→7→5。（4）節(jié)點(diǎn)5既沒有左子節(jié)點(diǎn)，也沒有右子節(jié)點(diǎn)，于是返回到其父節(jié)點(diǎn)2。此時(shí)節(jié)點(diǎn)2完成了其所有子節(jié)點(diǎn)的遍歷，于是繼續(xù)向上返回到節(jié)點(diǎn)1。（5）此時(shí)節(jié)點(diǎn)1已完成了左節(jié)點(diǎn)的遍歷，繼續(xù)訪問其右節(jié)點(diǎn)3，更新遍歷序列為1→2→4→7→5→3。節(jié)點(diǎn)3沒有左子節(jié)點(diǎn)，于是訪問其右節(jié)點(diǎn)6，更新遍歷序列為1→2→4→7→5→3→6。（6）節(jié)點(diǎn)6先訪問左子節(jié)點(diǎn)8，由于節(jié)點(diǎn)8沒有子節(jié)點(diǎn)，于是完成訪問后返回節(jié)點(diǎn)6，然后訪問節(jié)點(diǎn)6的右子節(jié)點(diǎn)9，更新遍歷序列為1→2→4→7→5→3→6→8→9。同樣，由于節(jié)點(diǎn)9也沒有子節(jié)點(diǎn)，于是完成訪問后返回節(jié)點(diǎn)6。（7）節(jié)點(diǎn)6已完成其所有子節(jié)點(diǎn)的訪問，于是返回節(jié)點(diǎn)3，同樣，節(jié)點(diǎn)3也完成了所有子節(jié)點(diǎn)的訪問，于是返回節(jié)點(diǎn)1，完成所有節(jié)點(diǎn)的遍歷和遞歸訪問。得到結(jié)論，基于深度優(yōu)先搜索算法遍歷該樹的所有節(jié)點(diǎn)時(shí)，訪問序列為：1→2→4→7→5→3→6→8→9。4.3.1DFS的基本概念

BFS（BreadthFirstSearch），即廣度優(yōu)先搜索。其搜索策略是：從起點(diǎn)開始，對(duì)與其鄰接的所有節(jié)點(diǎn)都訪問一邊，然后依次從這些已經(jīng)訪問過的鄰接點(diǎn)出發(fā)，再對(duì)它們的鄰接點(diǎn)進(jìn)行訪問。具體說來包括以下幾個(gè)步驟：4.3.2BFS的基本概念

（1）初始化所有節(jié)點(diǎn)均未被訪問，并初始化一個(gè)空隊(duì)列。（2）從圖中的某個(gè)節(jié)點(diǎn)v出發(fā)，訪問v并標(biāo)記其已被訪問，將v入隊(duì)列。（3）如果隊(duì)列非空，則繼續(xù)執(zhí)行，否則算法結(jié)束。（4）將隊(duì)頭元素v移出隊(duì)列，依次訪問v的所有未被訪問的鄰接點(diǎn)，標(biāo)記已被訪問并將它們加入隊(duì)的尾部。轉(zhuǎn)向步驟3。按照廣度優(yōu)先搜索算法遍歷圖中的節(jié)點(diǎn)，我們會(huì)發(fā)現(xiàn)每次都是從隊(duì)列的頭部拿出一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展，而新擴(kuò)展出的節(jié)點(diǎn)都是加到隊(duì)列的尾部，因此所有的節(jié)點(diǎn)按照先進(jìn)先出的順序被訪問，可以借助于隊(duì)列的結(jié)構(gòu)來實(shí)現(xiàn)。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，你不能隨機(jī)地訪問隊(duì)列中的元素。隊(duì)列只支持兩種操作：入隊(duì)和出隊(duì)。4.3.2BFS的基本概念

廣度優(yōu)先搜索算法可以用以下偽代碼來表示：voidBFS(GraphG,nodev){初始化一個(gè)空隊(duì)列queue;將nodev加入queue頭部；while(queue不為空){nodev=queue_front();visited[v]=True；pop_front(queue);for(w=FirstNeighbor(G,v);w!=null;w=NextNeighbor(G,v))if(!visited[w])將節(jié)點(diǎn)w加入queue尾部；}}下面依然以圖4-1為例模擬廣度優(yōu)先搜索算法的搜索路線。按照廣度優(yōu)先搜索算法：（1）隊(duì)列初始條件下為空queue={}；（2）從根節(jié)點(diǎn)1開始，將節(jié)點(diǎn)1放入隊(duì)列，得到隊(duì)列為{1}。（3）將隊(duì)列中的第一個(gè)元素1取出來，將其標(biāo)記為已訪問，并將1的所有未訪問的鄰接節(jié)點(diǎn)放入隊(duì)列的尾部，隊(duì)列更新為{2，3}，訪問序列為1。（4）將隊(duì)列中的第一個(gè)元素2取出來，將其標(biāo)記為已訪問，并將2的所有未訪問的鄰接節(jié)點(diǎn)放入隊(duì)列的尾部，隊(duì)列更新為{3，4，5}，訪問序列為1→2。（5）將隊(duì)列中的第一個(gè)元素3取出來，將其標(biāo)記為已訪問，并將3的所有未訪問的鄰接節(jié)點(diǎn)放入隊(duì)列的尾部，隊(duì)列更新為{4，5，6}，訪問序列為1→2→3。（6）將隊(duì)列中的第一個(gè)元素4取出來，將其標(biāo)記為已訪問，并將4的所有未訪問的鄰接節(jié)點(diǎn)放入隊(duì)列的尾部，隊(duì)列更新為{5，6，7}，訪問序列為1→2→3→4。4.3.2BFS的基本概念

（7）將隊(duì)列中的第一個(gè)元素5取出來，將其標(biāo)記為已訪問，由于5沒有未訪問的鄰接節(jié)點(diǎn)，于是隊(duì)列更新為{6，7}，訪問序列為1→2→3→4→5。（8）將隊(duì)列中的第一個(gè)元素6取出來，將其標(biāo)記為已訪問，并將6的所有未訪問的鄰接節(jié)點(diǎn)放入隊(duì)列的尾部，隊(duì)列更新為{7，8，9}，訪問序列為1→2→3→4→5→6。（9）將隊(duì)列中的第一個(gè)元素7取出來，將其標(biāo)記為已訪問，由于7沒有未訪問的鄰接節(jié)點(diǎn)，隊(duì)列更新為{8，9}，訪問序列為1→2→3→4→5→6→7。（10）將隊(duì)列中的第一個(gè)元素8取出來，將其標(biāo)記為已訪問，由于8沒有未訪問的鄰接節(jié)點(diǎn)，隊(duì)列更新為{9}，訪問序列為1→2→3→4→5→6→7→8。（11）將隊(duì)列中的第一個(gè)元素9取出來，將其標(biāo)記為已訪問，由于9沒有未訪問的鄰接節(jié)點(diǎn)，隊(duì)列更新為{}，訪問序列為1→2→3→4→5→6→7→8→9。（12）由于隊(duì)列為空，結(jié)束循環(huán)，搜索結(jié)束，最終得到的樹的廣度優(yōu)先搜索序列為1→2→3→4→5→6→7→8→94.3.2BFS的基本概念

時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述輸入一個(gè)包含n個(gè)節(jié)點(diǎn)的樹，節(jié)點(diǎn)編號(hào)依次為0、1...n-1，以及一個(gè)包含n-1條無向邊的edges列表，其中edges[i]=[a,b]表示節(jié)點(diǎn)a和節(jié)點(diǎn)b中存在一條無向邊。當(dāng)選擇其中任何一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)時(shí)，都可形成一棵高度為h的樹。在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。要求找到所有的最小高度樹，并依次輸出它們的根節(jié)點(diǎn)編號(hào)。輸入說明一個(gè)整數(shù)n，代表樹的節(jié)點(diǎn)數(shù)。一個(gè)二維矩陣edges，表示樹的邊輸出說明所有最小高度樹的根節(jié)點(diǎn)編號(hào)。輸入樣例n=4edges=[[1,0],[1,2],[1,3]]輸出樣例[1]4.3.3DFS與BFS的應(yīng)用舉例1：最小高度樹

算法分析以樣例輸入為例，該樹包括4個(gè)節(jié)點(diǎn)，3條邊，當(dāng)我們選擇其中任何一個(gè)節(jié)點(diǎn)作為樹根時(shí)，都可以相應(yīng)構(gòu)造出一棵樹，樹的結(jié)構(gòu)如下：4.3.3DFS與BFS的應(yīng)用舉例1：最小高度樹

圖4-2不同高度的樹其中最小高度樹是以節(jié)點(diǎn)1為根的樹，樹高為1。由于樹的連通性且沒有環(huán)，任何一個(gè)節(jié)點(diǎn)都可以作為樹根，從而形成一棵樹。直觀的解決辦法是依次對(duì)每一個(gè)可能形成的樹使用DFS算法，然后計(jì)算樹中每個(gè)節(jié)點(diǎn)的高度，并將其中最大值作為樹的高度。但是這種算法的時(shí)間復(fù)雜度太高了，是O(n2)。通過觀察樹的結(jié)構(gòu)，我們發(fā)現(xiàn)如果將度為1的節(jié)點(diǎn)作為葉子節(jié)點(diǎn)的話，那么這棵樹的高度會(huì)最小。因此，我們可以使用類似剝洋蔥的方法，一層一層的刪掉葉子節(jié)點(diǎn)，最后剩下一個(gè)或兩個(gè)節(jié)點(diǎn)就是我們要找的最小高度的根節(jié)點(diǎn)。4.3.3DFS與BFS的應(yīng)用舉例1：最小高度樹

算法設(shè)計(jì)如下：1、如果n==1，則直接返回[0]，這是因?yàn)楫?dāng)樹只包含一個(gè)節(jié)點(diǎn)時(shí)，樹的高度為0，節(jié)點(diǎn)0就是這個(gè)樹的根。2、如果n==2，則返回[0,1]，這是因?yàn)楫?dāng)樹包含兩個(gè)節(jié)點(diǎn)時(shí)，樹的高度為1，節(jié)點(diǎn)0和節(jié)點(diǎn)1都可以是最小高度樹的根。3、創(chuàng)建一個(gè)空隊(duì)列queue；4、遍歷edges[][]數(shù)組，計(jì)算每個(gè)節(jié)點(diǎn)連接到其他節(jié)點(diǎn)的邊數(shù)，并將所有度為1的節(jié)點(diǎn)加入隊(duì)列queue中。5、將隊(duì)列queue中的節(jié)點(diǎn)依次刪除，同時(shí)圖中將其他連接到該節(jié)點(diǎn)的節(jié)點(diǎn)的度減1。6、當(dāng)減1后的節(jié)點(diǎn)的度也變成1，就作為新的要?jiǎng)h除的節(jié)點(diǎn)加入隊(duì)列；7、循環(huán)執(zhí)行步驟3和步驟4，直到圖中所有的節(jié)點(diǎn)要么被刪除了，要么已在隊(duì)列中，此時(shí)隊(duì)列中還未被刪除的節(jié)點(diǎn)就是最小高度樹的根節(jié)點(diǎn)。4.3.3DFS與BFS的應(yīng)用舉例1：最小高度樹

時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述：現(xiàn)在有一個(gè)容量為S毫升的瓶子，里面正好裝滿了水，還有兩個(gè)空杯子A和B，它們的容量分別是N毫升和M毫升，且S==N+M?，F(xiàn)在想將瓶子里的水平均分成兩份，但可惜的是無論是瓶子還是杯子都沒有刻度，聰明的你能否利用它們?nèi)齻€(gè)之間相互倒水的方式將水平分呢？如果能請(qǐng)輸出最少的倒水次數(shù)，如果不能輸出No。輸入說明輸入一行包括三個(gè)以空格分隔的整數(shù)S,N,M，分別代表水的體積和兩個(gè)杯子的容量。其中，0<s<101,N>0,M>0輸出說明如果能平分的話請(qǐng)輸出最少要倒的次數(shù)，否則輸出No。輸入樣例1743輸出樣例1No輸入樣例2413輸出樣例23。4.3.4DFS與BFS的應(yīng)用舉例2：水壺問題

4.3.4DFS與BFS的應(yīng)用舉例2：水壺問題

算法分析：我們可以用