algorithm - 在图连接算法中寻找邻居节点

Question

我正在研究寻路问题。我有一个均匀分布的节点的二维网格。我需要一种算法来为每个节点找到所有 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 坐标索引的二维数组中。这样，您只需索引数组并查看其中的内容，就可以随机访问存储在位置 (x, y) 的节点。

或者，如果您的节点稀疏，您可以考虑将节点存储在以 (x, y) 位置为键的哈希表中。这也为 O(1) 随机访问给定位置的节点提供了条件，并且通过简单的双 for 循环，您可以列出所有八个邻居。

希望这对您有所帮助!