Самый эффективный способ посетить узлы DAG в порядке

Question

У меня есть большой (более 100 000 узлов) направленный ациклический граф (DAG), и я хотел бы запустить функцию типа «посетитель» на каждом узле по порядку, где порядок определяется стрелками на графике.то есть все родители узла гарантированно будут посещены раньше самого узла.

Если два узла не ссылаются друг на друга прямо или косвенно, то мне все равно, в каком порядке они посещаются.

Какой самый эффективный алгоритм для этого?

Answer 1

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

Сложность такого алгоритма O (| V | + | E |), что довольно хорошо. Вы хотите пересечь все узлы, поэтому, если вы хотите более быстрый алгоритм, чем этот, вам придется решать его, даже не глядя на все ребра, что было бы опасно, потому что один единственный ребро может нарушить порядок полностью.

Answer 2

Как уже упоминалось в других ответах, эту проблему можно решить с помощью Топологическая сортировка .

Очень простой алгоритм для этого (не самый эффективный):

Keep an array (or map) indegree[] where indegree[node]=number of incoming edges of node

while there is at least one node n with indegree[n]=0:
   for each node n in nodes where indegree[n]>0:
      visit(n)
      indegree[n]=-1 # mark n as visited
      for each node x adjacent to n:
          indegree[x]=indegree[x]-1 # its parent has been visited, so one less edge coming into it

Answer 3

Здесь есть несколько ответов: Хороший алгоритм обхода графа

и здесь: http://en.wikipedia.org/wiki/Topological_sorting

В общем, после посещения узла вы должны посетить его связанныйузлы, но только узлы, которые еще не посещены.Чтобы отслеживать посещенные узлы, вам нужно сохранить идентификаторы узлов в наборе (или карте), или вы можете пометить узел как посещенный (каким-либо образом).

Если вы заботитесь о топологическом порядке, вы должны сначала получить коллекцию всех непроходных ссылок («оставшихся ссылок») на узел, отсортированных по идентификатору ссылочного узла (обычно:карта (идентификатор узла -> количество ссылок)).Если у вас этого нет, вам может потребоваться построить его, используя подход, аналогичный описанному выше.Затем начните с посещения узла, у которого количество оставшихся входящих ссылок равно нулю.Для каждой ссылки с этого узла уменьшите количество оставшихся ссылок для каждого связанного узла, добавив связанный узел к набору посещаемых узлов (или просто посещающих узел), если счет достигает нуля.

Answer 4

Вы можете пройти DAG в O (N) (без всякой сортировки), просто запустив ваши dfs с каждого узла с нулевой степенью неопределенности, потому что они будут действительной «отправной точкой». Это будет работать, потому что граф не имеет циклов, эти узлы с нулевой степенью должны существовать и должны пересекать весь граф.