定義

廣度優先搜索算法（Breadth-First-Search），是一種圖形搜索算法。

簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。

如果所有節點均被訪問，則算法中止。

BFS同樣屬于盲目搜索。

一般用隊列數據結構來輔助實現BFS算法。

如下圖，其廣度優先算法的遍歷順序為：1->2->3->4->5->6->7->8

算法步驟

首先將根節點放入隊列中。

從隊列中取出第一個節點，并檢驗它是否為目標。如果找到目標，則結束搜尋并回傳結果。否則將它所有尚未檢驗過的直接子節點加入隊列中。

若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋并回傳“找不到目標”。

重復步驟2。

算法模板

# Python

def BFS(root):

visited = set()

queue = []

queue.append([root])

while queue:

node = queue.pop()

visited.add(node)

process(node)

nodes = generate_related_nodes(node)

queue.push(nodes)

# other processing work

// Golang

type TreeNode struct {

Val int

Left *TreeNode

Right *TreeNode

}

func BFS(root *TreeNode){

visited := make(map[*TreeNode]bool)

queue := make([]*TreeNode,0)

queue = append(queue, root)

for len(queue)>0{

node := queue[0]

queue = queue[1:]

visited[node] = true

process(node)

nodes := generate_related_nodes(node)

queue = append(queue, nodes...)

}

// other processing work

}

要點

使用隊列 queue

記錄已訪問節點 visited ，通常使用哈希表

一般要抽象成樹、圖等模型

適用場景

樹

圖

二維數組

實戰題目

參考資料