算法系列之搜索算法-广度优先搜索BFS

随着每年"金三银四"招聘季的到来，许多求职者开始积极备战面试。在众多面试环节中，机试往往是不可或缺的一环，而算法能力更是机试考核的重点。为此，我们特别推出算法系列文章，帮助大家系统复习算法知识。今天，我们将首先探讨搜索算法中的重要内容——广度优先搜索（BFS）。

图的介绍

图(Graph)是一种非线性的数据结构，由顶点（Vertex）和边（Edge）组成。如下图所示

分类如下：

无向图（Undirected Graph）：边没有方向，表示双向关系。

有向图（Directed Graph）：边有方向，表示单向关系。

加权图（Weighted Graph）：边带有权重。

无权图（Unweighted Graph）：边没有权重。

广度优先搜索（BFS, Breadth-First Search）

BFS（广度优先搜索，Breadth-First Search）是一种用于遍历或搜索图的算法。它从根节点开始，逐层访问（由近及远）所有相邻节点，直到找到目标节点或遍历完整个结构。BFS的核心思想是“先广后深”，即先访问离起点最近的节点，再逐步扩展到更远的节点。

BFS 通常借助于队列来实现。队列具有"先进先出（FIFO）"特性非常适合BFS的逐层遍历需求。其实现步骤如下：

初始化队列：使用一个队列来存储待访问的节点。标记已访问节点：使用一个集合记录已访问的节点，避免重复访问。从起点开始：将起点加入队列，并标记为已访问。循环处理队列： 从队列中取出一个节点。检查该节点是否为目标节点（如果有目标节点的条件）。如果不是目标节点，将其所有未访问的邻接节点加入队列，并标记为已访问。 重复步骤4，直到队列为空或找到目标节点。

示例代码如下：

public class BFSExample { // 定义图的节点类 static class Node { int value; List<Node> neighbors; public Node(int value) { this.value = value; this.neighbors = new ArrayList<>(); } // 添加邻接节点 public void addNeighbor(Node neighbor) { this.neighbors.add(neighbor); } } //bfs函数 public static void bfs(Node startNode) { if(startNode == null ) return; // 使用队列存储待访问的节点 Queue<Node> queue = new LinkedList<>(); // 使用HashSet记录已访问的节点 Set<Node> visited = new HashSet<>(); // 将起点加入队列并标记为已访问 queue.add(startNode); visited.add(startNode); // 遍历队列 while (!queue.isEmpty()) { // 从队列中取出一个节点 Node currentNode = queue.poll(); //打印当前顶点 System.out.print(currentNode.value + " "); // 遍历当前节点的所有邻接节点 for (Node neighbor : currentNode.neighbors) { // 如果邻接节点未被访问，则加入队列并标记为已访问 if (!visited.contains(neighbor)) { queue.add(neighbor); visited.add(neighbor); } } } } public static void main(String[] args) { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); Node node6 = new Node(6); node1.addNeighbor(node2); node1.addNeighbor(node3); node1.addNeighbor(node5); node2.addNeighbor(node1); node2.addNeighbor(node3); node2.addNeighbor(node5); node3.addNeighbor(node1); node3.addNeighbor(node2); node3.addNeighbor(node4); node3.addNeighbor(node6); node4.addNeighbor(node3); node4.addNeighbor(node6); node5.addNeighbor(node2); node5.addNeighbor(node6); node6.addNeighbor(node3); node6.addNeighbor(node4); node6.addNeighbor(node5); bfs(node2); } } BFS的特点 逐层遍历：BFS按层次顺序访问节点，适合求解最短路径问题、层次遍历和连通性问题空间复杂度较高：需要存储所有待访问的节点，空间复杂度通常为O(V)，其中V是节点数量。时间复杂度：对于图，时间复杂度为O(V + E)，其中V是节点数，E是边数。 BFS 示例题

以下列举了一些机试题

BOSS的收入 题目描述：

一个 XX 产品行销总公司，只有一个boss，其有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销。规定，每个月，下级分销需要将自己的总收入(自己的+下级上交的)每满 100 元上交 15 元给自己的上级。

现给出一组分销的关系，和每个分销的收入，请找出boss并计算出这个boss的收入。

比如：

收入 100 元，上交 15 元；

收入 199 元（99 元不够 100），上交 15 元，

收入 200 元，上交 30 元。

输入：

分销关系和收入: 【【分销id 上级分销的Id收入】，【分销id 上级分销的id收入】，【分销id 上级分销的id收入】】

分销ID范围 0…65535 收入范围 0…65535，单位元

提示：输入的数据只存在 1 个boss，不存在环路

输出：【boss的ID，总收入】

输入描述 第 1 行输入关系的总数量 N

第 2 行开始，输入关系信息，格式：分销ID 上级分销ID 收入

比如：

5 1 0 100 2 0 199 3 0 200 4 0 200 5 0 200

输出描述 输出：boss的ID 总收入 比如： 0 120

补充说明 给定的输入数据都是合法的，不存在坏路，重复的。

代码如下：

public class BFSBoss { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取关系的总数量 int N = scanner.nextInt(); // 用于存储每个分销商的上级 Map<Integer, Integer> parentMap = new HashMap<>(); // 用于存储每个分销商的收入 Map<Integer, Integer> incomeMap = new HashMap<>(); // 构建⼊度哈希表，key是节点名，value是⼊度（其有几个下级分销商） Map<Integer, Integer> indegree = new HashMap<>(); // 读取所有关系 for (int i = 0; i < N; i++) { int id = scanner.nextInt(); int parentId = scanner.nextInt(); int income = scanner.nextInt(); parentMap.put(id, parentId); incomeMap.put(id, income); // 初始化子节点列表 indegree.put(parentId, indegree.getOrDefault(parentId, 0)+1); } // 找到boss（没有上级的分销商） int bossId = -1; for (int id : indegree.keySet()) { if (!parentMap.containsKey(id)) { bossId = id; break; } } // BFS遍历计算收入 Queue<Integer> queue = new LinkedList<>(); for (int id : parentMap.keySet()) { if (indegree.getOrDefault(id,0) == 0) { queue.add(id); // 将所有叶子节点加入队列 } } while (!queue.isEmpty()) { int currentId = queue.poll(); if (currentId == bossId) { break; // 已经到达boss，无需再向上传递 } int parentId = parentMap.get(currentId); // 计算当前分销商的总收入 int totalIncome = incomeMap.get(currentId); // 计算需要上交的收入 int submitIncome = (totalIncome / 100) * 15; // 更新当前分销商上级的收入 incomeMap.put(parentId, incomeMap.getOrDefault(parentId,0) + submitIncome); // 更新上级分销商的⼊度 indegree.put(parentId, indegree.get(parentId)-1); // 上级分销商的下级分销收入上交完成，则将上级分销商加入队列 if(indegree.get(parentId) == 0){ queue.add(parentId); } } // 输出boss的ID和总收入 System.out.println(bossId + " " + incomeMap.get(bossId)); } } 总结

广度优先搜索（BFS）是一种非常强大的算法，特别适用于解决最短路径、层次遍历和连通性问题。在面试中，掌握BFS的基本实现和应用场景，能够帮助你高效解决许多与图或树相关的问题。希望本文的介绍和例题能够帮助你更好地理解和应用BFS算法。