|
作者:Dong | 可以轉(zhuǎn)載, 但必須以超鏈接形式標(biāo)明文章原始出處和作者信息及版權(quán)聲明
網(wǎng)址:http:///structure/basic-graph-search/ 1. 介紹 本文介紹了比較初級的圖搜索算法，包括深度優(yōu)先遍歷，廣度優(yōu)先遍歷和雙向廣度優(yōu)先遍歷。 2. 深度優(yōu)先遍歷DFS 2.1 算法思想 從圖中某個頂點(diǎn)v開始，訪問此節(jié)點(diǎn)，然后依次從v中未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中上所有和v有路徑相通的頂點(diǎn)都被訪問；若此時圖中尚有頂點(diǎn)未被訪問，則另選圖中一個未被訪問頂點(diǎn)做起點(diǎn)，重復(fù)以上過程，直到圖中所有頂點(diǎn)都被訪問為止。 深度優(yōu)先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點(diǎn)均未被訪問過，在G中任選一個頂點(diǎn)i作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遍歷可定義如下： (1) 首先訪問頂點(diǎn)i，并將其訪問標(biāo)記置為訪問過，即visited[i]=1； (2) 然后搜索與頂點(diǎn)i有邊相連的下一個頂點(diǎn)j，若j未被訪問過，則訪問它，并將j的訪問標(biāo)記置為訪問過，visited[j]=1，然后從j開始重復(fù)此過程，若j已訪問，再看與i有邊相連的其它頂點(diǎn)； (3) 若與i有邊相連的頂點(diǎn)都被訪問過，則退回到前一個訪問頂點(diǎn)并重復(fù)剛才過程，直到圖中所有頂點(diǎn)都被訪問完止。 2.2 算法實現(xiàn) 鄰接矩陣的算法描述為下面形式：
鄰接表算法描述為下面形式：
2.3 適用范圍 需要有順序遍歷圖，且找到一個解后輸出即可。如：trie樹排序 多用于只要求解，并且解答樹中的重復(fù)節(jié)點(diǎn)較多并且重復(fù)較難判斷時使用，但往往可以用A*或回溯算法代替。 2.4 舉例 數(shù)獨(dú)求解。給出一個不完整的數(shù)獨(dú)，讓填充其中空白的數(shù)字。 更多題目： POJ 1321 棋盤問題：http://www./u3/105033/showart_2212140.html 類迷宮問題：http://www./post/2010/02/17/DFS-Code.aspx 數(shù)獨(dú)問題：http://acm./showproblem.php?pid=1426 3. 廣度優(yōu)先遍歷BFS 3.1 算法思想 廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷。設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問，在G 任選一頂點(diǎn)i作為初始點(diǎn)，則廣度優(yōu)先搜索的基本思想是： (1)首先訪問頂點(diǎn)i，并將其訪問標(biāo)志置為已被訪問，即visited[i]=1； (2)接著依次訪問與頂點(diǎn)i有邊相連的所有頂點(diǎn)W1，W2，…，Wt； (3)然后再按順序訪問與W1，W2，…，Wt有邊相連又未曾訪問過的頂點(diǎn)； 依此類推，直到圖中所有頂點(diǎn)都被訪問完為止。 3.2 算法實現(xiàn) 用鄰接矩陣的算法描述如下：
用鄰接矩陣的算法描述如下：
3.3 適用范圍 求問題的最優(yōu)解 3.4 舉例 給定一個8*8的格子地圖，再給定初始狀態(tài)和終止?fàn)顟B(tài)，輸出從初始點(diǎn)到達(dá)終止點(diǎn)的最少步數(shù)。 更多題目： http://www./firstnode/archive/2009/03/07/75839.html http://blog.sina.com.cn/s/blog_6635898a0100hwe3.html http://blog.csdn.net/super_chris/archive/2009/12/26/5082666.aspx 4. 雙向廣度優(yōu)先遍歷 4.1 算法思想 有些問題按照廣度優(yōu)先搜索法則擴(kuò)展結(jié)點(diǎn)的規(guī)則，既適合順序，也適合逆序，于是我們考慮在尋找目標(biāo)結(jié)點(diǎn)或路徑的搜索過程中，初始結(jié)點(diǎn)向目標(biāo)結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)向初始結(jié)點(diǎn)同時進(jìn)行擴(kuò)展，直至在兩個擴(kuò)展方向上出現(xiàn)同一個子結(jié)點(diǎn)，搜索結(jié)束，這就是雙向搜索過程。 出現(xiàn)的這個同一子結(jié)點(diǎn)，我們稱為相交點(diǎn)，如果確實存在一條從初始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最佳路徑，那么按雙向搜索進(jìn)行搜索必然會在某層出現(xiàn)“相交”，即有相交點(diǎn)，初始結(jié)點(diǎn)一相交點(diǎn)一目標(biāo)結(jié)點(diǎn)所形成的一條路徑即是所求路徑。 4.2 算法實現(xiàn)
4.3 適用范圍 最優(yōu)化問題中，知道問題的起始狀態(tài)和最終狀態(tài)，且兩個狀態(tài)可相互到達(dá)。 4.4 舉例 棋盤上有四個棋子，給你兩個狀態(tài)，問可否8步內(nèi)將一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)？ 5. DFS與BFS比較 數(shù)據(jù)結(jié)構(gòu)：DFS采用棧，而BFS采用隊列 算法思想：深度搜索與廣度搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很相似，唯一的區(qū)別在于對擴(kuò)展節(jié)點(diǎn)選取上。由于其保留了所有的前繼節(jié)點(diǎn)，所以在產(chǎn)生后繼節(jié)點(diǎn)時可以去掉一部分重復(fù)的節(jié)點(diǎn)，從而提高了搜索效率。這兩種算法每次都擴(kuò)展一個節(jié)點(diǎn)的所有子節(jié)點(diǎn)，而不同的是，深度搜索下一次擴(kuò)展的是本次擴(kuò)展出來的子節(jié)點(diǎn)中的一個，而廣度搜索擴(kuò)展的則是本次擴(kuò)展的節(jié)點(diǎn)的兄弟節(jié)點(diǎn) 使用范圍：DFS可以迅速的找到一個解，然后利用這個解進(jìn)行剪枝，而BFS可找到最優(yōu)解。 原創(chuàng)文章，轉(zhuǎn)載請注明： 轉(zhuǎn)載自董的博客 |
|
|
