Как найти соседей графа effiiciently

Question

У меня есть программа, которые создают графики, как показано ниже

Алгоритм начинается с зеленого цвета узла и пересекает график. Предположим, что узел (узел типа Linked list type с 4 ссылками Left, Right, Up и Down) был добавлен в график, изображенный красной точкой на изображении. Чтобы интегрировать вновь созданный узел с его соседями, мне нужно найти четыре объекта и связать их, чтобы связь между графами сохранилась.

Ниже то, что мне нужно уточнить

1. Предположит, что все желтые цветные узлы являются недействительными и не держать структуру других данных для отображения узлов, что является наиболее эффективным способом, чтобы найти существование соседей вновь созданного узла. Я знаю основные алгоритмы поиска графа, такие как алгоритмы DFS, BFS и кратчайшие пути, но я не думаю, что любой из них достаточно эффективен, потому что граф может иметь около 10000 узлов и выполнять алгоритмы поиска графа (начиная с зеленого узла), чтобы найти соседи, когда новый узел добавлен, кажется мне дорогостоящим.
2. Если поиск по графу не позволяет избежать того, что является лучшей альтернативной структурой. Я думал о большом многомерном массиве. Однако у этого есть потеря памяти, а также проблема отсутствия отрицательных индексов. Так как график в изображении может расти в любом направлении. Мое решение заключается в том, чтобы написать отдельный класс, который состоит из структуры данных на основе массива для отображения отрицательных индексов. Однако, прежде чем принимать этот вариант, я хотел бы знать, смогу ли я решить проблему без разрешения новой структуры и сэкономить много доработок.

Благодарим вас за отзыв и прочтите этот вопрос.

Answer 1

Я не уверен, правильно ли я вас понимаю. Вы хотите

• Проверьте, что есть путь от (0,0) до (x1, y1)

или

• Проверьте, если какой-либо из соседей (x1 , y1) находятся на графике? (даже если нет пути от (0,0) к любому из этих соседей).

Я предполагаю, что вы ищете путь (иначе вы не будете использовать связанный список), что означает, что вы не можете хранить точки, у которых нет пути к (0,0).

Кроме того, вы упомянули, что не хотите использовать какую-либо другую структуру данных рядом с/вместо вашего 2D-связанного списка.

Вы не можете избежать поиска по полному графику. BFS и DFS - классические алгоритмы. Я не думаю, что вы заботитесь о кратчайшем пути - любой путь.

Другие подходы, которые вы можете рассмотреть, это A * (простое объяснение here) или один из его вариантов (смотрите here).

Альтернативной структурой данных будет набор узлов (каждый узел представляет собой пару < x, y>, конечно). Вы можете легко запустить 4 проверки, чтобы убедиться, что кто-либо из его соседей уже находится в наборе. Это займет O (n) пространство и O (logn) время для проверки и добавления. Если ваш язык программирования не поддерживает пары как узлы набора, вы можете использовать одно целое (x * (Ymax + 1) + Y).

Answer 2

Вы можете использовать пространственный индекс, например, квадровое дерево или r-дерево.

Answer 3

Ваша структура данных может быть создана для работы, но, вероятно, неэффективно. И это будет много работы.

С вашей текущей структурой данных вы можете использовать поиск A * (см. https://en.wikipedia.org/wiki/A * _search_algorithm для базового описания), чтобы найти путь к точке, который обязательно находит сосед. Тогда притворись, что у тебя есть маленький парень в этот момент, положил свою правую руку на стену, а затем попросил его найти по часовой стрелке вокруг точки. Когда он вернется, он найдет все остальное.

Что я могу сказать, найдя его по часовой стрелке? Например, предположим, что вы уходите от соседа, чтобы понять его. Тогда ваш парень должен столкнуться с первым из Right, Up и Left, у которого есть сосед. Если он сможет идти вправо, он будет, то он попробует направления вниз, вправо, вверх и влево. (Представьте себе, чтобы попытаться пройти через лабиринт самостоятельно правой рукой на стене.)

Этот путь - это безумие.

Вот две альтернативные структуры данных, с которыми намного легче работать.

Вы можете использовать квадрант. См. http://en.wikipedia.org/wiki/Quadtree для описания. При этом вставка узла логарифмична по времени. Поиск соседей также логарифмичен. И вы используете пространство для данных, которые у вас есть, поэтому даже если ваш график очень распространен, это эффективная память.

Альтернативно вы можете создать класс для типа массива, который принимает как положительные, так и отрицательные индексы.Затем тот, который строится на том, чтобы быть 2-м классом, который принимает как положительные, так и отрицательные индексы. Под капотом этот класс будет реализован как обычный массив и смещение. Итак, массив, который может начинаться с некоторого числа, положительного или отрицательного. Если вы попытаетесь вставить часть данных, которая находится перед смещением, вы создадите новое смещение, которое ниже этой части, фиксированной частью длины массива, создайте новый массив и скопируйте данные из старого в новый. Теперь вставка/поиск соседей обычно O(1), но это может быть очень расточительно для памяти.