當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

算法之图搜索算法(一)

發布時間：2025/3/21 编程问答 16 豆豆

生活随笔收集整理的這篇文章主要介紹了算法之图搜索算法(一) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

1. 介紹

本文介紹了比較初級的圖搜索算法，包括深度優先遍歷，廣度優先遍歷和雙向廣度優先遍歷。

2. 深度優先遍歷DFS

2.1 算法思想

從圖中某個頂點v開始，訪問此節點，然后依次從v中未被訪問的鄰接點出發深度優先遍歷圖，直到圖中上所有和v有路徑相通的頂點都被訪問；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問頂點做起點，重復以上過程，直到圖中所有頂點都被訪問為止。

深度優先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態是所有頂點均未被訪問過，在G中任選一個頂點i作為遍歷的初始點，則深度優先搜索遍歷可定義如下：

(1) 首先訪問頂點i，并將其訪問標記置為訪問過，即visited[i]=1；

(2) 然后搜索與頂點i有邊相連的下一個頂點j，若j未被訪問過，則訪問它，并將j的訪問標記置為訪問過，visited[j]=1，然后從j開始重復此過程，若j已訪問，再看與i有邊相連的其它頂點；

(3) 若與i有邊相連的頂點都被訪問過，則退回到前一個訪問頂點并重復剛才過程，直到圖中所有頂點都被訪問完止。

2.2 算法實現

鄰接矩陣的算法描述為下面形式：

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

   void  dfs1 (graph & g, int  i, int  n)???????? // 從頂點i 出發遍歷   {   ??cout<<g.v[i];??????????????? //輸出訪問頂點   ??visited[i]=1;??????????????????? //訪問標記置1表示已經訪問   ??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<<‘’ ;????????????? //輸出訪問頂點   ??visted[i]=1;??????????? //訪問標記置為1表示已訪問   ??edgenode * p=GL[i];   ??while  (p!=NULL)   ??{   ?????if?  (!visited[p->adjvex])   ???????dfs2(p->adjvex);   ?????p=p->next;  ??}   ?}  

2.3 適用范圍

需要有順序遍歷圖，且找到一個解后輸出即可。如：trie樹排序

多用于只要求解，并且解答樹中的重復節點較多并且重復較難判斷時使用，但往往可以用A*或回溯算法代替。

2.4 舉例

數獨求解。給出一個不完整的數獨，讓填充其中空白的數字。

更多題目：

POJ 1321 棋盤問題：http://www.cublog.cn/u3/105033/showart_2212140.html

類迷宮問題：http://www.jguoer.com/post/2010/02/17/DFS-Code.aspx

數獨問題：http://acm.hdu.edu.cn/showproblem.php?pid=1426

3. 廣度優先遍歷BFS

3.1 算法思想

廣度優先搜索遍歷類似于樹的按層次遍歷。設圖G的初態是所有頂點均未訪問，在G 任選一頂點i作為初始點，則廣度優先搜索的基本思想是：

(1)首先訪問頂點i，并將其訪問標志置為已被訪問，即visited[i]=1；

(2)接著依次訪問與頂點i有邊相連的所有頂點W1，W2，…，Wt；

(3)然后再按順序訪問與W1，W2，…，Wt有邊相連又未曾訪問過的頂點；

依此類推，直到圖中所有頂點都被訪問完為止。

3.2 算法實現

用鄰接矩陣的算法描述如下：

 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)?????? //從頂點i出發遍歷   {   ??Queue? Q ;???????? //Q為隊列   ??InitQueue(Q)   ??cout<<g.v[i] ;??????? // 輸出訪問頂點   ??visited[i]=1 ;???????? //標記置1表示已經訪問   ??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)??????????????????????????????? //進隊   ??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 適用范圍

求問題的最優解

3.4 舉例

給定一個8*8的格子地圖，再給定初始狀態和終止狀態，輸出從初始點到達終止點的最少步數。

更多題目：

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. 雙向廣度優先遍歷

4.1 算法思想

有些問題按照廣度優先搜索法則擴展結點的規則，既適合順序，也適合逆序，于是我們考慮在尋找目標結點或路徑的搜索過程中，初始結點向目標結點和目標結點向初始結點同時進行擴展，直至在兩個擴展方向上出現同一個子結點，搜索結束，這就是雙向搜索過程。

出現的這個同一子結點，我們稱為相交點，如果確實存在一條從初始結點到目標結點的最佳路徑，那么按雙向搜索進行搜索必然會在某層出現“相交”，即有相交點，初始結點一相交點一目標結點所形成的一條路徑即是所求路徑。

4.2 算法實現

 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表示節點的層數   ????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 適用范圍

最優化問題中，知道問題的起始狀態和最終狀態，且兩個狀態可相互到達。

4.4 舉例

棋盤上有四個棋子，給你兩個狀態，問可否8步內將一個狀態轉移到另一個狀態？

5. DFS與BFS比較

數據結構：DFS采用棧，而BFS采用隊列

算法思想：深度搜索與廣度搜索的控制結構和產生系統很相似，唯一的區別在于對擴展節點選取上。由于其保留了所有的前繼節點，所以在產生后繼節點時可以去掉一部分重復的節點，從而提高了搜索效率。這兩種算法每次都擴展一個節點的所有子節點，而不同的是，深度搜索下一次擴展的是本次擴展出來的子節點中的一個，而廣度搜索擴展的則是本次擴展的節點的兄弟節點

使用范圍：DFS可以迅速的找到一個解，然后利用這個解進行剪枝，而BFS可找到最優解。

原創文章，轉載請注明：?轉載自董的博客

本文鏈接地址:?http://dongxicheng.org/structure/basic-graph-search/

總結

以上是生活随笔為你收集整理的算法之图搜索算法(一)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

算法