BFS 问题的本质通常是让你在一副“图”中找到从起点 start 到终点 target 的最短距离。BFS的思想不多说，直接上模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int BFS(Node start, Node target){
    //初始化队列
    Queue<Node> q;
    //集合用于去重
    Set<Node> visited;

    //将起点加入队列
    q.offer(start);
    //记录访问节点
    visited.add(start);
    //记录扩散的步数
    int step = 0;

    while(q not empty){
        //当前层次的队列长度
        int sz = q.size();
        //遍历该层
        for(int i = 0;i< sz;i++>){
            Node cur = q.poll();
            //是目标节点嘛
            if(cur is target){
                return step;
            }
            //将该层没有被访问过的节点加入队列
            for(Node x : cur.adj()){
                if(x in visited) continue;
                q.offer(x);
                visited.add(x);
            }
        }
        step++;
    }
}

注：
1.cur.adj() 泛指节点的相邻节点
2.visited 的作用是不走回头路，只访问没有访问过的节点，一般情况下都是必要的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路，就不需要visited
3.这里需要入队时就记录visited，如果出队时再记录就有可能重复入队，比如有两个节点同时可以到达下一个节点，那么该节点就会重复入队。还有一个解决方案可以在出队时记录，就是出队时再查看该节点是否被访问过，访问过就continue，但是这种方法并不可取，这样会导致队列中的冗余，造成更大的空间复杂度。虽说visited的作用时访问没有访问过的节点，但是入队时记录，同样是使所有节点依次访问，即只要进队列了就算访问了，因为迟早是要访问的。