我正在研究寻路问题。我有一个均匀分布的节点的二维网格。我需要一种算法来为每个节点找到所有 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)，我想有更好的方法来解决它。
任何帮助都会很棒!
最佳答案
一个简单的选择是将节点本身存储在由节点的 x 和 y 坐标索引的二维数组中。这样，您只需索引数组并查看其中的内容，就可以随机访问存储在位置 (x, y) 的节点。
或者，如果您的节点稀疏，您可以考虑将节点存储在以 (x, y) 位置为键的哈希表中。这也为 O(1) 随机访问给定位置的节点提供了条件，并且通过简单的双 for 循环，您可以列出所有八个邻居。
希望这对您有所帮助!
关于algorithm - 在图连接算法中寻找邻居节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9090361/