廣度優(yōu)先搜索在圖論中的應用

1、廣度優(yōu)先搜索在圖論中的應用摘要：本文詳細的分析了廣度優(yōu)先搜索算法，重點研究了該算法在圖論中的應用，尤其是在最短路徑問題中的應用。通過與其它最短路搜索算法的比較分析，本文得到了這些最短路算法之間的關系。關鍵詞：廣度優(yōu)先搜索，最短路徑，圖論。Abstract：this paper gives a detailed analysis of the breadth-first search algorithm, and emphasis on the algorithm in the application of graph theory, especially in the shortest pat

2、h problem in the application. Through the comparative analysis with the other shortest path search algorithm, this paper obtains these relationships between these shortest path algorithms.Keywords: breadth first search, shortest path, graph theory.目錄摘要0Abstract0一、引言2二、廣度優(yōu)先搜索算法2（一）基本思想2（二）算法結構3（三）算法特

3、性4（四）廣度優(yōu)先搜索算法在圖論中的應用5三、廣度優(yōu)先搜索算法在圖論中應用的具體分析5（一）尋找連接元件5（二）測試是否二分圖5（三）尋找非加權圖中任兩點的最短路徑5四、最短路中常用算法的比較7五、總結7參考文獻8附件8一、引言使用計算機求解的問題中，有許多問題是無法用數學公式進行計算推導和采用模擬方法來找出答案的。這樣的問題往往需要我們根據問題所給定的一些條件，在問題的所有可能解中用某種方式找出問題的解來，這就是所謂的搜索法或搜索技術。常見的搜索算法有廣度優(yōu)先搜索法（簡稱為BFS）、深度優(yōu)先搜索法、雙向廣度優(yōu)先搜索法，A*算法、回溯法、枚舉法、分支定界法等。圖論是數學的一個分支,以圖為研究對

4、象。這種圖由若干給定的點和連接兩點的線構成,借以描述某些事物之間的關系。用點代表事物,用連接兩點的線表示兩個事物之間具有特定關系。圖論起源于18世紀,追朔到1736年瑞士數學家L.Euler出版第一本圖論著作,提出和解決著名Konigsberg七橋問題。從那時以來,圖論不僅在許多領域,如計算機科學,運籌學,心理學等方面得到了廣泛的應用,而且學科本身也獲得長足發(fā)展,形成了擬陣理論,超圖理論,代數圖論,拓撲圖論等新分支。本文討論廣度優(yōu)先搜索在圖論中的應用。二、廣度優(yōu)先搜索算法（一）基本思想采用廣度優(yōu)先搜索算法解答問題時，需要構造一個表明狀態(tài)特征和不同狀態(tài)之間關系的數據結構，這種數據結構稱為結點。根

5、據問題所給定的條件，從一個結點出發(fā)，可以生成一個或多個新的結點，這個過程通常稱為擴展。結點之間的關系一般可以表示成一棵樹，它被稱為解答樹。搜索算法的搜索過程實際上就是根據初始條件和擴展規(guī)則構造一棵解答樹并尋找符合目標狀態(tài)的結點的過程。廣度優(yōu)先搜索算法中，解答樹上結點的擴展是沿結點深度的“斷層”進行，也就是說，結點的擴展是按它們接近起始結點的程度依次進行的。首先生成第一層結點，同時檢查目標結點是否在所生成的結點中，如果不在，則將所有的第一層結點逐一擴展，得到第二層結點，并檢查第二層結點是否包含目標結點，.對長度為n +1的任一結點進行擴展之前，必須先考慮長度為n的結點的每種可能的狀態(tài)。因此，對于

6、同一層結點來說，求解問題的價值是相同的，我們可以按任意順序來擴展它們。這里采用的原則是先生成的結點先擴展。廣度優(yōu)先搜索算法的搜索順序如下圖：A B C D E F GH I J K L M廣度優(yōu)先搜索順序如下：A-B-C-D-E-F-G-H-I-J-K-L-M廣度優(yōu)先搜索算法中，為了便于進行搜索，要設置一個表存儲所有的結點，為了滿足先生成的結點先擴展的原則，存儲結點的表一般設計成隊列的數據結構。搜索過程中不斷地從隊列頭取出結點進行擴展。對生成的新結點，要檢查它是否已在隊列中存在，還要檢查它是否目標結點。如果新結點是目標結點，則搜索成功，程序結束；若新結點不是目標結點，并且未曾在隊列中出現過，則

7、將它加入到隊列尾，否則將它丟棄，再從隊列頭取出結點進行擴展.。最終可能產生兩種結果：找到目標結點，或擴展完所有結點而沒有找到目標結點。如果目標結點存在于解答樹的有限層上，廣度優(yōu)先搜索算法一定能保證找到一條通向它的最佳路徑，因此廣度優(yōu)先搜索算法特別適用于只需求出最優(yōu)解的問題。當問題需要給出解的路徑，則要保存每個結點的來源，也就是它是從哪一個節(jié)點擴展來的。對于不同的問題，用廣度優(yōu)先搜索法的算法基本上都是一樣的。但表示問題狀態(tài)的結點數據結構、新結點是否目標結點和是否重復結點的判斷等方面則有所不同，對具體的問題需要進行具體分析。 （二）算法結構數據初始化；設隊列首指針CLOSED：=0；隊尾指針OPE

