1. 介紹
本文介紹了比較初級的圖搜索算法，包括深度優(yōu)先遍歷，廣度優(yōu)先遍歷和雙向廣度優(yōu)先遍歷。
2. 深度優(yōu)先遍歷DFS
2.1 算法思想
從圖中某個(gè)頂點(diǎn)v開(kāi)始，訪(fǎng)問(wèn)此節點(diǎn)，然后依次從v中未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直到圖中上所有和v有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)；若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未被訪(fǎng)問(wèn)頂點(diǎn)做起點(diǎn)，重復以上過(guò)程，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)為止。
深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的先序遍歷。假定給定圖G的初態(tài)是所有頂點(diǎn)均未被訪(fǎng)問(wèn)過(guò)，在G中任選一個(gè)頂點(diǎn)i作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遍歷可定義如下：
(1) 首先訪(fǎng)問(wèn)頂點(diǎn)i，并將其訪(fǎng)問(wèn)標記置為訪(fǎng)問(wèn)過(guò)，即visited[i]=1；
(2) 然后搜索與頂點(diǎn)i有邊相連的下一個(gè)頂點(diǎn)j，若j未被訪(fǎng)問(wèn)過(guò)，則訪(fǎng)問(wèn)它，并將j的訪(fǎng)問(wèn)標記置為訪(fǎng)問(wèn)過(guò)，visited[j]=1，然后從j開(kāi)始重復此過(guò)程，若j已訪(fǎng)問(wèn)，再看與i有邊相連的其它頂點(diǎn)；
(3) 若與i有邊相連的頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)，則退回到前一個(gè)訪(fǎng)問(wèn)頂點(diǎn)并重復剛才過(guò)程，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)完止。
2.2 算法實(shí)現
鄰接矩陣的算法描述為下面形式：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | void dfs1 (graph & g, int i, int n) // 從頂點(diǎn)i 出發(fā)遍歷{ cout<<g.v[i]; //輸出訪(fǎng)問(wèn)頂點(diǎn) visited[i]=1; //訪(fǎng)問(wèn)標記置1表示已經(jīng)訪(fǎng)問(wèn) for(j=1; j<=n; j++) if ((g.arcs[i ][j]= =1)&&(!visited[j])) dfs(g,j,n);} |
鄰接表算法描述為下面形式：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | void dfs2(adjlist GL,int i, int n){ cout<<i<<‘’ ; //輸出訪(fǎng)問(wèn)頂點(diǎn) visted[i]=1; //訪(fǎng)問(wèn)標記置為1表示已訪(fǎng)問(wèn) edgenode * p=GL[i]; while (p!=NULL) { if (!visited[p->adjvex]) dfs2(p->adjvex); p=p->next; } } |
2.3 適用范圍
需要有順序遍歷圖，且找到一個(gè)解后輸出即可。如：trie樹(shù)排序
多用于只要求解，并且解答樹(shù)中的重復節點(diǎn)較多并且重復較難判斷時(shí)使用，但往往可以用A*或回溯算法代替。
2.4 舉例
數獨求解。給出一個(gè)不完整的數獨，讓填充其中空白的數字。
更多題目：
POJ 1321 棋盤(pán)問(wèn)題：http://www.cublog.cn/u3/105033/showart_2212140.html
類(lèi)迷宮問(wèn)題：http://www.jguoer.com/post/2010/02/17/DFS-Code.aspx
數獨問(wèn)題：http://acm.hdu.edu.cn/showproblem.php?pid=1426
3. 廣度優(yōu)先遍歷BFS
3.1 算法思想
廣度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的按層次遍歷。設圖G的初態(tài)是所有頂點(diǎn)均未訪(fǎng)問(wèn)，在G 任選一頂點(diǎn)i作為初始點(diǎn)，則廣度優(yōu)先搜索的基本思想是：
(1)首先訪(fǎng)問(wèn)頂點(diǎn)i，并將其訪(fǎng)問(wèn)標志置為已被訪(fǎng)問(wèn)，即visited[i]=1；
(2)接著(zhù)依次訪(fǎng)問(wèn)與頂點(diǎn)i有邊相連的所有頂點(diǎn)W1，W2，…，Wt；
(3)然后再按順序訪(fǎng)問(wèn)與W1，W2，…，Wt有邊相連又未曾訪(fǎng)問(wèn)過(guò)的頂點(diǎn)；
依此類(lèi)推，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)完為止。
3.2 算法實(shí)現
用鄰接矩陣的算法描述如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | void bfs1( graph g, int i) //從頂點(diǎn)i出發(fā)遍歷{ Queue Q ; //Q為隊列 InitQueue(Q) cout<<g.v[i] ; // 輸出訪(fǎng)問(wèn)頂點(diǎn) visited[i]=1 ; //標記置1表示已經(jīng)訪(fǎng)問(wèn) Qinsert(Q,i) ; //入隊列 while (!Queueempty(Q)) { int k=Qdelete(Q); for (j=0; j<n; j++) { if ((g.a[i][j]==1)&&(!visited[j])) { cout<<g.v[j]; visited[j]=1 ; Qinsert(Q,i) ; } } }} |
用鄰接矩陣的算法描述如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | void bfs2(adjlist GL, int i, int n){ Queue Q ; InitQueue(Q); //定義隊列 cout<<i<<‘’; visited[i]=1; Qinsert(Q,i) //進(jìn)隊 while (!QueueEmpty(Q)) { int k=Qdelete(Q) ; //出隊 edgenode* p=GL[k]; while (p!=NULL) { if (!visited[p->adjvex]) { cout<<j; visited[p->data]=1; Qinsert(Q); } p=p->next; } }} |
3.3 適用范圍
求問(wèn)題的最優(yōu)解
3.4 舉例
給定一個(gè)8*8的格子地圖，再給定初始狀態(tài)和終止狀態(tài)，輸出從初始點(diǎn)到達終止點(diǎn)的最少步數。
更多題目：
http://www.cppblog.com/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
http://www.chenyajun.com/2010/05/08/4540
4. 雙向廣度優(yōu)先遍歷
4.1 算法思想
有些問(wèn)題按照廣度優(yōu)先搜索法則擴展結點(diǎn)的規則，既適合順序，也適合逆序，于是我們考慮在尋找目標結點(diǎn)或路徑的搜索過(guò)程中，初始結點(diǎn)向目標結點(diǎn)和目標結點(diǎn)向初始結點(diǎn)同時(shí)進(jìn)行擴展，直至在兩個(gè)擴展方向上出現同一個(gè)子結點(diǎn)，搜索結束，這就是雙向搜索過(guò)程。
出現的這個(gè)同一子結點(diǎn)，我們稱(chēng)為相交點(diǎn)，如果確實(shí)存在一條從初始結點(diǎn)到目標結點(diǎn)的最佳路徑，那么按雙向搜索進(jìn)行搜索必然會(huì )在某層出現“相交”，即有相交點(diǎn)，初始結點(diǎn)一相交點(diǎn)一目標結點(diǎn)所形成的一條路徑即是所求路徑。
4.2 算法實(shí)現
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | now = 0;Q.push(st); RQ.push(ed);mark[st] = true; Rmark[ed] = true;while(!Q.empty() && !RQ.empty()){ // 兩邊的擴展方式須為按層擴展 while(Q.front().step == now) { //step表示節點(diǎn)的層數 nextState = extend(Q.front); t if(mark[nextState]) continuel if(Rmark[nextState]) return true; } while(RQ.front().step == now) { nextState = extend(RQ.front); if(Rmark[nextState]) continuel if(mark[nextState]) return true; } now++;} |
4.3 適用范圍
最優(yōu)化問(wèn)題中，知道問(wèn)題的起始狀態(tài)和最終狀態(tài)，且兩個(gè)狀態(tài)可相互到達。
4.4 舉例
棋盤(pán)上有四個(gè)棋子，給你兩個(gè)狀態(tài)，問(wèn)可否8步內將一個(gè)狀態(tài)轉移到另一個(gè)狀態(tài)？
5. DFS與BFS比較
數據結構：DFS采用棧，而B(niǎo)FS采用隊列
算法思想：深度搜索與廣度搜索的控制結構和產(chǎn)生系統很相似，唯一的區別在于對擴展節點(diǎn)選取上。由于其保留了所有的前繼節點(diǎn)，所以在產(chǎn)生后繼節點(diǎn)時(shí)可以去掉一部分重復的節點(diǎn)，從而提高了搜索效率。這兩種算法每次都擴展一個(gè)節點(diǎn)的所有子節點(diǎn)，而不同的是，深度搜索下一次擴展的是本次擴展出來(lái)的子節點(diǎn)中的一個(gè)，而廣度搜索擴展的則是本次擴展的節點(diǎn)的兄弟節點(diǎn)
使用范圍：DFS可以迅速的找到一個(gè)解，然后利用這個(gè)解進(jìn)行剪枝，而B(niǎo)FS可找到最優(yōu)解。
原創(chuàng )文章，轉載請注明： 轉載自董的博客
本文鏈接地址: http://dongxicheng.org/structure/basic-graph-search/
聯(lián)系客服
