广度优先搜索（BFS）解题总结
广度优先搜索算法（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)
# other processing workprocess(node) nodes = generate_related_nodes(node) queue.push(nodes)// 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
} // other processing workprocess(node) nodes := generate_related_nodes(node) queue = append(queue, nodes...)}
使用队列 queue
记录已访问节点 visited ，通常使用哈希表
一般要抽象成树、图等模型
树
图
二维数组
手机扫一扫
移动阅读更方便
你可能感兴趣的文章