8、N：=1； 初始結點入隊； REPEAT CLOSED：=CLOSED+1； 取下一個CLOSED所指結點； FOR R：=1 TO MAXR DO 共有MAXR種操作方法,試第R種 BEGIN IF 子結點符合條件 THEN BEGIN OPEN：=OPEN+1；把新結點存入隊列； IF 新結點與原有結點重復 THEN OPEN：=OPEN-1刪去刻結點 ELSE IF 新結點是目標結點 THEN BEGIN 輸出結果并退出； END； END； END； UNTIL CLOSEDOPEN隊列空（三）算法特性1、空間復雜度因為所有節(jié)點都必須被儲存，因此廣度優(yōu)先搜索算法的空間復雜度為 O(|V

9、| + |E|)，其中 |V| 是節(jié)點的數目，而 |E| 是圖中邊的數目。注：另一種說法稱廣度優(yōu)先搜索算法的空間復雜度為 O(BM)，其中 B 是最大分支系數，而 M 是樹的最長路徑長度。由于對空間的大量需求，因此廣度優(yōu)先搜索算法并不適合解非常大的問題。2、時間復雜度最差情形下，廣度優(yōu)先搜索算法必須尋找所有到可能節(jié)點的所有路徑，因此其時間復雜度為 O(|V| + |E|)，其中 |V| 是節(jié)點的數目，而 |E| 是圖中邊的數目。3、完全性廣度優(yōu)先搜索算法具有完全性。這里指無論圖形的種類如何，只要目標存在，則廣度優(yōu)先搜索算法一定會找到。然而，若目標不存在，且圖為無限大，則廣度優(yōu)先搜索算法將不收斂

10、（不會結束）。4、最佳解若所有邊的長度相等，廣度優(yōu)先搜索算法是最佳解亦即它找到的第一個解，距離根節(jié)點的邊數目一定最少；但對一般的圖來說，廣度優(yōu)先搜索算法并不一定回傳最佳解。這是因為當圖形為加權圖（亦即各邊長度不同）時，廣度優(yōu)先搜索算法仍然回傳從根節(jié)點開始，經過邊數目最少的解；而這個解距離根節(jié)點的距離不一定最短。這個問題可以使用考慮各邊權值，廣度優(yōu)先搜索算法的改良算法成本一致搜尋法（en:uniform-cost search）來解決。然而，若非加權圖形，則所有邊的長度相等，廣度優(yōu)先搜索算法就能找到最近的最佳解。（四）廣度優(yōu)先搜索算法在圖論中的應用 尋找圖中所有連接元件（Connected Co

11、mponent）。一個連接元件是圖中的最大相連子圖。 尋找連接元件中的所有節(jié)點。 尋找非加權圖中任兩點的最短路徑。 測試一圖是否為二分圖。 (Reverse) CuthillMcKee算法。三、廣度優(yōu)先搜索算法在圖論中應用的具體分析（一）尋找連接元件由起點開始，執(zhí)行廣度優(yōu)先搜索算法后所經過的所有節(jié)點，即為包含起點的一個連接元件。（二）測試是否二分圖廣度優(yōu)先搜索算法可以用以測試二分圖。從任一節(jié)點開始搜尋，并在搜尋過程中給節(jié)點不同的標簽。例如，給開始點標簽 0，開始點的所有鄰居標簽 1，開始點所有鄰居的鄰居標簽二以此類推。若在搜尋過程中，任一節(jié)點有跟其相同標簽的鄰居，則此圖就不是二分圖。若搜尋結束

12、時這種情形未發(fā)生，則此圖為一二分圖。（三）尋找非加權圖中任兩點的最短路徑最短路問題是圖論中的核心問題之一，它是許多更深層算法的基礎。同時，該問題有著大量的生產實際的背景。不少問題從表面上看與最短路問題沒有什么關系，卻也可以歸結為最短路問題。最短路的定義：在最短路問題中，給出的是一有向加權圖G=(V,E)，在其上定義的加權函數W:ER為從邊到實型權值的映射。路徑P=(, , )的權是指其組成邊的所有權值之和：定義u到v間最短路徑的權為： 從結點u到結點v的最短路徑定義為權的任何路徑。廣度優(yōu)先搜索能夠在非加權圖G=(V,E)中快速地尋找從一個固定頂點s到其余頂點之間的最短距離。廣度優(yōu)先搜索是基于如

