使用LinkedList实现BFS广度优先搜索算法

程序等于算法加数据结构。今天搞个算法玩玩。还记得曾经让我们备受折磨的广度优先搜索算法吗？今天就搞它，用LinkedList搞。

广度优先搜索（BFS，Breadth-First Search）是一种图遍历算法，通常用于寻找最短路径或遍历图中的所有节点。

BFS 的工作方式类似于“分层”遍历，依次访问离起始节点较近的节点，然后逐层向外扩展，直至所有节点都被访问或找到目标节点。

下面是 BFS 的详细解释，包括算法的工作原理、步骤、代码实现以及应用场景。

1. BFS 的核心概念

BFS 主要应用在无权重图中，它的特点是按层遍历每一个节点，即从起始节点开始，先访问它的所有邻居节点，然后再访问这些邻居节点的邻居，以此类推。因此，BFS 可以找到无权重图中从起点到目标节点的最短路径。

2. BFS 的实现步骤

BFS 的实现通常基于队列（Queue）结构，这种数据结构具有“先进先出”（FIFO）的特性，非常适合逐层扩展的遍历需求。

以下是 BFS 的基本步骤：

初始化队列：将起始节点加入队列。

标记已访问节点：为避免重复访问节点，通常需要一个 visited 集合来记录已访问的节点。

循环遍历：

从队列中取出一个节点。

访问该节点的所有未被访问的邻居节点，并将这些邻居节点加入队列，同时标记它们为已访问。

重复上述步骤，直到队列为空或找到目标节点。

3. BFS 的代码实现

假设我们有一个无向图表示的网络图（邻接列表），以下是 BFS 的简单实现：

import java.util.*;

public class BFSExample {

public static void bfs(Map<Integer, List<Integer>> graph, int start) {

Queue<Integer> queue = new LinkedList<>(); // 创建队列

Set<Integer> visited = new HashSet<>(); // 记录访问过的节点

queue.offer(start); // 起始节点入队

visited.add(start); // 标记起始节点已访问

while (!queue.isEmpty()) {

int node = queue.poll(); // 取出队列的第一个节点

System.out.println("Visited: " + node);

// 遍历该节点的所有邻居

for (int neighbor : graph.get(node)) {

if (!visited.contains(neighbor)) {

queue.offer(neighbor); // 未访问的邻居入队

visited.add(neighbor); // 标记该邻居已访问

}

}

}

}

public static void main(String[] args) {

// 示例图：邻接列表表示

Map<Integer, List<Integer>> graph = new HashMap<>();

// 1相邻的两个结点是2和3

graph.put(1, Arrays.asList(2, 3));

// 2相邻的两个结点是4和5

graph.put(2, Arrays.asList(4, 5));

// 3相邻的两个结点是6和空

graph.put(3, Arrays.asList(6));

// 4相邻的两个结点是空

graph.put(4, Arrays.asList());

graph.put(5, Arrays.asList());

graph.put(6, Arrays.asList());

// 从节点 1 开始 BFS

bfs(graph, 1);

}

}

在这个代码中：

graph 是一个邻接列表，表示无向图。

queue 用于存储下一层要访问的节点。

visited 集合用于记录已经访问的节点，防止重复访问。

每次从队列中取出一个节点，访问它的所有未被访问的邻居，将这些邻居加入队列，直至遍历完成。

网络图结构如下：

1

/ \

2 3

/ \ \

4 5 6

如果我们从节点 1 开始执行 BFS，遍历顺序为：1 -> 2 -> 3 -> 4 -> 5 -> 6。可以看到，BFS 是按层次逐层访问节点。

运行结果如下：

Visited: 1

Visited: 2

Visited: 3

Visited: 4

Visited: 5

Visited: 6

4. BFS 的应用场景

BFS 具有多种实际应用，尤其适用于图遍历、最短路径等问题。以下是一些常见的应用场景：

无权重图的最短路径：BFS 可以找到从起始节点到目标节点的最短路径，因为它逐层扩展，不会错过任何可能更短的路径。

连通性问题：判断图中的节点是否连通，例如判断两个人在社交网络中是否存在间接的朋友关系。

迷宫求解：在迷宫或网格中找出从起点到终点的最短路径。

图的层次遍历：例如在树形结构中，BFS 可以用来分层遍历每一层的节点。

5. BFS 的时间复杂度和空间复杂度

假设图的节点数为V，边数为E，则：

时间复杂度：O(V+E)，因为每个节点和边最多访问一次。

空间复杂度：O(V)，主要取决于 queue 和 visited 集合的大小。

6. BFS 和 DFS 的对比

最后总结

BFS 使用队列结构，按层遍历节点。

BFS 常用于寻找无权图的最短路径和层次遍历。

适合用于解决图的连通性问题、迷宫求解等。