Breadth First Search(BFS) - 广度优先搜索

问题

用广度优先搜索从图$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 \|)$。

Introduction To Algorithms

• VI.Graph Algorithms - 22.Elementary Graph Algorithms - 22.2.Breadth-first search

源码

BreadthFirstSearch.h

BreadthFirstSearch.cpp

测试

BreadthFirstSearchTest.cpp