广度优先搜索 (Breadth-First Search, BFS)

算法原理

广度优先搜索（BFS）是一种图形搜索算法，用于遍历或搜索树或图。它从根节点开始，沿着树的宽度遍历树的节点，并尽可能先访问同一层的节点。换句话说，它是按层级顺序访问节点的。BFS使用队列数据结构来跟踪待访问的节点。从队列中取出一个节点，访问它，然后将其所有未访问的邻居节点加入队列。这个过程持续进行，直到队列为空。

算法步骤

1. 创建一个队列，将起始节点放入队列中
2. 创建一个集合或数组来记录已访问的节点
3. 当队列不为空时，执行以下操作：
   • 从队列中取出一个节点
   • 标记该节点为已访问
   • 访问该节点（例如打印节点值）
   • 将该节点的所有未访问邻居节点加入队列
4. 重复步骤3直到队列为空

代码实现

import java.util.*;

public class BFSGraph {
    // 图的邻接表表示
    private Map> adjList;
    
    public BFSGraph() {
        adjList = new HashMap<>();
    }
    
    // 添加边
    public void addEdge(int v, int w) {
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
    }
    
    // 广度优先搜索
    public void BFS(int startVertex) {
        // 创建访问标记数组
        Set visited = new HashSet<>();
        
        // 创建队列用于BFS
        Queue queue = new LinkedList<>();
        
        // 标记起始节点为已访问并加入队列
        visited.add(startVertex);
        queue.offer(startVertex);
        
        while (!queue.isEmpty()) {
            // 取出队列的第一个节点并打印
            int vertex = queue.poll();
            System.out.print(vertex + " ");
            
            // 获取该节点的所有邻接节点
            List neighbors = adjList.getOrDefault(vertex, new ArrayList<>());
            
            // 将所有未访问的邻接节点加入队列
            for (Integer neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }
    
    // 寻找从起点到终点的最短路径
    public List shortestPath(int startVertex, int endVertex) {
        Set visited = new HashSet<>();
        Map parent = new HashMap<>();
        Queue queue = new LinkedList<>();
        
        visited.add(startVertex);
        queue.offer(startVertex);
        parent.put(startVertex, null);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            
            // 如果找到目标节点，重构路径
            if (vertex == endVertex) {
                return reconstructPath(parent, startVertex, endVertex);
            }
            
            List neighbors = adjList.getOrDefault(vertex, new ArrayList<>());
            for (Integer neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    parent.put(neighbor, vertex);
                    queue.offer(neighbor);
                }
            }
        }
        
        // 如果未找到路径，返回空列表
        return new ArrayList<>();
    }
    
    // 重构路径
    private List reconstructPath(Map parent, int startVertex, int endVertex) {
        List path = new ArrayList<>();
        Integer current = endVertex;
        
        while (current != null) {
            path.add(current);
            current = parent.get(current);
        }
        
        Collections.reverse(path);
        return path;
    }

    // 测试方法
    public static void main(String[] args) {
        BFSGraph graph = new BFSGraph();
        
        // 构建图
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        
        System.out.println("BFS遍历结果 (从节点2开始):");
        graph.BFS(2);
        System.out.println();
        
        System.out.println("从节点1到节点3的最短路径:");
        List path = graph.shortestPath(1, 3);
        if (path.isEmpty()) {
            System.out.println("未找到路径");
        } else {
            System.out.println(path);
        }
    }
}

应用场景

• 最短路径查找：在无权图中寻找两点之间的最短路径
• 社交网络分析：查找两个人之间的最短关系链
• 网络爬虫：按层级爬取网页
• 垃圾回收：追踪引用链
• 广播系统：在网络中传播消息

优缺点