如何将坐标对转换为适用于BFS的顶点邻接表格式图结构

你需要生成的是BFS遍历通用的无向图邻接表结构，核心是每条边的两个节点要互相添加为邻居，不能只存单向关联，具体实现逻辑如下：

• 初始化存储结构：可以用字典（兼容非连续编号的顶点）或者定长列表（顶点编号是从0开始的连续整数时性能更好），每个键/索引对应一个顶点，值为该顶点的邻居列表
• 遍历所有边：对每条边的两个顶点u、v，分别将v加入u的邻居列表、将u加入v的邻居列表
• （可选）排序规整：如果需要固定输出顺序、和示例格式对齐，可以对每个顶点的邻居列表做升序排序，避免边的遍历顺序导致邻居排列混乱

Python实现代码 #

# 输入的边连接关系
edges = [[0, 1], [1, 2], [1, 3], [2, 4], [4, 5], [3, 4]]
adj_table = {}

for u, v in edges:
    # 初始化u的邻居列表（如果不存在）
    if u not in adj_table:
        adj_table[u] = []
    adj_table[u].append(v)
    # 无向图反向添加邻居
    if v not in adj_table:
        adj_table[v] = []
    adj_table[v].append(u)

# 按顶点序号升序输出结果
for node in sorted(adj_table.keys()):
    print(f"{node} = {sorted(adj_table[node])}")

运行结果 #

0 = [1]
1 = [0, 2, 3]
2 = [1, 4]
3 = [1, 4]
4 = [2, 3, 5]
5 = [4]

补充说明：如果处理的是有向图，只需要保留单向添加逻辑（即仅把v加入u的邻居列表）即可，常规BFS求解最短路径、连通性问题用的无向图/树结构都需要双向存储邻居，否则遍历会出现断链。

内容的提问来源于stack exchange，提问作者StudentHus