广度优先搜索（BFS）

图的遍历

之前我们说到过图是一种十分混乱的数据结构，因此对图的遍历当然没有对表和树那样清晰和明确。在这一篇和下一篇中我会详细介绍图的两种遍历：广度优先遍历（BFS）和深度优先遍历（DFS）

对于广度优先遍历和广度优先搜索请不要过于纠结，其实是一样的

对于广度优先遍历，我们需要根据提供的初始点给出遍历结果，这里的遍历结果用打印来表示，因此我们的任务是对于给定的顶点x,利用DFS不重复地打印所有顶点。下面给出方法的结构

1
2
3
void BFS(int x){
    //TODO:bfs and print
}

说明：用java不用c的原因是：我们关注的是算法的本身，用c写会有好多不利于我们理解的细节（比如一堆指针的指向），而用java可以封装没有必要的东西，把关注点更多放在算法本身上。

下面来看一下到底什么是BFS.

BFS的基本策略

我们以题图（如下）来进行讲解（设遍历的起始点是顶点3）

遍历的顺序

BFS类似树的层次遍历，也就是一层一层地往下遍历，我们这里定义一下：在遍历过程中，与第n层直接相连且未定义层数的点为第n+1层，下面是个例子：

  1. 毫无疑问，顶点3是第一层

  2. 与3只接相连的有顶点4和顶点0，那么顶点4和顶点0是第2层

  3. 与4相连的点有3，0，2，由于3和0已经是第一二曾，因此未被定义的点只有2，所有顶点2是第三层同意顶点1也是第三层（因为顶点1与处于第二层的顶点0直接相连）

  4. 所有的点已经定义，分层结束，得到如下的图：

    image
    我们的BFS就是按照第一层到第n层进行遍历的比如这个图的遍历顺序就是： 3->(4,0)->(1,2)(至于4和0，1和2的顺序得看图是怎么存储的，和BFS的关系不大)。

遍历的实现

根据上面的分析我们已经能大致分析出遍历的实现了（打印的点即为已经遍历的点）：

  1. 打印顶点3
  2. 找到与顶点3相邻的（且未被打印的）顶点（这里是4和0）
  3. 打印顶点4
  4. 找到与顶点4相邻的（且未被打印的）顶点…
  5. 打印顶点0
  6. 找到与顶点0相邻的顶点（且未被打印的）顶点..
  7. …

这样算法流程就清晰了起来。我们还需要注意一点，先找到的点总是先打印的，比如我们找到4和0后，先打印4，然后找与4相邻的点，再打印0，然后打印刚刚找到的和4相邻的点……不知聪明的你有没有发现这其中隐含了一个顶点的队列：

  • 找到与当前点相邻且为被打印的点是一个入队的过程
  • 打印顶点是一个出队的过程

下面是入队和出队的全过程：

  • 3（3入队）
  • 340（由3找到的4，0入队）
  • 40（与3相邻的点找完，3出队）
  • 402（由4找到2，2入队）
  • 02（与4相邻的点找完，4出队）
  • 021（由0找到1，1入队）
  • 21（与0相邻的点找完，0出队）
  • 1（没有与2相邻的，2出队）
  • （没有与1相邻的，1出队）

还有最后一个问题就是如何判断该点是否已经打印，这个问题很简单，打印的时候用一个数组visited[]存一下，在入队之前检查数组里面的情况，未被打印就入队就ok.

这样整个过程以及逻辑实现就十分清晰了，只剩最后的代码实现

代码实现（以邻接图的存储为例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 void BFS(int s){
    //参观过为true
    boolean visited[] = new boolean[V];
    //第一个遍历的节点已经访问，设为true
    LinkedList<Integer> queue = new LinkedList<>();//初始化队列
    visited[s] = true;//标记第一个点为已经打印
    queue.add(s);//把第一个节点加入队列
    
	while (queue.size()!=0){//全部出队==遍历结束
        s = queue.poll();//从队列出一个顶点
        System.out.println(s +" ");//打印该顶点
        //遍历与s顶点连接的顶点
        Iterator<Integer> i = adj[s].listIterator();
        while (i.hasNext()){
            int n = i.next();//若该节点没有访问
            if(!visited[n]){
                visited[n] = true;//访问该节点
                queue.add(n);//加入队列
            }
        }
       }
}

这样就完成的BFS,代码理解还是不难的，下一次应该是DFS（深度优先搜索）