チェス盤のKnight'sShortestPathでの以前のStackOverflow投稿の1つに質問があります
'ok、それはグラフの質問であり、そのスパース行列は'：のようなものです。
(a1,b3)=1,
(a1,c2)=1,
.....
既存のエッジを記述します。ただし、ダイクストラのアルゴリズムで簡単に使用できるように、このグラフのデータ構造がどのように見えるか（隣接行列ですか？上記の「スパース行列」と記載されていますか？）はまだわかりません。
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。
アルゴリズムの説明から、グラフのデータ構造が頂点のセットであり、隣接する頂点情報が利用可能である場合は便利に見えます。しかし、どうすればこれを達成できますか？
このグラフのサンプルデータ構造を書き出すにはどうすればよいですか？ダイクストラのアルゴリズムにどのように便利にリンクできるかについての理解を求めています。
グラフは非常にまばらであるため（64の頂点、各頂点には最大8つのエッジがあります）、隣接行列は無駄なIMOです。
このためのより良い構造は隣接リストになります：
v1->v2,v3,v4,v5
v2->v1,...
...
アイデアは確かにを保持することSet<Vertex>であり、Vertex型にはフィールド：List<Vertex> neighbors、があり、これにはすべての頂点の隣接する頂点が含まれます。
この場合、グラフは重み付けされていないため、追加の重み情報は必要ありません。
また、ここではダイクストラのアルゴリズムは冗長です。繰り返しになりますが、グラフは重み付けされていません。したがって、最短パスを見つけるためのより単純な（プログラムして理解する）より高速な（実行時）アルゴリズムは、重み付けされていないグラフのBFSです。
タイルは64個しかないため、隣接行列をそれぞれ64ビットの64個の整数の配列に配置すると便利です。確かにそれはまばらですが、それも小さいので、もしそれが存在するとしても（ポインタはシングルビットに比べてかなり大きいです）、無駄も少なくなります。
ビットベクトルからインデックスのリストを抽出することも、スパースの場合は特に簡単ですが、それも必要ありません。代わりに、フロントをビットベクトルのキューにし、「すでにアクセスした」セットを単一のビットベクトルにすることができます。
編集：わかりました。実際には、そのトリックを使用する場合でも必要になる可能性がありますが、ビットスキャンやなどの高速操作が2、3回必要なだけx &= x -1です。