グラフ接続で隣人ノードを見つけるアルゴリズム

Question

私は、問題を見つけることに取り組んでいます。私は均等に間隔を置いたノードの2Dグリッドを持っています。私はすべての隣人の接続を見つけることができるように、各ノードのすべての8つの隣人（存在する場合）を見つけるアルゴリズムが必要です。

私はそれを行う方法を知っている唯一の方法はこのようなものになるだろう：

for each node 
for every other node 
    check position to find if it is neighboring if so add it to the nodes connection list 

私の懸念は、これがO(n^2)かなり非効率的だろうと私はそれを解決する良い方法があると想像ということです。

助けがあれば助かります。

Answer 1

ノードのx座標とy座標でインデックスされた2次元配列にノード自体を格納するのが簡単なオプションです。そうすれば、配列にインデックスを付け、そこにあるものを見るだけで、位置（x、y）に格納されているノードへのO（1）ランダムアクセスができます。

また、ノードが散在している場合、（x、y）の位置をキーにしたハッシュテーブルにノードを格納することを検討できます。これはまた与えられた位置のノードへのO（1）ランダムアクセスを与え、単純な二重forループで8つの隣人すべてをリストすることができます。

希望すると便利です。