java实现广度优先搜索算法

广度优先搜索算法（BFS）是一种用于图遍历的算法。它从图的某个节点开始，依次访问其所有邻接节点，再依次访问邻接节点的邻接节点，以此类推，直到遍历完所有节点。

BFS使用队列数据结构来实现遍历过程。具体步骤如下：

1. 将起始节点标记为已访问，并将其加入队列。
2. 重复以下步骤直到队列为空：
   • 从队列中取出一个节点，并访问该节点。
   • 将该节点的所有未访问邻接节点加入队列，并标记为已访问。
3. 遍历完所有节点后，算法结束。

BFS的特点是按层遍历图，即先访问起始节点的所有邻接节点，然后访问邻接节点的邻接节点，以此类推。因此，BFS可以用来解决寻找最短路径的问题，即找到从起始节点到目标节点的最短路径。

BFS的时间复杂度为O(V+E)，其中V是图的节点数，E是图的边数。

以下是使用Java实现广度优先搜索算法的示例代码：

import java.util.LinkedList;
import java.util.Queue;

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

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

    // 广度优先搜索
    void BFS(int s) {
        boolean visited[] = new boolean[V]; // 记录顶点是否被访问过

        Queue<Integer> queue = new LinkedList<>(); // 创建队列用于广度优先搜索
        visited[s] = true; // 标记起始顶点为已访问
        queue.add(s); // 将起始顶点加入队列

        while (queue.size() != 0) {
            s = queue.poll(); // 从队列中弹出一个顶点并访问
            System.out.print(s + " ");

            // 遍历邻接表中的所有相邻顶点
            for (int i : adj[s]) {
                if (!visited[i]) {
                    visited[i] = true; // 标记相邻顶点为已访问
                    queue.add(i); // 将相邻顶点加入队列
                }
            }
        }
    }

    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开始)：");
        g.BFS(2);
    }
}

在上面的示例代码中，我们首先创建了一个Graph类来表示图。Graph类中包含一个邻接表用于存储图的结构，并提供addEdge方法来添加边。

然后定义了一个BFS方法来执行广度优先搜索算法。在BFS方法中，我们使用一个boolean数组visited来记录顶点是否被访问过。我们使用一个Queue来存储待访问的顶点，起始时将起始顶点加入队列，并标记为已访问。

接下来，我们开始进行循环，直到队列为空。在每次循环中，我们从队列中弹出一个顶点s，并访问该顶点，然后遍历邻接表中的所有相邻顶点。如果相邻顶点i没有被访问过，我们将其标记为已访问，并将其加入到队列中。

最后，我们在main方法中创建一个图对象，并添加一些边来测试广度优先搜索算法。我们从顶点2开始进行广度优先遍历，并输出遍历的结果。

以上就是用Java实现广度优先搜索算法的示例代码。