优化图以进行路径查找和获取特定坐标的节点

Question

我正在创建一个图的类，用字典来表示这个图。这个图的类用来在一个大的二维网格矩阵上寻找路径。节点被存储为字典的键，而邻居节点则存储为值。

这样做可以快速找到路径，但我还需要根据节点的 x 和 y 坐标从字典中提取特定的节点。

class Node(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Graph(dict):
    def get_node_at(self, x, y):
        for node in self:
            if node.x == x and node.y == y:
                return node

    def set_neighbours(self):
        pass

graph = Graph()

# build a 2d matrix of nodes
for x in range(10):
    for y in range(10):
        graph[Node(x,y)] = []

# set the neighbour nodes for each node
graph.set_neighbours()
mynode = graph.get_node_at(6,6) # will later be executed quite often

有没有办法优化这个图的类，让 get_node_at 方法在处理大网格时表现得更好？

Answer 1

给Graph添加一个索引，格式是{(x,y):node}。这意味着我们需要实现一个叫__setitem__的方法，用来把Node添加到这个索引里。如果在同样的位置已经有了另一个Node，那么就要把它删除。同时，我们还需要一个__delitem__的方法，用来从索引中移除Node。这样的话，调用get_node_at(self, x, y)时，就可以简单地用return self.index[(x,y)]来获取对应的节点。