我对以前的 Stack Overflow 帖子有一个问题@ Knight's Shortest Path on Chessboard
我理解'好的，这是一个图形问题，它的稀疏矩阵就像'的回复：
(a1,b3)=1,
(a1,c2)=1,
.....
它描述了现有的边缘。但是我仍然不知道这个图的数据结构应该是什么样子（它是一个邻接矩阵吗？上面表示为“稀疏矩阵”，还是其他什么？），以便 Dijkstra 的算法可以很容易地使用它。
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。
从算法描述来看，如果图数据结构是一组顶点，并且有可用的邻居顶点信息，看起来很方便。但我们如何实现这一目标？
如何为该图写出示例数据结构？我正在寻求了解如何将它方便地链接到 Dijkstra 的算法。
该图非常稀疏（64 个顶点，每个顶点最多有 8 条边），因此邻接矩阵是一种浪费的 IMO。
一个更好的结构将是邻接列表：
v1->v2,v3,v4,v5
v2->v1,...
...
这个想法确实是持有一个Set<Vertex>, 并且Vertex类型有一个字段: List<Vertex> neighbors，它将包含所有顶点的相邻顶点。
在这种情况下，不需要一些额外的权重信息——因为该图是未加权的。
另外 - Dijkstra 的算法在这里是多余的。同样，该图是未加权的——因此，一种更简单（易于编程和理解）且更快（运行时）的算法来找到最短路径是未加权图的BFS。
由于只有 64 个图块，因此您可以方便地将邻接矩阵放入一个由 64 个整数组成的数组中，每个整数为 64 位。当然它是稀疏的，但它也很小，所以如果它存在的话（与单个位相比，指针相当大），浪费也会很小。
当位向量稀疏时，从位向量中提取索引列表也特别容易，但您甚至不需要- 您可以让前面成为位向量队列，而“已访问”集可以是单个位向量。
编辑：好的，如果你使用那个技巧，实际上你可能仍然需要它，但它仍然只需要几个快速操作，比如 bitscan 和x &= x -1.