如何从笛卡尔坐标与二维矩阵创建邻接表

需求说明 #

给定由0和1组成的二维矩阵，仅针对值为1的坐标，将每个坐标与北、东、南、西四个方向上同样为1的坐标建立邻接关系，最终生成字典形式的邻接表。

示例矩阵 #

[[1,1,0,0,0],
 [1,1,0,0,0]]

目标邻接表 #

adjacencylist = {
    (0,0): [(0,1), (1,0)],
    (0,1): [(0,0), (1,1)],
    (1,0): [(0,0), (1,1)],
    (1,1): [(1,0), (0,1)]
}

实现步骤 #

1. 筛选有效坐标：遍历矩阵，收集所有值为1的坐标，存入集合以便快速校验。
2. 定义方向偏移：设置四个方向的坐标偏移量：北(-1,0)、东(0,1)、南(1,0)、西(0,-1)。
3. 校验邻接坐标：对每个有效坐标，依次检查四个方向的相邻坐标是否在矩阵范围内，且属于有效坐标集合，符合条件的加入该坐标的邻接列表。
4. 构建邻接表：将所有坐标与对应的邻接列表整理为字典结构。

代码实现（Python） #

def build_adjacency_list(matrix):
    # 收集所有值为1的坐标
    valid_coords = set()
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 1:
                valid_coords.add((i, j))
    
    # 四方向偏移量
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    adjacency_list = {}
    
    for (x, y) in valid_coords:
        neighbors = []
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            # 检查相邻坐标是否合法且为有效坐标
            if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) in valid_coords:
                neighbors.append((nx, ny))
        adjacency_list[(x, y)] = neighbors
    
    return adjacency_list

# 测试示例
sample_matrix = [
    [1,1,0,0,0],
    [1,1,0,0,0]
]

result = build_adjacency_list(sample_matrix)
for coord, neighbors in result.items():
    print(f"{coord}: {neighbors}")

代码说明 #

• 先用集合存储所有1的坐标，避免重复判断矩阵值，提升效率。
• 遍历每个有效坐标时，通过方向偏移量计算相邻坐标，结合矩阵边界校验和集合查找，快速筛选出合法邻接点。
• 最终生成的邻接表与示例目标完全匹配，且可适配任意规模的0-1二维矩阵。

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