BFS广度优先搜索算法总结

发表于 | 分类于

BFS intro

广度优先搜索算法(Breadth First Search)，又称为”宽度优先搜索”或”横向优先搜索”，简称BFS。

它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2…的顶点。

Understand BFS

无向图(undirected graph)

第1步：访问A。

第2步：依次访问C,D,F。 

在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前面，因此，先访问C。再访问完C之后，再依次访问D,F。

第3步：依次访问B,G。 

在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。

第4步：访问E。 

在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。

因此访问顺序是：A -> C -> D -> F -> B -> G -> E

有向图(directed graph)

第1步：访问A。

第2步：访问B。

第3步：依次访问C,E,F。 

在访问了B之后，接下来访问B的出边的另一个顶点，即C,E,F。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，因此会先访问C，再依次访问E,F。

第4步：依次访问D,G。 

在访问完C,E,F之后，再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。

因此访问顺序是：A -> B -> C -> E -> F -> D -> G

BFS implement

对于没有边权重的图来说可以计算最短路径.

由于树的BFS只是图的BFS的一种特殊情况, 而且比较简单不需要visited标记, 这里只写一下图的BFS好了.

先定义一个Graph类, 这里在每一个节点保存邻居信息:

1
2
3
4
public class GraphNode{   
    int val;   
    List<GraphNode> neighbors;   
}

BFS for trees/graphs

图的遍历需要注意不走重复节点, 所以需要一个HashSet(名字叫visited)来保存哪些节点已经访问过了.

需要注意的是, 在把一个节点放进队列queue的时刻就要把它放进visited, 而不是在队列里取出来的时刻再放.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void BFS(GraphNode start){   
    LinkedList<GraphNode> q = new LinkedList<GraphNode>();   
    HasheSet<GraphNode> visited = new HasheSet<GraphNode>();   
    q.push(start);   
    visited.add(start);   
    while(!q.empty()){   
        GraphNode cur = q.poll();   
        System.out.println(cur.val);   
        for(GraphNode next: cur.children){    
            if(!visited.contains(next)){   
                q.push(next);   
                visited.add(next); // mark node as visited when adding to queue!    
            }   
        }   
    }//while   
}

BFS with distance

在BFS的同时我们可以记录从start节点到当前node的距离, 方法是把一个距离信息同时入队(封装一个Pair), 或者使用一个与queue平行的队列保存距离信息.

在上面的代码中, 加入:

1
2
3
4
5
6
7
8
9
//...   
LinkedList<Integer> distq = new LinkedList<Integer>();   
distq.push(0);// distance from start to start   
//...   
// in the while(!q.empty()) loop:    
    int d = distq.poll();//get distance from start to current node   
    for(GraphNode next: node.children){   
        distq.push(d+1);// distance from start to next node   
        //...

对于Tree的情况来说, 这里的dist其实就是当前节点的深度depth.

properties

性质1:
每个节点node的distance都是node距离起始点start的最短距离.

性质2:
距离start近的节点(depth浅的节点)一定比距离start远的节点早被访问到.

这是对一个树BFS的时候节点的访问顺序:

BFS “by layer”

参考上面的性质, 可以一次处理”一层”的节点, “一层”的意思是指所有节点距离start的距离相同. 代码在while循环里不是一次poll一个节点, 而是一次把queue的内容处理完, 然后换新的queue进入下一次while循环. 代码重新写一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void BFS(GraphNode start){   
    ArrayList<GraphNode> q = new ArrayList<Tree>();   
    HasheSet<GraphNode> visited = new HasheSet<GraphNode>();   
    q.push(start);   
    visited.add(start);   
    while(!q.empty()){   
        ArrayList<GraphNode> newq = new ArrayList<Tree>();// create a new queue   
        for(GraphNode cur: q){// deal with all nodes in the queue    
            System.out.print(cur.val+", ");// all nodes in q are of the same distance/depth   
            for(GraphNode next: cur.children)    
                if(!visited.contains(next))   
                    { newq.push(next);visited.add(next); }   
        }   
        System.out.println();   
        q = newq;//replace q with newq   
    }//while   
}

以上程序每次打印一行, 第i行包括了距start距离为i的所有节点.

由于这样的话每次不必在队首poll出元素(而是依次处理所有queue的元素), 所以可以改用ArrayList. 此时while循环里的不变量是: 所有q里面的节点距离start的距离都相同.

complexity

假设一个图有N个节点和M条边, BFS会走遍所有节点, 时间是O(N), 然后由于每个节点会检查所有的出边, 最终所有的边都会被检查过, 时间是O(M), 所以BFS的时间复杂度是O(N+M).

队列里面最多可能存放所有节点, 空间复杂度为O(N).