нужен графический алгоритм, похожий на DFS

Question

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

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

Редактировать:пример:учитывая график {AB, EB, BC, BD}, пересекаем как:{A, B, E, B, C, D} или уникальный порядок как {A,B, E, C, D}.Обратите внимание, что этот алгоритм, в отличие от BFS или DFS, не требует повторного запуска на новом начальном узле, если все пути первого начального узла исчерпаны.

Answer 1

В DFS вы обычно выбираете вершину для посещения после u на основе ребер, начинающихся с u .Вы хотите выбрать, основываясь сначала на ребрах, заканчивающихся на u.Чтобы сделать это, вы могли бы иметь транспонировать граф info, и попытайтесь сначала получить вершину оттуда.

Это было бы что-то вроде этого:

procedure dfs(vertex u)
  mark u as visited
  for each edge (v, u) //found in transpose graph
    if v not visited
      dfs(v)
  for each edge (u, w)
    if v not visited
      dfs(w)

Answer 2

То, что вы ищете, - это топологическая сортировка.Насколько мне известно, нет простого способа обойти график в его топологически отсортированном порядке без каких-либо предварительных вычислений.

Стандартный способ получить верхнюю сортировку - выполнить стандартную DFS, а затем сохранить посещенные узлы в порядке их времени посещения.Наконец, переверните эти узлы и вуаля, они у вас есть в том порядке, в каком вы хотите.

Псевдокод:

list topsort

procedure dfs(vertex u)
  mark u as visited
  for each edge (u, v)
    if v not visited
      dfs(v)
  add u to the back of topsort

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

Answer 3

Если вы ищете topological sort, вы также можете сделать это, учитывая список смежности (или список ребер (u,v) который вы можете предварительно обработать в O(E) время):

list top_sort( graph in adjacency list )
     parent = new list
     queue = new queue
     for each u in nodes
         parent(u) = number of parents
         if ( parent(u) is 0 ) // nothing points to node i
             queue.enqueue( u )

     while ( queue is not empty )
         u = queue.pop
         add u to visited
         for each edge ( u, v )
             decrement parent(v) // children all have one less parent
             if ( parent(v) is 0 )
                 queue.enqueue( v )

Учитывая adjacency list (или список ребер (u,v)), это O( V + E ), поскольку к каждому краю прикасаются дважды - один раз для увеличения, один раз для уменьшения, в O(1) время каждого.При обычной очереди каждая вершина также будет обработана очередью не более двух раз, что также может быть сделано в O(1) со стандартной очередью.

Обратите внимание, что это отличается от DFS (по крайней мере, простой реализации) тем, что оно обрабатывает леса.

Еще одно интересное замечание заключается в том, что если вы замените queue с помощью priority_queue навязывая какую-то структуру / порядок, вы действительно можете возвращать результаты, отсортированные в определенном порядке.

Например, для канонического графика зависимостей классов (вы можете использовать класс X только в том случае, если вы использовали класс Y):

100:
101: 100
200: 100 101
201: 
202: 201

вы, вероятно, получили бы в результате:

100, 201, 101, 202, 200

но если вы измените его так, чтобы вам всегда хотелось сначала посещать классы с более низкими номерами, вы можете легко изменить его на return:

100, 101, 200, 201, 202