图（Graph）遍历：广度优先搜索（BFS）

# /*
# 图（Graph）遍历：广度优先搜索（BFS）
# --------------------------------------------------------
# 定义：
# 广度优先搜索（Breadth-First Search）从起点出发，
# 先访问所有邻居，再逐层向外扩展。
#
# 特点：
# - 常用于最短路径搜索、连通性判断
# - 使用队列实现，先进先出（FIFO）
# */

from collections import deque

# 图的邻接表表示
class Graph:
    def __init__(self):
        self.adj_list = {}

    def add_vertex(self, v):
        if v not in self.adj_list:
            self.adj_list[v] = []

    def add_edge(self, u, v):
        if u not in self.adj_list:
            self.add_vertex(u)
        if v not in self.adj_list:
            self.add_vertex(v)
        self.adj_list[u].append(v)
        # 无向图可添加 self.adj_list[v].append(u)

    def display(self):
        for vertex, neighbors in self.adj_list.items():
            print(f"{vertex} -> {neighbors}")

# --------------------------------------------------------
# BFS 遍历（队列实现）
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbor in graph.adj_list.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# --------------------------------------------------------
# 示例操作
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")
g.add_edge("D", "E")

print("图的邻接表：")
g.display()

print("\n广度优先搜索 BFS 结果：", end="")
bfs(g, "A")
print()

# --------------------------------------------------------
# 要点总结：
# 1) BFS 逐层访问节点，先访问邻居，再扩展到更远节点；
# 2) 使用队列（FIFO）实现；
# 3) 适合最短路径、连通分量、拓扑排序等问题；
# 4) visited 集合防止重复访问；
# 5) 时间复杂度 O(V + E)，空间复杂度取决于队列大小。
# */

#
# 图的邻接表：
# A -> ['B', 'C']
# B -> ['D']
# C -> ['D']
# D -> ['E']
# E -> []
#
# 广度优先搜索 BFS 结果：A B C D E