本章内容广度优先算法（BFS）

广度优先搜索（Breadth-First-Search，简称BFS），又称宽度优先算法。它采用的是一种地毯式层层推进的搜索策略，即：从起始顶点开始从近到远依次搜索，直到找到目标顶点。

由于BFS是以先进先出的方式遍历顶点，因此，可以使用队列（queue）存储已经被搜索、相连顶点还未被搜索的顶点。

广度优先搜索算法基于图实现。

图（Graph）

图是一种非线性表结构。其中：

图中的元素称为顶点（vertex）。图中顶点之间的关系称为边（edge）。图中与顶点相连接的边的条数称为顶点的度（degree）。

图的种类

图的种类有很多，常用的有无向图、有向图、带权图：

无向图指的是边没有方向的图。有向图指的是边有方向的图。带权图指的是每条边都有权重的图。

如图所示：

在有向图中：

顶点的入度（In-degree）：表示有多少条边指向一个顶点。顶点的出度（Out-degree）：表示一个顶点有多少条边指向其他顶点。

图的存储方式

图的存储方式主要有邻接矩阵、邻接表。本文中BFS算法采用邻接表存储，因此简单介绍一下邻接表。

邻接表（Adjacency List）

有向图邻接表存储方式，如图所示：

其中：每个顶点对应一个链表，链表中存储的是与该顶点相连接的其他顶点。

无向图与有向图类似，每个顶点的链表中存储与该顶点有边相连的顶点。

图解BFS

如图所示：

图中，s表示起始顶点，t表示目标顶点，求解从s->t的最短路径。

使用BFS求解从s->t的最短路径，如图所示：

图中：

灰色顶点表示已经被搜索的顶点。绿色顶点表示已经被搜索、相连顶点还未被搜索的顶点。黄色顶点表示未被搜索的顶点。蓝色顶点表示目标顶点虚线箭头表示要搜索的层及搜索顺序。queue用于存储已经被搜索、相连顶点还未被搜索的顶点。visited用于存储已经被搜索的顶点。route用于存储相邻顶点之间的路径。

搜索步骤：

1）从起始顶点0开始搜索下一层的顶点，找到顶点1和顶点3将其加入到队列中，将visited数组中顶点1和顶点3对应的下标设置为1（表示已经被搜索），将route数组中顶点1和顶点3（route数组下标）对应的值设置为0（即：本轮搜索的起始顶点）。2）从队列中取出顶点1（先进先出）开始搜索下一层的顶点，找到顶点2和顶点4将其加入到队列中，将visited数组中顶点2和顶点4对应的下标设置为1（表示已经被搜索），将route数组中顶点2和顶点4（route数组下标）对应的值设置为1（即：本轮搜索的起始顶点）。3）依次类推，直到找到目标顶点。

注意：每轮搜索顶点时都会校验被搜索出来的顶点是否为目标顶点。

代码实现

/** * @author 南秋同学 * 广度优先算法 */public class Bfs {    /**     * 图中节点数     */    private final int number;    /**     * 采用邻接表存储图     */    private final LinkedList<Integer>[] adjacencyList;    public Bfs(int number){        this.number = number;        adjacencyList = new LinkedList[number];        for(int i=0; i<number; ++i){            adjacencyList[i] = new LinkedList<>();        }    }    /**     * 增加一条边(无向图一条边存两次)     * @param start 节点     * @param target 节点     */    public void addEdge(int start, int target){        adjacencyList[start].add(target);        adjacencyList[target].add(start);    }    /**     * BFS     * @param start 起始顶点     * @param target 目标顶点     */    public void bfs(int start, int target) {        if (start == target) {            return;        }        // 初始化记录已经被搜索顶点的数组        boolean[] visited = new boolean[number];        // 起始顶点设置为true，表示从起始顶点开始搜索        visited[start]=true;        // 初始化存储已经被搜索、相连顶点还未被搜索的顶点的队列        Queue<Integer> queue = new LinkedList<>();        // 将起始顶点加入队列，表示表示从起始顶点开始搜索        queue.add(start);        // 初始化记录已经被搜索顶点路径的数组，并设置数组中每个元素为-1        int[] route = new int[number];        for (int i = 0; i < number; ++i) {            route[i] = -1;        }        // 如果队列中存储的顶点不为空        while (queue.size() != 0) {            // 按先进先出的顺序取出顶点            int w = queue.poll();            // 遍历邻接表            for (int i = 0; i < adjacencyList[w].size(); ++i) {                // 获取与顶点相连的顶点                int q = adjacencyList[w].get(i);                // 如果顶点未被搜索过                if (!visited[q]) {                    // 设置与顶点q相连的源顶点                    route[q] = w;                    // 判断被搜索出来的顶点是否为目标顶点，是则打印路径并返回                    if (q == target) {                        print(route, start, target);                        return;                    }                    // 设置顶点q已经被搜索                    visited[q] = true;                    // 将已经被搜索、相连顶点还未被搜索的顶点加入到队列中，开启下一轮搜索                    queue.add(q);                }            }        }    }    /**     * 递归打印起始顶点到目标顶点的路径     * @param route 路径     * @param start 起始顶点     * @param target 目标顶点     */    private void print(int[] route, int start, int target) {        if (route[target] != -1 && target != start) {            print(route, start, route[target]);        }        System.out.print(target + " ");    }    public static void main(String[] args) {        Bfs bfs = new Bfs(8);        // 构建图        bfs.addEdge(0,1);        bfs.addEdge(0,3);        bfs.addEdge(1,2);        bfs.addEdge(1,4);        bfs.addEdge(3,4);        bfs.addEdge(2,5);        bfs.addEdge(4,5);        bfs.addEdge(4,6);        bfs.addEdge(5,7);        bfs.addEdge(6,7);        // 求解0～6的最短路径        bfs.bfs(0,6);    }}

广度优先搜索的时间复杂度为O(V+E)，其中，V表示顶点的个数，E表示边的条数。

广度优先搜索的空间复杂度为O(V)，需要使用queue队列、visited数组、route数组存储顶点数据，他们的大小不会超过顶点的个数。

【阅读推荐】

想了解其他常用算法（如：堆与堆排序、快速排序、二分查找、动态规划、带备忘录的递归、暴力穷举等）的童鞋请移步->算法系列合集（持续更新中）。

更多内容持续更新中......

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～