BFS广度优先搜索（模板）

广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。

结点的处理顺序是什么？ 与树的层序遍历类似，越是接近根结点的结点将越早地遍历。 如果在第 k 轮中将结点 X 添加到队列中，则根结点与 X 之间的最短路径的长度恰好是 k。也就是说，第一次找到目标结点时，处于最短路径中。队列的入队和出队顺序是什么？ 首先将根结点排入队列。然后在每一轮中，我们逐个处理已经在队列中的结点，并将所有邻居添加到队列中。值得注意的是，新添加的节点不会立即遍历，而是在下一轮中处理。 结点的处理顺序与它们添加到队列的顺序是完全相同的顺序，即先进先出（FIFO）。这就是在 BFS 中使用队列的原因。

Python模板：

def BFS(Node root, Node target): """Return the length of the shortest path between root and target node.""" queue = [] step = 0 # initialize queue.append(root) # BFS while queue: step += 1 # iterate the nodes which are already in the queue size = len(queue) for i in range(size): Node cur = queue[0] return step if cur == target for next in Node.neighbors: queue.append(next) queue.pop(0) return -1 # there is no path from root to target

Java模板：

/** * Return the length of the shortest path between root and target node. */ int BFS(Node root, Node target) { Queue<Node> queue; // store all nodes which are waiting to be processed int step = 0; // number of steps neeeded from root to current node // initialize add root to queue; // BFS while (queue is not empty) { step = step + 1; // iterate the nodes which are already in the queue int size = queue.size(); for (int i = 0; i < size; ++i) { Node cur = the first node in queue; return step if cur is target; for (Node next : the neighbors of cur) { add next to queue; } remove the first node from queue; } } return -1; // there is no path from root to target }

有时，确保永远不会访问一个结点两次很重要。否则，可能陷入无限循环。如果是这样，可以在上面的代码中添加一个哈希集来解决这个问题。 有两种情况不需要使用哈希集：

确定没有循环，例如，在树遍历中；确实希望多次将结点添加到队列中。

Python模板：

def BFS(Node root, Node target): """Return the length of the shortest path between root and target node.""" queue = [] uesd = set() # used = {}是创建字典，创建集合用set() step = 0 # initialize queue.append(root) used.add(root) # BFS while queue: step += 1 # iterate the nodes which are already in the queue size = len(queue) for i in range(size): Node cur = queue[0] return step if cur == targer for next in Node.neighbors: if next not in used: queue.append(next) used.add(next) queue.pop(0) return -1 # there is no path from root to target

Java模板：

/** * Return the length of the shortest path between root and target node. */ int BFS(Node root, Node target) { Queue<Node> queue; // store all nodes which are waiting to be processed Set<Node> used; // store all the used nodes int step = 0; // number of steps neeeded from root to current node // initialize add root to queue; add root to used; // BFS while (queue is not empty) { step = step + 1; // iterate the nodes which are already in the queue int size = queue.size(); for (int i = 0; i < size; ++i) { Node cur = the first node in queue; return step if cur is target; for (Node next : the neighbors of cur) { if (next is not in used) { add next to queue; add next to used; } } remove the first node from queue; } } return -1; // there is no path from root to target }

Reference： 队列和广度优先搜索 Python3集合