我对上一篇Stack Overflow帖子@Knight'；有一个问题；棋盘上的s最短路径
我理解关于"好吧，这是一个图形问题，它的稀疏矩阵是这样的"的回答：
(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位。当然它是稀疏的，但它也很小，所以如果它存在的话（指针与单个比特相比相当大），浪费也会很小。
当位向量稀疏时，从位向量中提取索引列表也特别容易，但您甚至不需要-您可以让前面是一个位向量队列，而"已访问"集可以是单个位向量。
edit：好吧，如果你使用这个技巧，实际上你可能仍然需要它，但它仍然只需要一些快速操作，如位扫描和x &= x -1。