【学习】《算法图解》第六章学习笔记：广度优先搜索

前言

《算法图解》第六章为我们介绍了一种基础且强大的图搜索算法——**广度优先搜索 (Breadth-First Search, BFS)**。这种算法能够系统地探索图中的节点，常用于解决两类核心问题：一是判断从一个节点到另一个节点是否存在路径；二是在无权图中找到两个节点之间的最短路径。本笔记将深入探讨图的基本概念、BFS 的工作原理、其实现方式以及相关的性能分析。

一、图（Graph）简介

在讨论 BFS 之前，我们需要理解什么是图。

（一）什么是图

图是一种由节点 (Nodes 或 Vertices) 和连接这些节点的边 (Edges) 组成的数据结构。图用于表示各种实体之间的关系。

节点：代表图中的事物或点。例如，在社交网络中，节点可以代表人；在地图中，节点可以代表城市。
边：代表节点之间的连接或关系。例如，在社交网络中，边可以表示朋友关系；在地图中，边可以表示城市间的道路。

（二）有向图与无向图

**有向图 (Directed Graph)**：图中的边具有方向性。如果存在一条从节点 A 指向节点 B 的边，意味着关系是从 A 到 B，但不一定是从 B 到 A。例如，Twitter 的关注关系是有向的。
```
    graph LR
    A --|> B; 
    B --|> C;
    A --|> C;
end
```
**无向图 (Undirected Graph)**：图中的边没有方向，关系是双向的。如果节点 A 和节点 B 之间有边相连，则可以从 A 到 B，也可以从 B 到 A。例如，Facebook 的好友关系是无向的。
```
    graph TD
    A --- B;
    B --- C;
    A --- C;
end
```

（三）邻居 (Neighbors)

一个节点的邻居是指所有与该节点直接通过一条边相连的节点。

二、广度优先搜索 (BFS) 概述

广度优先搜索 (BFS) 是一种用于遍历或搜索树或图数据结构的算法。它从图的某个起始节点（源节点）开始，探索其所有邻近节点，然后再逐层向外探索这些邻近节点的邻近节点，依此类推。

（一）基本思想

BFS 算法的核心思想是”逐层扩展”。

首先访问起始节点。
然后访问所有与起始节点直接相连的（一度关系）邻居节点。
接着访问与一度关系节点相连的、且尚未被访问过的（二度关系）节点。
这个过程持续进行，直到图中所有可达节点都被访问过，或者找到了目标节点。

这种探索方式确保了在无权图中，BFS 找到的从起始节点到任何其他节点的路径都是最短的（以边的数量衡量）。

（二）BFS 能解决的问题

路径存在性：从节点 A 出发，是否存在到达节点 B 的路径？
最短路径（无权图）：从节点 A 出发，到达节点 B 的最短路径是什么（即经过最少的边）？

例如，在社交网络中找到与你关系最近（中间隔着最少朋友）的某个特定职业的人，或者在棋盘游戏中计算最少步数到达某个状态。

三、队列 (Queue) 在 BFS 中的作用

为了实现 BFS 的”逐层扩展”特性，即按照节点被发现的顺序来检查它们，我们需要一种特定的数据结构来管理待访问的节点列表。这个数据结构就是**队列 (Queue)**。

（一）为什么是队列

**先进先出 (First-In, First-Out, FIFO)**：队列的特性是先进入队列的元素会先被取出。这与 BFS 的需求完全一致：我们希望先处理（检查其邻居）最早被加入到待访问列表中的节点。
当访问一个节点时，我们会将其所有未访问过的邻居加入队列的末尾。然后，从队列的头部取出一个节点进行处理。这样就保证了我们是按照”层级”或”距离起始点的远近”来逐步探索的。

（二）与栈 (Stack) 的对比

栈 (Stack) 是后进先出 (Last-In, First-Out, LIFO) 的数据结构。如果使用栈来管理待访问节点，则会导致算法优先探索最新发现的路径，从而实现**深度优先搜索 (Depth-First Search, DFS)**，DFS 会沿着一条路径尽可能深地探索，直到无法继续才回溯。

因此，要实现广度优先搜索并找到最短路径，必须使用队列。

四、实现图的数据结构

在代码中表示图，常用的一种方法是使用散列表（在 Python 中是字典）。字典的键是图中的节点，对应的值是一个列表，该列表包含了该节点的所有邻居。

