Как эффективно находить соседей графа

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

Структура созданного графа

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

Вот что мне нужно уточнить

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

Спасибо за любой отзыв и чтение этого вопроса.


search graph algorithm path-finding graph-algorithm
person Synex    schedule 29.06.2013    source источник

Ответы (3)


arrow_upward
1
arrow_downward

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

  • Убедитесь, что существует путь от (0,0) до (x1,y1)

or

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

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

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

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

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

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

person Lior Kogan    schedule 29.06.2013

arrow_upward
0
arrow_downward

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

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

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

На этом пути лежит безумие.

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

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

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

person btilly    schedule 29.06.2013
comment
Мне тоже нравится ваш ответ... но, к сожалению, я смог выбрать только один как лучший.... - person Synex; 02.07.2013

arrow_upward
0
arrow_downward

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

person Gigamegs    schedule 29.06.2013