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], ... }

这将用于具有到节点2的边的节点1，节点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)}}