python - 更优雅的图形实现解决方案？

Question

我目前正在尝试制作一个程序，该程序将使用图形数据结构，以网格的形式用于寻路算法。我唯一的问题是，我将计划制作一个 20x20 网格，而 4x4 网格已经占用了大量空间。

graph = {'A': ['B', 'E'],
     'B': ['A', 'C', 'F'],
     'C': ['B', 'D', 'G'],
     'D': ['C', 'H'],
     'E': ['A', 'F', 'I'],
     'F': ['B', 'E', 'J', 'G'],
     'G': ['C', 'F', 'K', 'H'],
     'H': ['D', 'G', 'L'],
     'I': ['E', 'J', 'M'],
     'J': ['F', 'I', 'K', 'N'],
     'K': ['L', 'G', 'O', 'L'],
     'L': ['H', 'K', 'P'],
     'M': ['I', 'N'],
     'N': ['J', 'M', 'O'],
     'O': ['K', 'N', 'P'],
     'P': ['L', 'O']}

是否有更优雅的解决方案来创建我缺少的图表？

Answer 1

只要您知道网格将是矩形，相邻元素之间就始终具有相同的相对距离(即上面的相邻元素始终位于当前元素之前的X = 列数下面的列表和邻居将始终位于之后的 X 列)。

如果使用节点的 2D 描述，则更容易看到。然而，一维和二维描述之间的转换是一项简单的任务(使用divmod)。一个有点复杂的例子(允许比你要求的多一点)是:

from functools import partial

# Get node order from coordinates
def orderYX(y, x, Y, X):
    return y*X + x

# Get coordinates from node order
def coordinatesYX(num, Y, X):
    return divmod(num, X)

# Get the coordinates of the neigbors, based on current coordinates
def get_neighborsYX(y, x, Y, X):
    neighbors = [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]
    # Also filter out neighbors outside the grid
    return [(y, x) for y, x in neighbors if (0 <= y < Y) and (0 <= x < X)]

# Special function to translate a node number to a name
# (To be able to print the graph with letters as names)
def get_name(num):
    name = []
    base = ord('A')
    Z = ord('Z') - base
    # If the number of nodes is larger than Z (25)
    # multiple letters must be used for the name
    while num > Z:
        res, rem = divmod(num, Z+1)
        num = res-1
        name.append(chr(rem + base))
    name.append(chr(num + base))
    name.reverse()
    return "".join(name)

Y = 20 # Number of rows
X = 20 # Number of columns

# Partially apply the functions, to not have to pass Y and X repeatedly
order = partial(orderYX, Y=Y, X=X)
coordinates = partial(coordinatesYX, Y=Y, X=X)
get_neighbors = partial(get_neighborsYX, Y=Y, X=X)

# Generate the graph (with named nodes)
# This may not be necessary, since the neighbors can be found when needed.
graph = {}
for num in range(Y*X):
    coord = coordinates(num)
    neighbors_coord = get_neighbors(*coord)
    neighbors = [order(y, x) for y, x in neighbors_coord]
    graph[get_name(num)] = [get_name(neighbor) for neighbor in neighbors]

在此示例中，我还使用了 functools 模块中的 partial，主要是因为我喜欢它。 :-)