图连接算法中查找邻居节点
我正在研究路径查找问题。我有一个由均匀分布的节点组成的二维网格。我需要一种算法来查找每个节点的所有 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) 并且我想有更好的方法来解决它。
任何帮助都会很棒！
I am working on a path finding problem. I have a 2D grid of evenly spaced nodes. I need an algorithm to find all 8 neighbors (if they exist) for each node so I can find all neighbor connections.
The only way I know how to do it would be something like this:
for each node
for every other node
check position to find if it is neighboring if so add it to the nodes connection list
My concern is that this would be pretty inefficient O(n^2) and I imagine there is a better way of solving it.
Any help would be great!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
一种简单的选择是将节点本身存储在由节点的 x 和 y 坐标索引的二维数组中。这样，您只需在数组中建立索引并查看其中的内容，即可以 O(1) 的方式随机访问存储在位置 (x, y) 的节点。
或者，如果您的节点稀疏，您可以考虑将节点存储在以 (x, y) 位置为键的哈希表中。这还提供了对给定位置节点的 O(1) 随机访问，并且通过简单的双 for 循环，您可以列出所有八个邻居。
希望这有帮助！
One simple option would be to store the nodes themselves in a two-dimensional array indexed by the x and y coordinates of the nodes. That way, you'd have O(1) random access to the node stored at position (x, y) by just indexing into the array and looking at what's there.
Alternatively, if your nodes are sparse, you could consider storing the nodes in a hash table keyed by the (x, y) location. This also gives O(1) random access to nodes at given positions, and with a simple double for-loop you could list off all eight neighbors.
Hope this helps!