图论（七）图的广度优先遍历BFS

前言

广度优先搜索是对图中的边进行系统性的探索来发现可以从源节点出发到达的所有节点。该算法能够计算从源节点到每个可到达的节点的最短距离（无权值）。其广度优先则体现在始终是对图进行逐层探索，当当前所在层探索完毕后才进入到邻居节点进一步探索。

一、图的广度优先遍历基本思想

• 1、图的广度优先搜索，简称BFS。
• 2、该遍历类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。

二、广度优先遍历算法步骤

• 1 访问初始结点v并标记结点v为已访问。

• 2 结点v入队列。

• 3 当队列非空时，继续执行，否则算法结束。

• 4 出队列，取得队头结点u。

• 5 查找结点u的第一个邻接结点w。

• 6 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：

  • 6.1 若结点w尚未被访问，则访问结点w并标记为已访问。
  • 6.2 结点w入队列。
  • 6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

三、广度优先遍历图文演示

广度优先遍历和树的层序遍历类似。

上图经过变形

特点：

• 1、把根节点放到队列的末尾；
• 2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们方法队列的末尾，并把这个元素记为下一级元素的前驱；
• 3、找到所要找到元素的结束程序；
• 4、如果遍历整个树还没有找到，结束遍历。

四、用邻接表进行广度优先遍历

4.1 构建数据结构

public class Graph {

    //顶点个数
    private int V;

    //边的条数
    private int E;

    //领接表的底层存储结构
    private TreeSet<Integer>[] adj;

}

