我的书签
添加书签
移除书签Breadth First Search(BFS) - 广度优先搜索
问题
用广度优先搜索从图 G 的节点 beg 开始，遍历图 G 中的所有节点。
解法
在图 G 中，假设节点 i 的邻节点集合为 V_i ，对于图中的任意节点 i ，在访问节点 i 之后，总是优先访问该节点的邻节点集合 V_i 中的所有节点，然后才继续访问其他节点。
广度优先遍历需要一个队列 queue 来存储那些等待访问而尚未被访问的节点，在遍历过程中，为了避免重复的访问一个节点，当某个节点 i 加入 queue 时我们将其染成红色。下面演示从无向图 G 中的节点 0 开始进行广度优先搜索过程：
(1) 初始时从节点 0 开始，将它染红并加入 queue 中；
(2) 从 queue 中取出头节点 0 进行访问，然后考虑其未被染色的邻节点 {1, 4, 5} ，将 { 1, 4, 5 } 节点染红并加入 queue 中；
(3) 从 queue 中取出头节点 1 进行访问，然后考虑其未被染色的邻节点 {2, 3} ，将 { 2, 3 } 节点染红并加入 queue 中；
(4) 从 queue 中取出头节点 4 进行访问，它没有未被染色的邻节点；
(5) 从 queue 中取出头节点 5 进行访问，它没有未被染色的邻节点；
(6) 从 queue 中取出头节点 2 进行访问，它没有未被染色的邻节点；
(7) 从 queue 中取出头节点 3 进行访问，它没有未被染色的邻节点；
(8) 队列 queue 为空，算法结束；
广度优先搜索的时间复杂度是 O(n) 。
