广度优先算法

Breadth First Search，一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。

广度优先遍历的序列不唯一。相邻节点的遍历顺序允许被任意打乱。

测试图的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph1:
    A
   / \
  B   C
 / \   \
D   E   F
     \
      F

graph2:
	0
   / \
  1   3
 / \ / \
2   4   6
 \ / \ /
  5   7
   \ /
	8

实践

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from collections import deque

def bfs(graph, start):
    # 初始化一个集合，用于存储已经访问过的节点
    # 集合的特点是查找操作非常快，有助于判断节点是否已经访问过
    visited = set()  
    
    # 初始化队列，将起始节点加入队列中
    # 队列用于存储待访问的节点，按照先进先出的顺序处理
    queue = deque([start])  
    
    # 初始化一个列表，用于记录节点的遍历顺序
    # 最终返回此列表以表示 BFS 的结果
    traversal_order = []  
    
    # 开始 BFS 循环，当队列非空时继续
    while queue:
        # 从队列左侧弹出一个节点，即最早加入的节点
        node = queue.popleft()  
        
        # 如果当前节点尚未访问
        if node not in visited:
            # 将当前节点标记为已访问，加入到 visited 集合
            visited.add(node)  
            
            # 将当前节点记录到遍历顺序中
            traversal_order.append(node)  
            
            # 遍历当前节点的邻居节点列表
            # 对于每个邻居，只有当其未被访问过时，才将其加入队列
            # 使用生成器表达式高效筛选未访问的邻居
            queue.extend(
                neighbor for neighbor in graph[node] if neighbor not in visited
            )
    
    # 当队列为空时，循环结束，返回记录的遍历顺序
    return traversal_order


# 示例图的表示
search.test(bfs)

流程图

graph TD
    Start["Start: Initialize visited, queue, and traversal_order"] --> A["Add the starting node to queue"]
    A --> B["Check if queue is empty"]
    B -->|Queue is not empty| C["Dequeue the first node from queue"]
    C --> D["Check if the node is in visited"]
    D -->|Not visited| E["Add the node to visited"]
    E --> F["Append the node to traversal_order"]
    F --> G["Get neighbors of the node from graph[node]"]
    G --> H["Filter neighbors: Keep only unvisited neighbors"]
    H --> I["Add unvisited neighbors to queue"]
    I --> B
    D -->|Already visited| B
    B -->|Queue is empty| End["End: Return traversal_order"]

    %% Subprocess for processing neighbors
    subgraph Loop["Neighbor Processing Logic"]
        G --> J["Iterate through each neighbor in graph[node]"]
        J --> K["Check if neighbor is in visited"]
        K -->|Not visited| L["Keep the neighbor"]
        K -->|Already visited| M["Skip the neighbor"]
        L --> H
        M --> J
end