（一）Python 字典表示图示例

# 使用字典来表示图的关系
graph = {}
graph["you"] = ["alice", "bob", "claire"] # "you" 是一个节点，它的邻居是 alice, bob, claire
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = [] # anuj 没有邻居
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

# 这个图可以想象成一个社交网络
# you -- alice
# |      |
# bob -- peggy
# |      
# anuj   
# |      
# claire -- thom
#        | 
#        jonny

五、实现广度优先搜索算法

下面是实现 BFS 算法的通用步骤，以《算法图解》中寻找芒果销售商的例子为背景。

（一）算法步骤

初始化队列：创建一个空队列。将起始节点（例如，”you”）的所有直接邻居（一度关系）加入队列。这些是第一批需要检查的人。
创建已搜索集合：创建一个集合（或列表） searched，用于存放已经检查过（处理过其邻居）的节点。这非常重要，可以避免重复检查同一个节点，更重要的是防止在有环路的图中陷入无限循环。
循环处理队列：当队列不为空时，执行以下操作：
a. 出队：从队列的前端取出一个节点（person）。
b. 检查是否已处理：如果该节点 person 已经在 searched 集合中，则跳过，处理下一个。
c. 目标判断：检查节点 person 是否满足目标条件（例如，person_is_seller(person) 是否为 True）。
* 如果满足条件，则表示找到了目标，搜索成功。可以打印信息并返回 True（或路径）。
* 如果不满足条件，则将该节点 person 的所有邻居加入搜索队列的末尾。然后，将 person 加入 searched 集合，表示该节点已被处理。
搜索失败：如果队列变为空，仍然没有找到满足条件的节点，则表示搜索失败，目标不存在（或从起点不可达）。返回 False。

（二）Python 代码示例

from collections import deque # 导入双端队列，可以高效地在两端添加和删除元素

# 图的表示 (同上节)
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = [] # 假设 thom 是芒果销售商
graph["jonny"] = []

def person_is_seller(name):
    """判断一个人是否是芒果销售商 (书中示例：名字以 'm' 结尾)"""
    return name == "thom" # 修改为 thom 是销售商

def breadth_first_search(start_node):
    search_queue = deque() # 1. 创建搜索队列
    # 将起始节点直接加入队列，在循环开始前处理，或先将其邻居加入
    # 书中的例子是直接将第一层关系加入队列，这里我们调整为先加入起始点本身，然后在循环中处理其邻居
    # 这样更通用，且能处理起始点就是目标的情况
    if start_node not in graph: # 确保起始节点在图中
        print(f"起始节点 {start_node} 不在图中。")
        return False
        
    search_queue.append(start_node) 
    searched = set() # 2. 创建已搜索节点的集合
    
    while search_queue: # 3. 当队列不为空
        person = search_queue.popleft() # a. 从队列头部取出一个节点
        
        if person not in searched: # b. 检查是否已处理过
            print(f"正在检查 {person}...")
            if person_is_seller(person): # c. 目标判断
                print(f"{person} 是一个芒果销售商！")
                return True # 找到目标
            else:
                # 将其所有邻居加入队列末尾 (如果这些邻居存在于图中)
                if person in graph:
                    for neighbor in graph[person]:
                        if neighbor not in searched and neighbor not in search_queue:
                             search_queue.append(neighbor)
                searched.add(person) # 将当前节点标记为已搜索
        # else:
            # print(f"{person} 已经被检查过了或已在队列中，跳过。") # 可选的调试信息
            
    print("队列为空，没有找到芒果销售商。")
    return False # 4. 搜索失败

# 从 "you" 开始搜索
if breadth_first_search("you"):
    print("搜索成功！")
else:
    print("搜索失败，网络中没有芒果销售商。")

# 测试起始点就是目标的情况
# graph["thom_seller"] = [] 
# def is_seller_direct(name):
#    return name == "thom_seller"
# if breadth_first_search("thom_seller"):
#    print("Direct search successful!")
# else:
#    print("Direct search failed.")

代码说明与调整：

上述代码示例中的BFS实现逻辑稍作调整，使其更通用：首先将起始节点放入队列，然后在循环中处理当前节点，再将其未处理的邻居加入队列。
增加了对起始节点是否在图中的检查。
在将邻居加入队列前，也检查了邻居是否已在searched集合或search_queue中，以避免重复添加，尽管searched集合主要防止重复处理。