广度优先搜索(BFS)详解：从入门到精通-det365娱乐官网登录-det365娱乐官网登录-bat365官方登录中文-365系统维护

一、BFS基本概念1. 什么是BFS？广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树/图的算法。它的特点是：

从起点开始，逐层遍历先访问离起点近的节点，再访问离起点远的节点保证找到的路径是最短路径想象你在一个游乐园里找朋友：

你先在当前位置环顾四周然后向外扩展一圈，检查附近的区域如此扩展下去，直到找到朋友这就是BFS的基本思想2. BFS中的核心数据结构：队列队列（Queue）是BFS算法的核心数据结构，它具有以下特点：

先进先出（FIFO）：最先加入队列的元素最先被处理有序性：保证了节点访问的顺序性，符合”逐层遍历”的需求层次性：通过队列可以方便地划分和处理每一层的节点为什么BFS需要使用队列？

保持顺序：队列确保我们按照距离起点的远近顺序处理节点层次管理：队列帮助我们追踪当前正在处理的层级状态记录：队列存储了待处理的节点，避免重复访问3. BFS的核心特征层次性按层级顺序访问节点同一层的节点被一起处理确保距离起点相同的节点被同时访问最短路径总是先找到最短路径适合解决最短距离问题路径长度等于层级深度完整性保证访问所有可达节点不会遗漏任何可能的路径适合寻找所有可能解4. BFS的优化方向：双向BFS双向BFS是一种重要的优化技术，它的基本思想是：

同时从起点和终点开始搜索当两个搜索相遇时，就找到了最短路径为什么双向BFS能提高效率？

搜索空间缩小单向BFS：搜索空间呈指数增长，(O(b^d))双向BFS：两端搜索空间各为(O(b^{d/2}))总体效果：(O(b^{d/2} + b^{d/2}) « O(b^d))实际应用场景起点和终点都已知搜索空间对称分支因子（每个节点的平均子节点数）较大举例说明：

单向BFS：

第1层：1个节点

第2层：3个节点

第3层：9个节点

第4层：27个节点

总计：40个节点

双向BFS：

从起点：

第1层：1个节点

第2层：3个节点

从终点：

第1层：1个节点

第2层：3个节点

总计：8个节点

二、BFS的实现方式1. 队列实现 1

// 二叉树的BFS遍历

