Поиск соседних узлов в алгоритме связности графа

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 узлов. Таким образом, у вас будет O (1) произвольный доступ к узлу, хранящемуся в позиции (x, y), просто проиндексировав массив и посмотрев, что там.

В качестве альтернативы, если ваши узлы разрежены, вы можете рассмотреть возможность хранения узлов в хеш-таблице с ключом (x, y). Это также дает O (1) произвольный доступ к узлам в заданных позициях, и с помощью простого двойного цикла for вы можете перечислить все восемь соседей.

Надеюсь, это поможет!