查找图中N个节点以外的所有节点

Question

你和几个朋友在玩棋盘游戏。游戏的棋盘被布置成一个有很多循环的大的相互关联的图形。每个玩家从棋盘上不同的位置开始。当轮到你的时候，你可以在一到六面的骰子之间滚动任何东西(换句话说，任何1-36的骰子)。如何确定您可能从当前位置转到的每个空间？(例如:我掷了一个13，在离我13个空间的地方找到了所有的位置。)你只能向前移动，但你可以绕圈遍历一个比你的滚动更少的净总数。

如果这是你的图形，你从左上角开始，然后你滚动了一个6，那么你可以移动的地方是向下，右，右，上，左，左。然而，你不能移动右，左，右，左，右，左。

  o---o---o---o---o
  |       |   |
  o---o---o---o

有比深度优先搜索更好的算法吗？

Answer 1

您根本不需要实际遍历图表来解决这个问题。

该图可由其邻接矩阵编码:一个矩阵M，如果存在从节点i到节点j的边缘，则为M(i,j) = 1；如果没有边缘，则为M(i,j) = 0。

这个矩阵具有一个超冷的性质:对于任何非负整数k，M**k ( M的k-th幂，即M乘以k乘以)使得(M**k)(i,j) =从i到j的不同步数。

如果是(M**k)(i,j) > 0，则可以从节点j准确地从k移动到节点k。请注意，如果您确保每个节点都有自己的边缘，即如果M的对角线上充满了1s，那么在精确的k移动中可以到达的节点与最多可以在k移动中到达的节点相同。

另见：https://en.wikipedia.org/wiki/Adjacency_matrix#Matrix_powers

在大多数编程语言中，有一些库可以非常有效地处理矩阵和矩阵操作，因此，将矩阵取为幂比逐个访问图的节点要快得多。

另一方面，如果图很大，而k很小，而且您只对一个起始节点感兴趣，那么计算M**k的效率可能低于图遍历，因为M**k回答了图的每个节点的问题，而不仅仅是您感兴趣的起始节点。

但是，如果您对所有可能的起始节点感兴趣，或者如果k接近图的直径，那么计算M**k最有可能是最好的选择。

Answer 2

由于限制您可以绕圈，但不能直接返回您来自的节点，这实际上是一个非常有趣的问题。特别是，您既不能只做BFS或DFS，并且在较少的移动中修剪已经访问过的所有节点，聪明的矩阵乘法也不能工作。

相反，您可以使用DFS的一个变体，但是您必须记录到达一个节点的移动次数，以及访问该节点时来自哪个节点，并且只有在您之前看到过这种精确组合的情况下，才需要修剪分支--而不是如果您在较少的移动中到达该节点，或者来自另一个节点。

Python和示例中的基本实现：

def search(graph, start, moves):
    stack = [(start, 0, -1)]
    distance = {i: set() for i in range(moves+1)}
    while stack:
        node, dist, prev = stack.pop()
        if (node, prev) in distance[dist]: continue
        distance[dist].add((node, prev))
        if dist < moves:
            stack.extend((x, dist+1, node) for x in graph[node] if x != prev)
    return {node for (node, prev) in distance[moves]}

# 1---2---3---4---5
# |       |   |
# 6---7---8---9
g = {1: [2,6], 2: [1,3], 3: [2,4,8], 4: [3,5,9], 5: [4],
     6: [1,7], 7: [6,8], 8: [3,7,9], 9: [4,8]}
print(search(g, 1, 13))
# {8, 2, 4, 6}