class TreeNode {

var val: Int

var left: TreeNode?

var right: TreeNode?

init(_ val: Int) {

self.val = val

}

func bfs(_ root: TreeNode?) {

// 1. 处理空树

guard let root = root else { return }

// 2. 创建队列并将根节点入队

var queue: [TreeNode] = [root]

// 3. 当队列不为空时循环

while !queue.isEmpty {

// 4. 获取当前层的节点数

let size = queue.count

// 5. 处理当前层的所有节点

for _ in 0..

let node = queue.removeFirst()

print(node.val)

// 6. 将子节点加入队列

if let left = node.left {

queue.append(left)

}

if let right = node.right {

queue.append(right)

}

// 使用示例

let root = TreeNode(1)

root.left = TreeNode(2)

root.right = TreeNode(3)

bfs(root) // 输出: 1 2 3

2. 双向队列（Deque）实现什么是双向队列？双向队列（Double-ended queue，简称Deque）是一种特殊的队列，它具有以下特点：

可以在队列的两端进行插入和删除操作结合了栈（LIFO）和队列（FIFO）的特性比普通队列更灵活，但实现也更复杂为什么需要双向队列？

性能优化普通队列在头部删除元素的时间复杂度为O(n)双向队列可以在常数时间O(1)完成两端的操作适合需要频繁在两端操作的场景特殊场景处理滑动窗口问题回文字符串判断需要同时支持FIFO和LIFO操作的场景双向队列的实现 1

// 双向队列的基本实现

class Deque {

// 使用数组作为底层存储

private var array: [T] = []

// 判断队列是否为空

var isEmpty: Bool { array.isEmpty }

// 获取队列大小

var count: Int { array.count }

// 查看队首元素

var first: T? { array.first }

// 查看队尾元素

var last: T? { array.last }

// 在队首添加元素 - O(1)

func addFirst(_ element: T) {

array.insert(element, at: 0)

}

// 在队尾添加元素 - O(1)

func addLast(_ element: T) {

array.append(element)

}

// 从队首移除元素 - O(1)

func removeFirst() -> T? {

guard !isEmpty else { return nil }

return array.removeFirst()

}

// 从队尾移除元素 - O(1)

func removeLast() -> T? {

guard !isEmpty else { return nil }

return array.removeLast()

}

// 使用双向队列进行BFS遍历

func bfsWithDeque(_ root: TreeNode?) {

guard let root = root else { return }

let deque = Deque()

deque.addLast(root) // 将根节点加入队尾

while !deque.isEmpty {

// 获取当前层的节点数

let levelSize = deque.count

// 处理当前层的所有节点

for _ in 0..

// 从队首取出节点

guard let node = deque.removeFirst() else { continue }

print(node.val)

// 将子节点加入队尾

if let left = node.left {

deque.addLast(left)

}

if let right = node.right {

deque.addLast(right)

}

双向队列在BFS中的应用场景二叉树层次遍历优化问题描述：给定一个二叉树，返回其按层序遍历得到的节点值。即逐层地，从左到右访问所有节点。

为什么使用双向队列？

普通数组在头部删除元素需要O(n)时间双向队列在头部删除元素只需O(1)时间对于大规模二叉树，性能提升明显解题思路：

使用双向队列存储每层节点每次处理一层时，记录当前层的节点数从队首取出节点处理，从队尾添加子节点重复这个过程直到队列为空 1

// 使用双向队列优化层次遍历

func levelOrderWithDeque(_ root: TreeNode?) -> [[Int]] {

var result: [[Int]] = []

guard let root = root else { return result }

let deque = Deque()

deque.addLast(root)

while !deque.isEmpty {

let levelSize = deque.count

var currentLevel: [Int] = []

for _ in 0..

if let node = deque.removeFirst() {

currentLevel.append(node.val)

// 从左到右添加子节点

if let left = node.left {

deque.addLast(left)

}

if let right = node.right {

deque.addLast(right)

}

result.append(currentLevel)

}

return result

}

滑动窗口最大值问题描述：给定一个数组 nums 和一个大小为 k 的滑动窗口，这个窗口从数组的最左侧移动到最右侧，每次只能看到窗口内的 k 个数字。滑动窗口每次向右移动一位，求每个窗口中的最大值。

例如：

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3

输出: [3,3,5,5,6,7]

解释:

滑动窗口的位置最大值

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

为什么使用双向队列？

需要在O(1)时间内获取窗口最大值需要高效地维护一个单调递减序列双向队列可以同时支持队首队尾的操作解题思路：

使用双向队列存储元素下标保持队列中的元素单调递减移除窗口外的元素（从队首）移除小于当前元素的值（从队尾）队首元素即为当前窗口最大值 1

// 使用双向队列解决滑动窗口最大值问题

func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {

var result: [Int] = []

let deque = Deque() // 存储索引

for i in 0..

// 移除窗口外的元素

while !deque.isEmpty && deque.first! < i - k + 1 {

_ = deque.removeFirst()

}

// 移除所有小于当前元素的值

while !deque.isEmpty && nums[deque.last!] < nums[i] {

_ = deque.removeLast()

}

// 添加当前元素

deque.addLast(i)

// 当窗口形成后，记录最大值

if i >= k - 1 {

result.append(nums[deque.first!])

}

return result

}

回文字符串判断问题描述：给定一个字符串，判断它是否是回文串。只考虑字母和数字字符，忽略大小写。

例如：

输入: "A man, a plan, a canal: Panama"

输出: true

解释: "amanaplanacanalpanama" 是回文串

输入: "race a car"

输出: false

解释: "raceacar" 不是回文串

为什么使用双向队列？

需要同时从字符串的两端进行比较双向队列可以高效地进行首尾操作避免了创建新的字符串副本解题思路：

将有效字符（字母和数字）依次加入双向队列同时从队列两端取出字符进行比较如果所有字符都匹配，则是回文串如果出现不匹配，则不是回文串 1

// 使用双向队列判断回文字符串

func isPalindrome(_ s: String) -> Bool {

let deque = Deque()

// 将字符加入双向队列

for char in s.lowercased() where char.isLetter || char.isNumber {

deque.addLast(char)

}

// 从两端比较字符

while deque.count > 1 {

if deque.removeFirst() != deque.removeLast() {

return false

}

return true

}

// 使用示例

let s1 = "A man, a plan, a canal: Panama"

print(isPalindrome(s1)) // 输出: true

let s2 = "race a car"

print(isPalindrome(s2)) // 输出: false

通过这些实际应用场景，我们可以看到双向队列在不同类型的问题中的优势：

在层次遍历中提供了更高效的节点访问在滑动窗口问题中维护了单调序列在回文串判断中简化了首尾比较操作三、实际应用示例1. 二叉树的层序遍历问题描述：给定一个二叉树，返回其按层序遍历得到的节点值。即逐层地，从左到右访问所有节点。

class Solution {

func levelOrder(_ root: TreeNode?) -> [[Int]] {

var result: [[Int]] = []

guard let root = root else { return result }

var queue: [TreeNode] = [root]

while !queue.isEmpty {

let size = queue.count

var currentLevel: [Int] = []

for _ in 0..

let node = queue.removeFirst()

currentLevel.append(node.val)

if let left = node.left {

queue.append(left)

}

if let right = node.right {

queue.append(right)

}

result.append(currentLevel)

}

return result

}

// 使用示例

/ \

9 20

/ \

15 7

输出: [

[3],

[9,20],

[15,7]

]

2. 最短路径问题问题描述：在一个二维网格中，1表示陆地，0表示水域。找到从起点到终点的最短路径长度。只能上下左右移动。

class Solution {

func shortestPath(_ grid: [[Int]], _ start: (Int, Int), _ end: (Int, Int)) -> Int {

let rows = grid.count

let cols = grid[0].count

let directions = [(0,1), (1,0), (0,-1), (-1,0)]

var queue: [(Int, Int)] = [start]

var visited = Set()

var steps = 0

// 将坐标转换为唯一标识符

func getKey(_ pos: (Int, Int)) -> String {

return "\(pos.0),\(pos.1)"

}

// 标记起点为已访问

visited.insert(getKey(start))

while !queue.isEmpty {

let size = queue.count

for _ in 0..

let current = queue.removeFirst()

// 到达终点

if current == end {

return steps

}

// 尝试四个方向

for (dx, dy) in directions {

let newX = current.0 + dx

let newY = current.1 + dy

let newPos = (newX, newY)

let key = getKey(newPos)

// 检查边界和是否可行

if newX >= 0 && newX < rows &&

newY >= 0 && newY < cols &&

grid[newX][newY] == 1 &&

!visited.contains(key) {

queue.append(newPos)

visited.insert(key)

}

steps += 1

}

return -1 // 无法到达终点

}

// 使用示例

let grid = [

[1,1,0,0],

[1,1,1,1],

[0,0,0,1]

]

let solution = Solution()

let result = solution.shortestPath(grid, (0,0), (3,3))

print("最短路径长度：\(result)") // 输出：6

3. 单词接龙问题问题描述：给定两个单词（起始单词和结束单词）和一个字典，找出从起始单词到结束单词的最短转换序列的长度。每次转换只能改变一个字母。

class Solution {

func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {

// 将wordList转换为Set以提高查找效率

var wordSet = Set(wordList)

// 如果结束单词不在字典中，无法完成转换

if !wordSet.contains(endWord) {

return 0

}

// 创建队列并将起始单词入队

var queue: [String] = [beginWord]

var visited = Set()

var level = 1

while !queue.isEmpty {

let size = queue.count

for _ in 0..

let currentWord = queue.removeFirst()

// 找到结束单词

if currentWord == endWord {

return level

}

// 尝试改变每个位置的字母

var wordArray = Array(currentWord)

for i in 0..

let originalChar = wordArray[i]

// 尝试所有可能的字母

for c in "abcdefghijklmnopqrstuvwxyz" {

wordArray[i] = c

let newWord = String(wordArray)

// 如果新单词在字典中且未访问过

if wordSet.contains(newWord) && !visited.contains(newWord) {

queue.append(newWord)

visited.insert(newWord)

}

// 恢复原始字母

wordArray[i] = originalChar

}

level += 1

}

return 0 // 无法完成转换

}

// 使用示例

let beginWord = "hit"

let endWord = "cog"

let wordList = ["hot","dot","dog","lot","log","cog"]

let solution = Solution()

print("最短转换序列长度：\(solution.ladderLength(beginWord, endWord, wordList))") // 输出：5

// 转换序列：hit -> hot -> dot -> dog -> cog

四、BFS的优化技巧1. 双向BFS双向BFS的实现需要考虑以下几个关键点：

两个搜索集合的管理分别维护起点集合和终点集合选择较小的集合进行扩展（优化策略）检测两个集合是否相交访问状态的记录记录每个节点的访问状态避免重复访问检测是否找到路径 1

// 双向BFS基础模板

func bidirectionalBFS(_ start: String, _ end: String, _ wordSet: Set) -> Int {

// 1. 特殊情况处理

guard wordSet.contains(end) else { return 0 }

// 2. 初始化两端的搜索集合

var beginSet: Set = [start]

var endSet: Set = [end]

var visited: Set = []

var level = 1

// 3. 当两端都还有节点时继续搜索

while !beginSet.isEmpty && !endSet.isEmpty {

// 4. 优化：选择较小的集合进行扩展

if beginSet.count > endSet.count {

let temp = beginSet

beginSet = endSet

endSet = temp

}

// 5. 扩展选定的集合

var nextLevel: Set = []

for word in beginSet {

// 6. 生成所有可能的下一步状态

let nextStates = getNextStates(word)

for nextWord in nextStates {

// 7. 如果另一端已经访问过这个状态，说明找到了最短路径

if endSet.contains(nextWord) {

return level + 1

}

// 8. 否则，如果这是一个有效且未访问的状态，加入下一层

if wordSet.contains(nextWord) && !visited.contains(nextWord) {

nextLevel.insert(nextWord)

visited.insert(nextWord)

}

// 9. 更新搜索集合和层数

beginSet = nextLevel

level += 1

}

return 0 // 未找到路径

}

// 辅助函数：生成下一步可能的状态

func getNextStates(_ word: String) -> [String] {

var result: [String] = []

var chars = Array(word)

for i in 0..

let original = chars[i]

for c in "abcdefghijklmnopqrstuvwxyz" {

chars[i] = c

result.append(String(chars))

}

chars[i] = original

}

return result

}

2. 状态压缩 1

// 使用位运算进行状态压缩

func bfsWithBitMask(_ start: Int, _ target: Int, _ n: Int) -> Int {

var queue: [Int] = [start]

var visited = Set()

var level = 0

while !queue.isEmpty {

let size = queue.count

for _ in 0..

let current = queue.removeFirst()

if current == target {

return level

}

// 使用位运算生成下一状态

for i in 0..

let next = current ^ (1 << i)

if !visited.contains(next) {

queue.append(next)

visited.insert(next)

}

level += 1

}

return -1

}

3. 记忆化搜索 1

// 带记忆化的BFS

func bfsWithMemo(_ start: String, _ target: String, _ dict: Set) -> Int {

var memo: [String: Int] = [:]

var queue: [(String, Int)] = [(start, 0)]

while !queue.isEmpty {

let (current, steps) = queue.removeFirst()

// 检查记忆化存储

if let cached = memo[current] {

if cached <= steps {

continue

}

// 更新记忆化存储

memo[current] = steps

// 生成下一步可能的状态

// ...

}

return memo[target] ?? -1

}

五、常见问题和解决方案1. 处理环 1

// 处理图中的环

func bfsWithCycleDetection(_ graph: [[Int]], _ start: Int) -> [Int] {

var queue: [Int] = [start]

var visited = Set()

var parent: [Int: Int] = [:]

visited.insert(start)

while !queue.isEmpty {

let current = queue.removeFirst()

for next in graph[current] {

if visited.contains(next) {

// 检测到环

if parent[current] != next {

// 找到一个非父子关系的已访问节点

return reconstructCycle(current, next, parent)

}

} else {

visited.insert(next)

parent[next] = current

queue.append(next)

}

return []

}

2. 多源BFS 1

// 多源BFS示例

func multiSourceBFS(_ grid: [[Int]], _ sources: [(Int, Int)]) -> [[Int]] {

var result = Array(repeating: Array(repeating: Int.max, count: grid[0].count),

count: grid.count)

var queue = sources

// 初始化源点距离

for (x, y) in sources {

result[x][y] = 0

}

let directions = [(0,1), (1,0), (0,-1), (-1,0)]

var distance = 0

while !queue.isEmpty {

distance += 1

let size = queue.count

for _ in 0..

let (x, y) = queue.removeFirst()

for (dx, dy) in directions {

let newX = x + dx

let newY = y + dy

if newX >= 0 && newX < grid.count &&

newY >= 0 && newY < grid[0].count &&

result[newX][newY] == Int.max {

result[newX][newY] = distance

queue.append((newX, newY))

}

return result

}

3. 带权BFS 1

// 带权BFS（使用优先队列）

struct PriorityQueue {

private var elements: [(T, Int)]

private let comparator: (Int, Int) -> Bool

init(comparator: @escaping (Int, Int) -> Bool) {

self.elements = []

self.comparator = comparator

}

mutating func enqueue(_ element: T, priority: Int) {

elements.append((element, priority))

siftUp(from: elements.count - 1)

}

mutating func dequeue() -> (T, Int)? {

guard !elements.isEmpty else { return nil }

elements.swapAt(0, elements.count - 1)

let result = elements.removeLast()

if !elements.isEmpty {

siftDown(from: 0)

}

return result

}

private mutating func siftUp(from index: Int) {

var child = index

var parent = (child - 1) / 2

while child > 0 && comparator(elements[child].1, elements[parent].1) {

elements.swapAt(child, parent)

child = parent

parent = (child - 1) / 2

}

private mutating func siftDown(from index: Int) {

var parent = index

while true {

var candidate = parent

let leftChild = 2 * parent + 1

let rightChild = 2 * parent + 2

if leftChild < elements.count &&

comparator(elements[leftChild].1, elements[candidate].1) {

candidate = leftChild

}

if rightChild < elements.count &&

comparator(elements[rightChild].1, elements[candidate].1) {

candidate = rightChild

}

if candidate == parent {

return

}

elements.swapAt(parent, candidate)

parent = candidate

}

六、性能分析1. 时间复杂度树的BFS：O(n)，n为节点数图的BFS：O(V + E)，V为顶点数，E为边数带权BFS：O((V + E) * log V)2. 空间复杂度队列存储：O(w)，w为最宽层的节点数访问标记：O(V)，V为顶点数双向BFS：O(2^(d/2))，d为最短路径长度七、实战技巧1. 写BFS的步骤创建队列和访问标记集合将起点加入队列循环处理队列中的节点记录层次信息（如果需要）2. 调试技巧打印队列状态可视化搜索过程使用小规模测试用例3. 代码模板 1

// BFS代码模板

func bfs(_ start: State) -> Result {

// 1. 初始化数据结构

var queue: [State] = [start]

var visited = Set()

var level = 0

// 2. 标记起点

visited.insert(start)

// 3. BFS主循环

while !queue.isEmpty {

let size = queue.count

// 处理当前层

for _ in 0..

let current = queue.removeFirst()

// 检查是否到达目标

if isTarget(current) {

return buildResult(current, level)

}

// 生成下一层状态

for next in getNextStates(current) {

if !visited.contains(next) {

queue.append(next)

visited.insert(next)

}

level += 1

}

return defaultResult

}

八、总结1. BFS的适用场景最短路径问题层序遍历连通性问题状态转换问题2. BFS的优缺点优点：

保证找到最短路径适合处理层次性问题不会栈溢出缺点：

空间消耗大不适合深度优先的场景实现相对复杂3. 实践建议选择合适的数据结构注意边界条件处理考虑优化方案处理好访问标记九、练习题推荐LeetCode 经典BFS题目：#102 二叉树的层序遍历#127 单词接龙#200 岛屿数量#207 课程表#994 腐烂的橘子进阶练习：#126 单词接龙 II#317 离建筑物最近的距离#815 公交路线#1293 网格中的最短路径

广度优先搜索(BFS)详解：从入门到精通

你可能也喜欢

衣服上沾了口红怎么去掉如何防止口红沾到衣服上

LOL英雄联盟手游扇子妈怎么样天启者卡尔玛技能介绍

2025最新!问卷调查赚钱平台推荐(附详细操作指南）

推荐21部关于蛇的电影，这种生物看着就可怕

PPT无法打开超链接

极尽奢华的“产品介绍”，嘎子哥卖的手机到底值多少钱？

🎨 友情链接

广度优先搜索(BFS)详解：从入门到精通

你可能也喜欢

衣服上沾了口红怎么去掉 如何防止口红沾到衣服上

LOL英雄联盟手游扇子妈怎么样 天启者卡尔玛技能介绍

2025最新!问卷调查赚钱平台推荐(附详细操作指南）​

推荐21部关于蛇的电影，这种生物看着就可怕

PPT无法打开超链接

极尽奢华的“产品介绍”，嘎子哥卖的手机到底值多少钱？

🎨 友情链接

衣服上沾了口红怎么去掉如何防止口红沾到衣服上

LOL英雄联盟手游扇子妈怎么样天启者卡尔玛技能介绍

2025最新!问卷调查赚钱平台推荐(附详细操作指南）