13、下的簡單想法：從s點開始，訪問每一個被s支配的頂點x。設和（頂點s是x的前驅）。訪問哪些與s距離不為1且受x所支配的頂點y，則有。繼續(xù)這種過程，直至達到所有能達到的頂點。這些頂點是從s點可達的。由于搜索過程是一級一級展開的，因此能快速的找到s點到其能到達的頂點的最短路徑。對于那些不能從s點可達的剩余頂點z，令。廣度優(yōu)先搜索較為正式的表述是算法的結尾處，意味著或者v從s是不可達的。（附件中有用matlab語言實現最短路徑搜索算法的程序）實作方法1、首先將根節(jié)點放入隊列中。2、從隊列中取出第一個節(jié)點，并檢驗它是否為目標。l 如果找到目標，則結束搜尋并回傳結果。l 否則將它所有尚未檢驗過的直接子節(jié)點

14、加入隊列中。3、若隊列為空，表示整張圖都檢查過了亦即圖中沒有欲搜尋的目標。結束搜尋并回傳“找不到目標”。4、重復步驟2。四、最短路中常用算法的比較其它最短路算法與廣度優(yōu)先搜索算法的比較列表算法時間復雜度空間復雜度編程復雜度適用范圍BFSO(E+V)O(E+V)簡單非加權圖（窄）DijkstraO()或O(E+V)logV)O()或O（E+V）簡單或相對復雜不含負權的圖（窄）FloydO（）O（）簡單實數圖（廣）Bellman-FordO（VE）O(E+V)簡單實數圖（廣）SPFAO(E)O(E+V)簡單實數圖（廣）通過比較分析分析，可知：l 對于非加權圖，可用簡便而又快捷的廣度優(yōu)先搜索算法找出

15、最短路徑。l Dijkstra算法的效率高，但是也有局限性，就是對于含負權的圖無能為力。l Floyd算法簡單、易于實現，且適用范圍廣，但時間和空間復雜度過高。l Bellman-Ford算法對于所有最短路長存在的圖都適用而且簡單，但是時間復雜度高，效率常常不盡人意。l SPFA算法可以說是綜合了上述算法的優(yōu)點。它的效率同樣很不錯，而且對于最短路中存在的所有圖都適用，無論是否存在負權。它的編程復雜度也很低，是高性價比的算法。五、總結廣度優(yōu)先搜索算法是一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結果。換句話說，它并不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止。廣度優(yōu)先

16、搜索算法并不使用經驗法則算法。對于非加權圖，廣度優(yōu)先搜索算法可以快速的找出最短路徑（假設存在最短路徑），但其在最短路問題中的適用范圍較窄。當最短路問題中出現賦權邊或負權時，可以根據情況選擇Dijkstra、Floyd、Bellman-Ford和SPFA等算法搜索最短路。對于尋找圖中所有連接元件，廣度優(yōu)先搜索是一種快速簡便的方法。另外，廣度優(yōu)先搜索算法還可以用于測試二分圖。因此廣度搜索算法在圖論中有廣泛的應用。對廣度優(yōu)先算法加以改進，可以得到特性更好的算法，如，雙向廣度優(yōu)先搜索算法和算法等。參考文獻1 卜月華 圖論及其應用 南京：東南大學出版社，2000。2 J.邦詹森 G.古廷 有向圖的理論、

17、算法及其應用 科學出版社 2009。3 /zh-cn/BFS#C_.E7.9A.84.E5.AF.A6.E4.BD.9C。4 殷劍宏 吳開亞.圖論及其算法M. 中國科學技術出版社。附件Matlab程序：function R,T=bfs(A,s,d)%A：鄰接矩陣(連通點間的距離為1，不連通的點間距離為inf,同點間距離為0）%s：源頂點，d：目標頂點%R：搜索過的節(jié)點%T：搜索過的邊%k=s;R(1)=s;Q(1)=s;T=;qq=;kk=0;while size(Q) %從Q中選一點% %選最先插入Q的點% p,q=find(A(k,:)=1) q

18、q=qq,q; for i=1:size(q) if sum(find(R=q(i) a=find(Q=q(i); Q(a)=; else Q=Q,q(i); R=R,q(i); T=T;k,q(i); end if i=d break; end end if i=d break; end k=qq(kk+1);endif sum(size(Q)=0 disp(找不到目標。);end有什么問題可以聯系我。姓名：劉明浩電話QQ：416588500As of Microsoft Internet Explorer 4.0, you can applmultimedia-s

19、tyle effects to your Web pages using visual filters and transitions. You can apply visual filters and transitions to standard HTML controls, such as text containers, images, and other windowless objects. Transitions are time-varying filters that create a transition from one visual state to another.

20、By combining filters and transitions with basic scripting, you can create visually engaging and interactive documents.Internet Explorer 5.5 and later supports a rich variety of optimized filters. Click the following button to see a demonstration of many of these filters and how to usetheProcedural s

21、urfaces are colored surfaces that display between the content of an object and the objects background. Procedural surfaces define each pixels RGB color and alpha values dynamically. Only the procedure used to compute the surface is stored in memory. The content of an object with a procedural surface applied is not affected by the procedural su