4.2 通过该结构定义，构造一个图(无向图）

/**
 * @Author: huangyibo
 * @Date: 2022/3/28 1:02
 * @Description: 领接表, 目前只支持无向无权图
 */

public class Graph {

    //顶点个数
    private int V;

    //边的条数
    private int E;

    //领接表的底层存储结构
    private TreeSet<Integer>[] adj;

    public Graph(String filename){
        File file = new File(filename);
        try {
            Scanner scanner = new Scanner(file);
            V = scanner.nextInt();
            if(V < 0){
                throw new IllegalArgumentException("V must be non-negative");
            }
            adj = new TreeSet[V];
            //初始化领接表
            for (int i = 0; i < V; i++) {
                adj[i] = new TreeSet<>();
            }

            E = scanner.nextInt();
            if(E < 0){
                throw new IllegalArgumentException("E must be non-negative");
            }
            for (int i = 0; i < E; i++) {
                int a = scanner.nextInt();
                //校验顶点a是否合法
                validateVertex(a);

                int b = scanner.nextInt();
                //校验顶点b是否合法
                validateVertex(b);

                //校验是否是自环边
                if(a == b){
                    throw new IllegalArgumentException("Self Loop is Detected!");
                }
                //校验是否是平行边
                if(adj[a].contains(b)){
                    throw new IllegalArgumentException("Parallel Edges are Detected!");
                }
                adj[a].add(b);
                adj[b].add(a);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    /**
     * 校验顶点是否合法
     * @param v
     */
    private void validateVertex(int v){
        if(v < 0 || v >= V){
            throw new IllegalArgumentException("vertex " + v + " is invalid");
        }
    }

    /**
     * 获取顶点个数
     * @return
     */
    public int V(){
        return V;
    }

    /**
     * 获取边的条数
     * @return
     */
    public int E(){
        return E;
    }

    /**
     * 图中是否存在v到w的边
     * @param v
     * @param w
     * @return
     */
    public boolean hasEdge(int v, int w){
        //校验顶点v是否合法
        validateVertex(v);
        //校验顶点w是否合法
        validateVertex(w);
        return adj[v].contains(w);
    }

    /**
     * 返回和v相邻的顶点
     * @param v
     * @return
     */
    public Iterable<Integer> adj(int v){
        //校验顶点v是否合法
        validateVertex(v);
        return adj[v];
    }

    /**
     * 返回顶点v的度
     * 顶点v的度（Degree）是指在图中与v相关联的边的条数
     * @param v
     * @return
     */
    public int degree(int v){
        //校验顶点v是否合法
        validateVertex(v);
        return adj[v].size();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d\n", V, E));
        for (int v = 0; v < V; v++) {
            sb.append(String.format("%d : ", v));
            for (Integer w : adj[v]) {
                sb.append(String.format("%d ", w));
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}

4.3 邻接表的广度优先算法

/**
 * @Author: huangyibo
 * @Date: 2022/4/9 18:26
 * @Description: 图的广度优先遍历
 */

public class GraphBFS {

    private Graph G;

    /**
     * 图的顶点是否已经被遍历过
     */
    private boolean[] visited;

    /**
     * 图的广度优先遍历结果集
     */
    private List<Integer> order = new ArrayList<>();

    public GraphBFS(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        //循环所有顶点, 防止一个图出现多个连通图(连通分量)的情况
        for (int v = 0; v < G.V(); v++) {
            if(!visited[v]){
                bfs(v);
            }
        }
    }

    /**
     * 图的广度优先遍历
     * @param source
     */
    private void bfs(int source){
        Queue<Integer> queue = new LinkedList<>();
        //将源结点加入队列
        queue.add(source);
        //标记为已访问
        visited[source] = true;
        while(!queue.isEmpty()){
            Integer v = queue.remove();
            //当前出队顶点添加到图的广度优先遍历结果集
            order.add(v);
            //遍历顶点V的相邻顶点
            for (Integer w : G.adj((v))) {
                //如果没有遍历过
                if(!visited[w]){
                    //顶点w先入队
                    queue.add(w);
                    //标记w为已访问
                    visited[w] = true;
                }
            }
        }
    }

    /**
     * 图的广度优先遍历结果集
     * @return
     */
    public List<Integer> order(){
        return order;
    }

    public static void main(String[] args) {
        Graph graph = new Graph("src/main/resources/g1.txt");
        GraphBFS graphBFS = new GraphBFS(graph);
        System.out.println(graphBFS.order());
    }
}

g1.txt

7 6
0 1
0 2
1 3
1 4
2 3
2 6

五、基于广度优先遍历的应用

5.1 求解单源路径问题

/**
 * @Author: huangyibo
 * @Date: 2022/4/9 22:08
 * @Description: 基于图的广度优先遍历、求解单源路径问题
 */

public class SingleSourcePath {

    private Graph G;

    /**
     * 源节点
     */
    private int source;

    /**
     * 图的顶点是否已经被遍历过
     */
    private boolean[] visited;

    /**
     * 存储的是当前访问节点的前一个节点的值
     */
    private int[] pre;

    public SingleSourcePath(Graph G, int source){
        this.G = G;
        this.source = source;
        visited = new boolean[G.V()];
        pre = new int[G.V()];
        for (int i = 0; i < G.V(); i++) {
            pre[i] = -1;
        }
        bfs(source);
    }

    /**
     * 图的广度优先遍历
     * @param source
     */
    private void bfs(int source){
        Queue<Integer> queue = new LinkedList<>();
        //将源结点加入队列
        queue.add(source);
        //标记为已访问
        visited[source] = true;
        //源节点的pre节点为自己
        pre[source] = source;
        while(!queue.isEmpty()){
            Integer v = queue.remove();
            //遍历顶点V的相邻顶点
            for (Integer w : G.adj((v))) {
                //如果没有遍历过
                if(!visited[w]){
                    //顶点w先入队
                    queue.add(w);
                    //标记w为已访问
                    visited[w] = true;
                    //标记w顶点的pre顶点为v
                    pre[w] = v;
                }
            }
        }
    }

    /**
     * 判断源s到顶点target是否可达
     * @param target
     * @return
     */
    public boolean isConnectedTo(int target){
        G.validateVertex(target);
        return visited[target];
    }

    /**
     * 源s到顶点target的路径
     * @param target
     * @return
     */
    public List<Integer> path(int target){
        List<Integer> result = new ArrayList<>();
        if(!isConnectedTo(target)){
            //源s到顶点target不可达, 直接返回空集合
            return result;
        }
        int cur = target;
        //如果当前顶点不是源顶点
        while(cur != source){
            //路径添加当前顶点
            result.add(cur);
            //当前顶点的pre顶点赋值为当前顶点，便于继续循环
            cur = pre[cur];
        }
        //将当前顶点添加到路径中
        result.add(source);
        //路径反转后，即为源顶点到目标顶点的路径
        Collections.reverse(result);
        return result;
    }

    public static void main(String[] args) {
        Graph graph = new Graph("src/main/resources/g1.txt");
        SingleSourcePath ssPath = new SingleSourcePath(graph, 0);
        System.out.println("0 -> 6 : " + ssPath.path(6));
        System.out.println("0 -> 5 : " + ssPath.path(5));
    }
}

5.2 求解无向无权图最短路径问题

/**
 * @Author: huangyibo
 * @Date: 2022/4/9 22:08
 * @Description: 基于图的广度优先遍历、求解无向无权图最短路径问题
 */

public class USSPath {

    private Graph G;

    /**
     * 源节点
     */
    private int source;

    /**
     * 图的顶点是否已经被遍历过
     */
    private boolean[] visited;

    /**
     * 存储的是当前访问节点的前一个节点的值
     */
    private int[] pre;

    /**
     * 存储的是从源点到各目标顶点的路径的长度
     */
    private int[] dis;

    public USSPath(Graph G, int source){
        this.G = G;
        this.source = source;
        visited = new boolean[G.V()];
        pre = new int[G.V()];
        dis = new int[G.V()];
        for (int i = 0; i < G.V(); i++) {
            pre[i] = -1;
            dis[i] = -1;
        }
        bfs(source);
    }

    /**
     * 图的广度优先遍历
     * @param source
     */
    private void bfs(int source){
        Queue<Integer> queue = new LinkedList<>();
        //将源结点加入队列
        queue.add(source);
        //标记为已访问
        visited[source] = true;
        //源节点的pre节点为自己
        pre[source] = source;
        //从源点source到source的距离为 0
        dis[source] = 0;
        while(!queue.isEmpty()){
            Integer v = queue.remove();
            //遍历顶点V的相邻顶点
            for (Integer w : G.adj((v))) {
                //如果没有遍历过
                if(!visited[w]){
                    //顶点w先入队
                    queue.add(w);
                    //标记w为已访问
                    visited[w] = true;
                    //标记w顶点的pre顶点为v
                    pre[w] = v;
                    //标记源点到w顶点的路径长度
                    dis[w] = dis[v] + 1;
                }
            }
        }
    }

    /**
     * 判断源s到顶点target是否可达
     * @param target
     * @return
     */
    public boolean isConnectedTo(int target){
        G.validateVertex(target);
        return visited[target];
    }

    /**
     * 源s到顶点target的路径
     * @param target
     * @return
     */
    public List<Integer> path(int target){
        List<Integer> result = new ArrayList<>();
        if(!isConnectedTo(target)){
            //源s到顶点target不可达, 直接返回空集合
            return result;
        }
        int cur = target;
        //如果当前顶点不是源顶点
        while(cur != source){
            //路径添加当前顶点
            result.add(cur);
            //当前顶点的pre顶点赋值为当前顶点，便于继续循环
            cur = pre[cur];
        }
        //将当前顶点添加到路径中
        result.add(source);
        //路径反转后，即为源顶点到目标顶点的路径
        Collections.reverse(result);
        return result;
    }

    /**
     * 从源点到目标顶点的最短路径的长度
     * @param target
     * @return
     */
    public int dis(int target){
        G.validateVertex(target);
        return dis[target];
    }

    public static void main(String[] args) {
        Graph graph = new Graph("src/main/resources/g1.txt");
        USSPath ssPath = new USSPath(graph, 0);
        System.out.println("0 -> 6 : " + ssPath.path(6));
        System.out.println("0 -> 6 : " + ssPath.dis(6));
        System.out.println("0 -> 5 : " + ssPath.path(5));
        System.out.println("0 -> 6 : " + ssPath.dis(5));
    }
}

参考：
https://zhuanlan.zhihu.com/p/138073414

https://blog.csdn.net/chengqiuming/article/details/115304221