個人理解廣度優(yōu)先搜索

google 下維基，廣度優(yōu)先搜索，理解定義只要看哪個“廣”字就都能明白，在圖的遍歷中，從根節(jié)點開始，沿著樹的寬度遍歷樹的節(jié)點?？梢赃@樣通俗的理解，一個人去拜訪你家的時候是先拜訪長輩，按照級別一級一級的拜訪下來。

廢話不多說，直接敲代碼（對于不懂的算法，直接敲代碼，背起來，就不信會不懂）

1. C 語言實現(xiàn)

廣度優(yōu)先搜索算法：

void BFS(VLink G[], int v) 
{ int w;
  VISIT(v);                    /*訪問頂點v*/
  visited[v] = 1;              /*頂點v對應的訪問標記置為1*/
  ADDQ(Q,v);
  while(!EMPTYQ(Q))
  { v = DELQ(Q);               /*退出隊頭元素v*/
    w = FIRSTADJ(G,v);         /*求v的第1個鄰接點。無鄰接點則返回-1*/
    while(w != -1)
    { if(visited[w] == 0)
      { VISIT(w);              /*訪問頂點v*/
        ADDQ(Q,w);             /*當前被訪問的頂點w進隊*/
        visited[w] = 1;        /*頂點w對應的訪問標記置為1*/
      }
      w = NEXTADJ(G,v);        /*求v的下一個鄰接點。若無鄰接點則返回-1*/
    }
  }  
}

對圖G=(V,E)進行廣度優(yōu)先搜索的主算法如下。

void TRAVEL_BFS(VLink G[], int visited[], int n)
{ int i;
  for(i = 0; i < n; i ++)
  { visited[i] = 0;            /* 標記數(shù)組賦初值（清零）*/
  }
  for(i = 0; i < n; i ++)
    if(visited[i] == 0)
      BFS(G,i);
}

定義一個結構體來表達一個節(jié)點的結構：

 struct node
 {
    int self; //數(shù)據(jù)
    node *left; //左節(jié)點
    node *right; //右節(jié)點
 };

那么，我們在搜索一個樹的時候，從一個節(jié)點開始，能首先獲取的是它的兩個子節(jié)點。例如：

   A
B     C

A是第一個訪問的，然后順序是B和C；然后再是B的子節(jié)點，C的子節(jié)點。那么我們怎么來保證這個順序呢？

這里就應該用queue數(shù)據(jù)結構，因為queue采用先進先出( first-in-first-out )的順序。

使用C++的STL函式庫，下面的程序能幫助理解：

 std::queue visited, unvisited; 
 node nodes[9];
 node* current;
 
 unvisited.push(&nodes[0]); //先把root放入unvisited queue
 
 while(!unvisited.empty()) //只有unvisited不空
 {
    current = (unvisited.front()); //目前應該檢驗的
 
    if(current -> left != NULL)
       unvisited.push(current -> left); //把左邊放入queue中
 
    if(current -> right != NULL) //右邊壓入。因為QUEUE是一個先進先出的結構，所以即使后面再壓其他東西，依然會先訪問這個。
       unvisited.push(current -> right);
 
    visited.push(current);
 
    cout << current -> self << endl;
 
    unvisited.pop();
 }

個人認為想要理解好廣度優(yōu)先算法的話，直接看 C++ 實現(xiàn)的代碼，簡單易懂。

關于廣度優(yōu)先搜索算法還有很多種方式的代碼實現(xiàn)，比如堆棧實現(xiàn)，遞歸實現(xiàn)...但是把上面這兩種實現(xiàn)方法記住，剩下的其實是換湯不換藥。