算法之圖搜索算法(一) | 董的博客

andersr 2012-06-28

展開全文

作者:Dong | 可以轉(zhuǎn)載, 但必須以超鏈接形式標明文章原始出處和作者信息及版權(quán)聲明
網(wǎng)址:http:///structure/basic-graph-search/

1. 介紹

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

2. 深度優(yōu)先遍歷DFS

2.1 算法思想

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

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

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

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

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

2.2 算法實現(xiàn)

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

void dfs1 (graph & g, int i, int n)         // 從頂點i 出發(fā)遍歷
 
{
 
  cout<<g.v[i];                //輸出訪問頂點
 
  visited[i]=1;                    //訪問標記置1表示已經(jīng)訪問
 
  for(j=1; j<=n; j++)
 
    if ((g.arcs[i ][j]= =1)&&(!visited[j]))
 
      dfs(g,j,n);
 
}

鄰接表算法描述為下面形式：

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樹排序

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

2.4 舉例

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

更多題目：

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

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

數(shù)獨問題：http://acm./showproblem.php?pid=1426

3. 廣度優(yōu)先遍歷BFS

3.1 算法思想

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

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

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

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

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

3.2 算法實現(xiàn)

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

void  bfs1( graph g, int  i)       //從頂點i出發(fā)遍歷
 
{
 
  Queue  Q ;         //Q為隊列
 
  InitQueue(Q)
 
  cout<<g.v[i] ;        // 輸出訪問頂點
 
  visited[i]=1 ;         //標記置1表示已經(jīng)訪問
 
  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) ;
 
      }
 
    }
  }
 
}

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

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 適用范圍

求問題的最優(yōu)解

3.4 舉例

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

http://blog.sina.com.cn/s/blog_6635898a0100hwe3.html

http://blog.csdn.net/super_chris/archive/2009/12/26/5082666.aspx

http://www./2010/05/08/4540

4. 雙向廣度優(yōu)先遍歷

4.1 算法思想

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

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

4.2 算法實現(xiàn)

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表示節(jié)點的層數(shù)
 
    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)化問題中，知道問題的起始狀態(tài)和最終狀態(tài)，且兩個狀態(tài)可相互到達。

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ū)別在于對擴展節(jié)點選取上。由于其保留了所有的前繼節(jié)點，所以在產(chǎn)生后繼節(jié)點時可以去掉一部分重復(fù)的節(jié)點，從而提高了搜索效率。這兩種算法每次都擴展一個節(jié)點的所有子節(jié)點，而不同的是，深度搜索下一次擴展的是本次擴展出來的子節(jié)點中的一個，而廣度搜索擴展的則是本次擴展的節(jié)點的兄弟節(jié)點

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

原創(chuàng)文章，轉(zhuǎn)載請注明： 轉(zhuǎn)載自董的博客

本文鏈接地址: http:///structure/basic-graph-search/