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