本文讲解BFS算法的核心思想和代码基本框架。

1 BFS算法的核心思想

BFS的英文全称为(Breadth-first search),称为广度优先搜索算法。 该算法是用于在树形结构中按照某种规则搜索结点的算法。 该算法的核心思想是从起始点出发，依次遍历完起始点周围的结点，不断重复该过程直至扩散至所有结点。

2 BFS算法的代码框架

基于BFS的特点：代码实现时，采用队列来保存每一轮迭代的结果。

1. 首次将起始点或初始状态的结点插入队列。
2. 在出队列时，将和该结点关联的结点进队。
3. 操作结束的条件：队列为空。

温馨提示：
若需要区分每层遍历的结果，可以通过记录队列中元素的个数来实现。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

queue.push(root);
while (!queue.empty()) {
    int size = 0;
    for (int idx = 0; idx < size; ++i) {
        head = queue.front();
        xxx;// 执行和队列头部相关的操作
        queue.push(head->child);
        queue.pop();
    }
}