广度优先搜索BFS—Swift代码模板

Swift

//广度优先搜索
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)
            }
            //直接添加数组也可以下面这么写
//            queue.append(contentsOf: node.children)
        }
    }
}

总结：如果是要找所有可能结果中最短的，那么BFS会更高效。因为DFS是一种一种的尝试，在把所有可能情况尝试完之前，无法确定哪个是最短，所以DFS必须把所有情况都找一遍，才能确定最终答案（DFS的优化就是剪枝，不剪枝很容易超时）。而BFS从一开始就是尝试所有情况，所以只要找到第一个达到的那个点，那就是最短的路径，可以直接返回了，其他情况都可以省略了，所以这种情况下，BFS更高效。

BFS解法中的visited为什么可以全局使用？
BFS是在尝试所有的可能路径，哪个最快到达终点，哪个就是最短。那么每一条路径走过的路不同，visited（也就是这条路径上走过的点）也应该不同，那么为什么visited可以全局使用呢？
因为我们要找的是最短路径，那么如果在此之前某个点已经在visited中，也就是说有其他路径在小于或等于当前步数的情况下，到达过这个点，证明到达这个点的最短路径已经被找到。那么显然这个点没必要再尝试了，因为即便去尝试了，最终的结果也不会是最短路径了，所以直接放弃这个点即可。