java广度优先搜索

Java广度优先搜索（BFS）是一种图遍历算法，用于在一个图中从给定的起始节点开始，按照广度优先的顺序遍历所有可达节点。BFS通常使用队列来实现。

以下是Java实现广度优先搜索的基本步骤：
1. 创建一个队列，并将起始节点入队。
2. 创建一个HashSet或HashMap来记录已访问的节点，防止重复访问。
3. 进入循环，直到队列为空：
- 从队列中取出一个节点作为当前节点。
- 将当前节点标记为已访问。
- 处理当前节点，例如输出节点值或进行其他操作。
- 将当前节点的所有未访问过的邻居节点入队。
4. 循环结束后，遍历完成。

下面是一个简单的Java代码示例，演示了如何使用BFS遍历一个图：

import java.util.*;

public class BFS {
    public void bfsTraversal(Graph graph, int startNode) {
        Queue<Integer> queue = new LinkedList<>();        Set<Integer> visited = new HashSet<>();

        queue.add(startNode);
        visited.add(startNode);

        while (!queue.isEmpty()) {
            int currentNode = queue.poll();
            System.out.print(currentNode + " ");

            List<Integer> neighbors = graph.getNeighbors(currentNode);
            for (int neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

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

        BFS bfs = new BFS();
        bfs.bfsTraversal(graph, 0);
    }
}

class Graph {
    private int vertices;
    private List<List<Integer>> adjacencyList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList.get(source).add(destination);
        adjacencyList.get(destination).add(source);
    }

    public List<Integer> getNeighbors(int vertex) {
        return adjacencyList.get(vertex);
    }
}

这段代码中，我们创建了一个Graph类来表示图，使用邻接表来存储图的结构。然后，我们使用BFS类中的bfsTraversal方法来执行广度优先搜索，并传入起始节点的索引。