Java 广度优先搜索（BFS）全面解析

简介

广度优先搜索（Breadth First Search，简称 BFS）是一种用于遍历或搜索树或图的算法。它从根节点（或起始节点）开始，逐层地访问节点，先访问距离起始节点最近的所有节点，再依次访问距离更远的节点。在 Java 中，BFS 是一种非常实用的算法，可用于解决诸如最短路径问题、连通性问题等。本文将详细介绍 Java 中广度优先搜索的基础概念、使用方法、常见实践以及最佳实践。

基础概念

广度优先搜索的原理

BFS 算法使用队列（Queue）来实现。从起始节点开始，将其加入队列，然后不断从队列中取出节点进行访问，并将该节点的所有未访问过的邻接节点加入队列。重复这个过程，直到队列为空。这样可以保证节点是按照距离起始节点的远近顺序依次被访问的。

适用场景

最短路径问题：在无权图中，BFS 可以找到从起始节点到目标节点的最短路径。
连通性问题：判断图中两个节点是否连通。
层次遍历：按层遍历树或图。

使用方法

实现步骤

创建一个队列用于存储待访问的节点。
将起始节点加入队列，并标记为已访问。
当队列不为空时，执行以下操作：
- 从队列中取出一个节点。
- 访问该节点。
- 将该节点的所有未访问过的邻接节点加入队列，并标记为已访问。

代码示例

以下是一个使用 BFS 遍历图的 Java 代码示例：

import java.util.*;

class Graph {
    private int V; // 顶点数
    private LinkedList<Integer> adj[]; // 邻接表

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // BFS 遍历
    void BFS(int s) {
        boolean visited[] = new boolean[V];

        LinkedList<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("从顶点 2 开始的 BFS 遍历:");
        g.BFS(2);
    }
}

代码解释

Graph 类表示一个图，使用邻接表来存储图的结构。
addEdge 方法用于向图中添加边。
BFS 方法实现了广度优先搜索，使用 visited 数组来标记节点是否已访问，使用 LinkedList 作为队列。

常见实践

最短路径问题

在无权图中，BFS 可以用来找到从起始节点到目标节点的最短路径。只需要在 BFS 过程中记录每个节点的前驱节点，最后从目标节点回溯到起始节点即可得到最短路径。

import java.util.*;

class ShortestPathBFS {
    private int V;
    private LinkedList<Integer> adj[];

    ShortestPathBFS(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    void shortestPath(int s, int d) {
        boolean visited[] = new boolean[V];
        int[] prev = new int[V];
        Arrays.fill(prev, -1);

        LinkedList<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            int node = queue.poll();
            if (node == d) {
                break;
            }
            Iterator<Integer> i = adj[node].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    prev[n] = node;
                    queue.add(n);
                }
            }
        }

        List<Integer> path = new ArrayList<>();
        for (int at = d; at != -1; at = prev[at]) {
            path.add(at);
        }
        Collections.reverse(path);

        if (path.get(0) != s) {
            System.out.println("未找到路径");
            return;
        }

        System.out.println("最短路径: " + path);
    }

    public static void main(String args[]) {
        ShortestPathBFS g = new ShortestPathBFS(8);
        g.addEdge(0, 1);
        g.addEdge(0, 3);
        g.addEdge(1, 2);
        g.addEdge(3, 4);
        g.addEdge(3, 7);
        g.addEdge(4, 5);
        g.addEdge(4, 6);
        g.addEdge(4, 7);
        g.addEdge(5, 6);
        g.addEdge(6, 7);

        int start = 0;
        int end = 7;
        g.shortestPath(start, end);
    }
}

连通性问题

可以使用 BFS 来判断图中两个节点是否连通。从起始节点开始进行 BFS 遍历，如果在遍历过程中访问到了目标节点，则说明两个节点连通。

最佳实践

优化队列的使用

在 Java 中，建议使用 ArrayDeque 作为队列，因为它的性能比 LinkedList 更好。

import java.util.ArrayDeque;
import java.util.Queue;

// ...
Queue<Integer> queue = new ArrayDeque<>();
// ...

避免重复访问

在 BFS 过程中，使用 visited 数组来标记节点是否已访问，避免重复访问，提高效率。

空间复杂度优化

如果图非常大，可以考虑使用位集（BitSet）来代替布尔数组，以节省空间。

import java.util.BitSet;

// ...
BitSet visited = new BitSet(V);
// ...

小结

广度优先搜索是一种非常实用的图遍历算法，在 Java 中可以使用队列来实现。它适用于最短路径问题、连通性问题等。在使用 BFS 时，需要注意避免重复访问，优化队列的使用，以及根据实际情况优化空间复杂度。通过本文的介绍，希望读者能够深入理解并高效使用 Java 中的广度优先搜索算法。

参考资料

《算法导论》
Java 官方文档
GeeksforGeeks 网站相关文章