Swift
//廣度優(yōu)先搜索
func bfs(_ root: Node?) {
guard let _root = root else { return }
var visited = [Int: Int]()
var queue = [Node]()
queue.append(_root)
while queue.count > 0 {
let size = queue.count
for _ in 0 ..< size {
let node = queue.removeFirst()
if let _visit = visited[node.val], _visit == 1 {
continue
}
visited[node.val] = 1
for child in node.children {
queue.append(child)
}
//直接添加數(shù)組也可以下面這么寫
// queue.append(contentsOf: node.children)
}
}
}
總結(jié)：如果是要找所有可能結(jié)果中最短的，那么BFS會(huì)更高效命雀。因?yàn)镈FS是一種一種的嘗試翔始，在把所有可能情況嘗試完之前，無法確定哪個(gè)是最短撑螺，所以DFS必須把所有情況都找一遍含思，才能確定最終答案（DFS的優(yōu)化就是剪枝，不剪枝很容易超時(shí)）。而BFS從一開始就是嘗試所有情況含潘，所以只要找到第一個(gè)達(dá)到的那個(gè)點(diǎn)饲做，那就是最短的路徑，可以直接返回了遏弱，其他情況都可以省略了盆均，所以這種情況下，BFS更高效漱逸。
BFS解法中的visited為什么可以全局使用泪姨？
BFS是在嘗試所有的可能路徑，哪個(gè)最快到達(dá)終點(diǎn)饰抒，哪個(gè)就是最短肮砾。那么每一條路徑走過的路不同，visited（也就是這條路徑上走過的點(diǎn)）也應(yīng)該不同袋坑，那么為什么visited可以全局使用呢唇敞？
因?yàn)槲覀円业氖亲疃搪窂剑敲慈绻诖酥澳硞€(gè)點(diǎn)已經(jīng)在visited中咒彤，也就是說有其他路徑在小于或等于當(dāng)前步數(shù)的情況下疆柔，到達(dá)過這個(gè)點(diǎn)，證明到達(dá)這個(gè)點(diǎn)的最短路徑已經(jīng)被找到镶柱。那么顯然這個(gè)點(diǎn)沒必要再嘗試了旷档，因?yàn)榧幢闳L試了，最終的結(jié)果也不會(huì)是最短路徑了歇拆，所以直接放棄這個(gè)點(diǎn)即可鞋屈。
