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

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 = number of columns下面的邻居将始终是X列(。

如果使用节点的2D说明，则更容易看到。但是，在1D和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，主要是因为我喜欢它。： - (