广度优先搜索

#广度优先搜索

• 图简介
• 广度优先搜索
• 查找最短路径
• 队列
• Python 实现

#图简介

图由节点（node/vertex）和边（edge）组成，用于模拟各种连接关系——人际关系网、公路网、神经元网络等。

        A ──── B
        |      |
        C ──── D ──── E

一个节点直接相连的节点称为邻居。有向图的边有方向（A→B 不意味着 B→A），无向图的边没有方向。

#广度优先搜索

广度优先搜索（BFS）从起点出发，由近及远地逐层搜索——先检查一度关系（直接邻居），再检查二度关系（邻居的邻居），以此类推。

它可以回答两类问题：

• 从 A 出发，有前往 B 的路径吗？
• 从 A 出发，前往 B 的最短路径是什么？

        A
      / | \
     B  C  D        ← 一度关系（先检查）
    /|  |  |\
   E F  H  I J      ← 二度关系（再检查）
   |        |
   K   G    L       ← 三度关系（最后检查）

搜索顺序: A → B → C → D → E → F → H → I → J → K → ... → G

#查找最短路径

一度关系胜过二度关系，所以应先在一度关系中搜索，没有才在二度关系中搜索。BFS 天然做到了这一点——找到的就是最短的路径。

关键：必须按添加顺序检查，先加入名单的先检查。实现这种顺序的数据结构是队列。

#队列

队列是先进先出（FIFO）的数据结构：

• 入队：添加到队尾
• 出队：从队首取出

#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"] = []
graph["jonny"] = []

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []                        # 记录已检查的人
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:       # 只检查没检查过的
            if person_is_seller(person):
                print(person + " is a mango seller!")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False

def person_is_seller(name):
    return name[-1] == 'm'    # 示例：名字以 m 结尾的是芒果销售商

search("you")

必须记录已检查的人，否则可能陷入无限循环（图中有环时）。

运行时间：O(V + E)，V 为顶点数，E 为边数。

#小结

• BFS 从起点由近及远逐层搜索，用于非加权图的最短路径问题
• 用队列管理候补节点，保证先加入的先检查
• 必须记录已检查的节点，避免无限循环
• 运行时间 O(V + E)