广度优先搜索（BFS）在 Java 中的应用

简介

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

目录

1. 基础概念
2. 使用方法
3. 常见实践
4. 最佳实践
5. 小结
6. 参考资料

1. 基础概念

什么是 BFS

BFS 是一种图的遍历算法，它的核心思想是从起始节点开始，逐层地扩展节点。具体来说，它使用一个队列来存储待访问的节点，每次从队列中取出一个节点进行访问，并将其所有未访问的邻接节点加入队列。这样可以保证节点按照距离起始节点的距离从小到大的顺序被访问。

数据结构

在 Java 中实现 BFS 通常需要使用以下数据结构： - 队列（Queue）：用于存储待访问的节点。Java 中可以使用 LinkedList 来实现队列。 - 访问标记数组：用于记录每个节点是否已经被访问过，避免重复访问。

2. 使用方法

实现步骤

1. 初始化队列，并将起始节点加入队列。
2. 标记起始节点为已访问。
3. 当队列不为空时，执行以下操作：
   • 从队列中取出一个节点。
   • 访问该节点。
   • 将该节点的所有未访问的邻接节点加入队列，并标记为已访问。

代码示例

以下是一个简单的图的 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];

        // 创建队列用于 BFS
        LinkedList<Integer> queue = new LinkedList<Integer>();

        // 标记当前节点为已访问并将其加入队列
        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 方法实现了 BFS 遍历，使用一个 visited 数组来标记节点是否已访问，使用 LinkedList 作为队列。

3. 常见实践

最短路径问题

BFS 可以用于解决无权图的最短路径问题。由于 BFS 是逐层扩展节点的，所以第一次到达目标节点时的路径一定是最短路径。

代码示例

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
    int shortestPath(int s, int d) {
        boolean visited[] = new boolean[V];
        int distance[] = new int[V];

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

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

        while (queue.size() != 0) {
            s = queue.poll();

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

                    if (n == d) {
                        return distance[n];
                    }
                }
            }
        }
        return -1; // 未找到路径
    }

    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);

        int source = 0;
        int destination = 3;
        int shortest = g.shortestPath(source, destination);
        if (shortest != -1) {
            System.out.println("从 " + source + " 到 " + destination + " 的最短路径长度为: " + shortest);
        } else {
            System.out.println("未找到从 " + source + " 到 " + destination + " 的路径。");
        }
    }
}

代码解释

在 shortestPath 方法中，使用一个 distance 数组来记录每个节点到起始节点的距离。每次扩展节点时，更新其邻接节点的距离。当到达目标节点时，返回其距离。

4. 最佳实践

空间优化

在处理大规模图时，BFS 的空间复杂度可能会很高。可以考虑使用双向 BFS 来减少空间开销。双向 BFS 同时从起始节点和目标节点开始进行 BFS，当两个搜索相遇时，合并路径即可得到最短路径。

代码示例

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
    int bidirectionalBFS(int s, int d) {
        if (s == d) return 0;

        boolean visitedS[] = new boolean[V];
        boolean visitedD[] = new boolean[V];
        int distanceS[] = new int[V];
        int distanceD[] = new int[V];

        LinkedList<Integer> queueS = new LinkedList<Integer>();
        LinkedList<Integer> queueD = new LinkedList<Integer>();

        visitedS[s] = true;
        queueS.add(s);
        distanceS[s] = 0;

        visitedD[d] = true;
        queueD.add(d);
        distanceD[d] = 0;

        while (!queueS.isEmpty() && !queueD.isEmpty()) {
            int temp = BFSUtil(queueS, visitedS, visitedD, distanceS, distanceD);
            if (temp != -1) return temp;

            temp = BFSUtil(queueD, visitedD, visitedS, distanceD, distanceS);
            if (temp != -1) return temp;
        }
        return -1; // 未找到路径
    }

    private int BFSUtil(LinkedList<Integer> queue, boolean visited1[], boolean visited2[], int distance1[], int distance2[]) {
        int s = queue.poll();

        Iterator<Integer> i = adj[s].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (visited2[n]) {
                return distance1[s] + distance2[n] + 1;
            }
            if (!visited1[n]) {
                visited1[n] = true;
                distance1[n] = distance1[s] + 1;
                queue.add(n);
            }
        }
        return -1;
    }

    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);

        int source = 0;
        int destination = 3;
        int shortest = g.bidirectionalBFS(source, destination);
        if (shortest != -1) {
            System.out.println("从 " + source + " 到 " + destination + " 的最短路径长度为: " + shortest);
        } else {
            System.out.println("未找到从 " + source + " 到 " + destination + " 的路径。");
        }
    }
}

代码解释

在 bidirectionalBFS 方法中，同时从起始节点和目标节点开始进行 BFS。使用两个队列和两个访问标记数组。每次扩展节点时，检查是否与另一个搜索相遇。如果相遇，则返回最短路径长度。

5. 小结

本文介绍了 BFS 在 Java 中的基础概念、使用方法、常见实践以及最佳实践。BFS 是一种强大的图遍历算法，可以用于解决许多问题，如最短路径问题。在处理大规模图时，可以使用双向 BFS 来优化空间复杂度。

6. 参考资料

• 《算法导论》