广度优先搜索（Breadth-first search）

遍历或搜索是可在图上执行的基本操作之一。在广度优先搜索(BFS)中，我们从一个特定的顶点开始，在进入下一层的顶点之前探索它当前深度的所有邻居。与树不同，图可以包含循环(第一个和最后一个顶点是相同的路径)。因此，我们必须跟踪访问过的顶点。在实现BFS时，我们使用队列数据结构。

图2表示一个示例图的BFS遍历的动画。注意顶点是如何被发现(黄色)和被访问(红色)的。

应用

• 用于确定最短路径和最小生成树。
• 被搜索引擎爬虫用来建立网页的索引。
• 用来在社交网络上搜索。
• 用于查找可用的邻接节点在对等网络，如BitTorrent。

无权重的bfs 框架

import java.util.*;

public class Graph {
    private Map<String, List<String>> adjList = new HashMap<>();

    // 向图中添加边
    public void addEdge(String source, String destination) {
        adjList.computeIfAbsent(source, k -> new LinkedList<>()).add(destination);
        adjList.computeIfAbsent(destination, k -> new LinkedList<>()); // 对于无向图，需要添加这行
    }

    // BFS 算法
    public void BFS(String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        // 将起始节点加入队列并标记为已访问
        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            String current = queue.poll();
            System.out.println(current);

            // 获取所有邻接节点
            for (String neighbor : adjList.getOrDefault(current, new LinkedList<>())) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    // 主函数，用于测试
    public static void main(String args[]) {
        Graph g = new Graph();

        // 构建图
        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("B", "D");
        g.addEdge("B", "E");
        g.addEdge("C", "F");
        g.addEdge("E", "F");

        // 执行BFS
        g.BFS("A");
    }
}