何為廣度優(yōu)先遍歷呢？

廣度優(yōu)先遍歷（BFS），又叫寬度優(yōu)先搜索或橫向優(yōu)先搜索，是從根結點開始沿著樹的寬度搜索遍歷，將離根節(jié)點最近的節(jié)點先遍歷出來，在繼續(xù)深挖下去。

基本思想是：

1、從圖中某個頂點V0出發(fā)，并訪問此頂點； 2、從V0出發(fā)，訪問V0的各個未曾訪問的鄰接點W1，W2，…,Wk;然后,依次從W1,W2,…,Wk出發(fā)訪問各自未被訪問的鄰接點； 3、重復步驟2，直到全部頂點都被訪問為止。

下面給出廣度優(yōu)先遍歷的例子：（廣度優(yōu)先遍歷不是唯一的哦，只要滿足“廣度”的含義即可）

訪問順序為：0，2，1，5，3，4（看圖很快就可得知）（將離根節(jié)點最近的節(jié)點先遍歷出來，再繼續(xù)深挖下去。）

知道了BFS之后，我們又要怎么通過編程來實現(xiàn)BFS呢？

下面給上詳細的分析：

首先，先準備一個隊列（利用隊列的結構）和一個Set（Set用來作為類似于注冊的作用，防止節(jié)點重復進入隊列）

step1.先把根節(jié)點1放入隊列中，同時將1注冊到set中去，證實它進過隊列（上面兩步是同步的）

step2.把1poll出來，同時打印出來（System.out...）（前面兩步也是同步的），同時將1的所有next節(jié)點都放到隊列中去（放到隊列中去時要提前判斷這些元素之前是否有注冊過，即有沒有在set中）

step3.如果一個節(jié)點已經(jīng)沒有next節(jié)點的時候，那就直接將該節(jié)點彈出去就行，不用注冊也不用添加到隊列中。

下面流程圖可以用來參考，下面也有源代碼，源代碼有注釋，很好理解，看不清楚的歡迎留言~

下面附上源代碼：

總結

以上是生活随笔為你收集整理的图之遍历--广度优先遍历的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。