CODEWITHSUNDEEP
algorithmdata-structuresgraphnodes
Justin Meiners
Justin Meiners

Reputation: 11113

Finding neighbor nodes in graph connection Algorithm

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!

Upvotes: 1

Views: 2027

Answers (1)

templatetypedef
templatetypedef

Reputation: 372714

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!

Upvotes: 5

Related Questions