奈特最短路径图的数据结构与算法

Question

我对之前的一个堆栈溢出帖子@ Knight's Shortest Path on Chessboard有一个问题

我理解关于‘好的，这是一个图形问题，它的稀疏矩阵是这样的’的回答：

(a1,b3)=1,
(a1,c2)=1,
  .....

它描述了现有的边。然而，我仍然不知道这个图的数据结构应该是什么样子(它是一个邻接矩阵吗？上面所说的“稀疏矩阵”，或者其他什么？)，以便它可以很容易地被Dijkstra算法使用。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。

从算法描述上看，如果图的数据结构是一组顶点，并且有相邻顶点的信息，这看起来很方便。但是我们如何做到这一点呢？

我如何写出这个图的样本数据结构？我正在寻求对它如何方便地与Dijkstra算法相联系的理解。

Answer 1

图是非常稀疏的(64个顶点，每个顶点最多有8条边)，因此邻接矩阵是一个浪费的IMO。

一种更好的结构是adjacency list

v1->v2,v3,v4,v5
v2->v1,...
...

这个想法实际上是保存一个Set<Vertex>，并且让Vertex类型有一个字段：List<Vertex> neighbors，它将包含顶点的所有相邻顶点。

在这种情况下，不需要一些额外的权重信息-因为图是未加权的。

还有-Dijkstra的算法在这里是冗余的。同样，该图是未加权的-因此找到最短路径的更简单(易于编程和理解)和更快(运行时)的算法是未加权图的。

Answer 2

由于只有64个瓦片，您可以方便地将邻接矩阵放入一个包含64个整数的数组中，每个整数64位。当然它是稀疏的，但它也很小，所以浪费，如果它存在的话(指针与单个位相比是相当大的)，也会很小。

当位向量稀疏时，从位向量中提取索引列表也特别容易，但您甚至不需要这样做-您可以让前面是位向量的队列，而“已访问”集可以是单个位向量。

编辑:好的，实际上如果你使用这个技巧，你可能仍然需要它，但是它仍然只需要几个快速的操作，比如位扫描和x &= x -1。