BreadthFirstSearch 广度优先搜索

问题

用广度优先搜索从图 $G = <V,E>$ 的顶点 $v_0$ 开始遍历所有顶点。

广度优先搜索需要设置一个队列 $queue$ ，然后进行以下操作：

$(1)$ 初始时将 $v_0$ 加入队列 $queue$ 中作为等待访问的顶点，并染红；

$(2)$ 重复从队列 $queue$ 中取出头节点 $v_i$ 访问，将 $v_i$ 的所有邻节点都加入队列 $queue$ 中作为下次等待访问的顶点，并染红；

重复第 $(2)$ 步操作直到 $queue$ 为空，算法结束。下图演示搜索过程：

Last updated 5 years ago

用广度优先搜索从图 $G = <V,E>$ 的顶点 $v_0$ 开始遍历所有顶点。

广度优先搜索需要设置一个队列 $queue$ ，然后进行以下操作：

$(1)$ 初始时将 $v_0$ 加入队列 $queue$ 中作为等待访问的顶点，并染红；

$(2)$ 重复从队列 $queue$ 中取出头节点 $v_i$ 访问，将 $v_i$ 的所有邻节点都加入队列 $queue$ 中作为下次等待访问的顶点，并染红；

重复第 $(2)$ 步操作直到 $queue$ 为空，算法结束。下图演示搜索过程：

顶点访问的顺序为 $[0, 4, 5, 3, 1, 2]$ 。广度优先搜索时间复杂度为 $O(\| V \|)$ 。

顶点访问的顺序为 $[0, 4, 5, 3, 1, 2]$ 。广度优先搜索时间复杂度为 $O(\| V \|)$ 。