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

廢話不多說(shuō)，直接敲代碼（對(duì)于不懂的算法，直接敲代碼，背起來(lái)，就不信會(huì)不懂）

1. C 語(yǔ)言實(shí)現(xiàn)

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

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

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

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

定義一個(gè)結(jié)構(gòu)體來(lái)表達(dá)一個(gè)節(jié)點(diǎn)的結(jié)構(gòu)：

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

那么，我們?cè)谒阉饕粋€(gè)樹(shù)的時(shí)候，從一個(gè)節(jié)點(diǎn)開(kāi)始，能首先獲取的是它的兩個(gè)子節(jié)點(diǎn)。例如：

   A
B     C

A是第一個(gè)訪問(wèn)的，然后順序是B和C；然后再是B的子節(jié)點(diǎn)，C的子節(jié)點(diǎn)。那么我們?cè)趺磥?lái)保證這個(gè)順序呢？

這里就應(yīng)該用queue數(shù)據(jù)結(jié)構(gòu)，因?yàn)閝ueue采用先進(jìn)先出( first-in-first-out )的順序。

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

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

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

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