Python：将xy坐标列表转换为邻接列表

Question

我有一个表示xy坐标的元组列表，例如

coordinates = [(1, 0), (1, 1), (7, 1), (1, 2), (2, 2), (3, 2), (4, 2), (6, 2), (7, 2), (4, 3)]

每个坐标代表该位置图中图形中的一个节点，仅当它们在x或y方向上相邻时才连接到其他节点，不包括对角线。例如，在坐标列表中，应该连接（1,0）和（1,1）元素，因为它们将在y方向上相邻。

我正在为此创建一个邻接列表，因此我可以运行bfs并找到节点之间的最短路径，但是这样做很麻烦，因为我不确定如何将每个元组与其他元组进行比较查找相邻元素的列表。

最终结果看起来像

adjacency_list = {1: [2], 2[1, 3], ... }

这将是节点1的边缘到节点2的边缘，而节点2的边缘到节点1和3的边缘。所有边缘都是未加权和无向的。

Answer 1

adjacency_lists = defaultdict(set)

for ind, coord in enumerate(coordinates):
    for other_coord in coordinates[ind:]:
        if abs((coord[0] - other_coord[0])) <= 1 or abs((coord[1] - other_coord[1])) <= 1:
            adjacency_lists[coord].add(other_coord)
            adjacency_lists[other_coord].add(coord)



>> adjacency_lists

  {(1, 0): {(1, 0), (1, 1), (1, 2), (2, 2), (7, 1)},
(1, 1): {(1, 0),(1, 1),(1, 2),(2, 2),(3, 2),(4, 2),(6, 2),(7, 1),(7, 2)},
(7, 1): {(1, 0),(1, 1),(1, 2),(2, 2),(3, 2),(4, 2),(6, 2),(7, 1),(7, 2)},
(1, 2): {(1, 0),(1, 1),(1, 2),(2, 2),(3, 2),(4, 2),(4, 3),(6, 2),(7, 1),(7, 2)},
(2, 2): {(1, 0),(1, 1),(1, 2),(2, 2),(3, 2),(4, 2),(4, 3),(6, 2),(7, 1),(7, 2)},
(3, 2): {(1, 1),(1, 2),(2, 2),(3, 2),(4, 2),(4, 3),(6, 2),(7, 1),(7, 2)},(4, 2): {(1, 1),(1, 2),(2, 2),(3, 2),(4, 2),(4, 3),(6, 2),(7, 1),(7, 2)},
(6, 2): {(1, 1),(1, 2),(2, 2),(3, 2),(4, 2),(4, 3),(6, 2),(7, 1),(7, 2)},
(7, 2): {(1, 1),(1, 2),(2, 2),(3, 2),(4, 2),(4, 3),(6, 2),(7, 1),(7, 2)},
(4, 3): {(1, 2), (2, 2), (3, 2), (4, 2), (4, 3), (6, 2), (7, 2)}}