Есть ли эффективный способ определить, достижим ли конечный узел из другого произвольного узла в направленном ациклическом графе?

Question

Википедия: Направленный ациклический граф

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

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

Есть ли другие алгоритмические оптимизации?

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

Edit:

Это больше, чем просто поиск одного узла, а поиск ВСЕХ узлов, которые являются конечными точками.

Также нет главного списка узлов. У каждого узла есть список его детей и его родителей. (Ну, это не совсем так, но забирать миллионы узлов из БД заранее непомерно дорого и, скорее всего, приведет к исключению OutOfMemory)

Edit2:

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

Answer 1

Есть несколько методов, каждый из которых может быть быстрее в зависимости от вашей структуры, но в общем случае вам нужен обходной путь.

Поиск в глубину вначале проходит через каждый возможный маршрут, отслеживая уже посещенные узлы. Это рекурсивная функция, потому что на каждом узле вы должны разветвляться и пробовать каждый его дочерний узел. Нет более быстрого метода, если вы не знаете, какой способ искать объект, вам просто нужно попробовать каждый путь! Вам определенно нужно следить за тем, где вы уже были, иначе это было бы расточительно. Это должно потребовать порядка количества узлов, чтобы сделать полный обход.

Поиск в ширину аналогичен, но посещает каждого потомка узла, прежде чем "двигаться дальше", и, таким образом, создает слои расстояния от выбранного корня. Это может быть быстрее, если ожидается, что место назначения будет близко к корневому узлу. Это будет медленнее, если ожидается, что он будет проходить весь путь, потому что это заставляет вас пересекать все возможные ребра.

Вы правы в том, что, возможно, ведете список известных корневых узлов, компромисс здесь заключается в том, что вам в основном приходится выполнять поиск всякий раз, когда вы изменяете график. Если вы изменяете график редко, это приемлемо, но если вы изменяете график чаще, чем нужно для создания этой информации, то, конечно, это слишком дорого.

РЕДАКТИРОВАТЬ: Обновление информации. Похоже, что мы на самом деле ищем путь между двумя произвольными узлами, семантика корня / листа продолжает переключаться. DepthFirstSearch (DFS) запускается на одном узле, а затем для каждого непосещенного дочернего элемента выполняется рекурсия. Перерыв, если вы найдете целевой узел. Из-за способа оценки рекурсии, он будет проходить весь путь вниз по «левому» пути, а затем перечислять узлы на этом расстоянии, прежде чем когда-либо попадет на «правильный» путь. Это дорогостоящее и неэффективное время, если целевой узел потенциально является первым дочерним элементом справа. BreadthFirst идет по ступеням, охватывая всех детей, прежде чем двигаться вперед. Поскольку ваш график является тяжелым снизу, как дерево, у обоих будет примерно одинаковое время выполнения.

Когда график тяжелый снизу, вас может заинтересовать обратный обход. Начните с целевого узла и идите вверх, потому что в этом направлении относительно меньше узлов. Пока узлы в целом имеют больше родителей, чем детей, это направление будет намного быстрее. Вы также можете объединить подходы, ступая один вверх и один вниз, затем сравнивая списки узлов и встречаясь где-то посередине. (эта комбинация может показаться самой быстрой, если вы игнорируете, что на каждом шаге выполняется вдвое больше работы).

Однако, так как вы сказали, что ваш график хранится в виде списка списков детей, у вас нет реального способа обхода графика в обратном направлении. Узел не знает, каковы его родители. Это проблема. Чтобы исправить это, вы должны получить узел, чтобы узнать, каковы его родители, добавив эти данные при обновлении графа или создав дубликат всей структуры (которую вы сказали, слишком большой). Потребуется переписать всю структуру, что, вероятно, не может быть и речи, поскольку на данный момент она является большой базой данных. Там много работы. http://en.wikipedia.org/wiki/Graph_(data_structure)

Answer 2

Только цвет (отслеживать) посещенных узлов.

Образец в Python:

def reachable(nodes, edges, start, end):
  color = {}
  for n in nodes:
    color[n] = False
  q = [start]
  while q:
    n = q.pop()
    if color[n]:
      continue
    color[n] = True
    for adj in edges[n]:
      q.append(adj)
  return color[end]

Answer 3

Для вершины x вы хотите вычислить массив битов f (x), каждый бит соответствует корневой вершине Ri, а 1 (соответственно 0) означает, что «x может (соответственно не может) быть достигнут из корневой вершины Ri .

Вы можете разбить график на один «верхний» набор U, содержащий все ваши целевые корни R и такие, что если x в U, то все родители x находятся в U. Например, множество всех вершин на расстоянии <= D ближайший ри. </p>

Держите U не слишком большим и предварительно вычислите f для каждой вершины x из U.

Тогда для вершины запроса y: если y в U, у вас уже есть результат. В противном случае рекурсивно выполните запрос для всех родителей y, кэшируя значение f (x) для каждой посещенной вершины x (например, на карте), поэтому вы не будете вычислять значение дважды. Значение f (y) является побитовым ИЛИ значения его родителей.