нужен алгоритм графа, похожий на 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

Если вы ищете 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

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

100, 101, 200, 201, 202

Answer 3

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

Стандартный способ получить топсорт - это сделать стандартную 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, чтобы исправить это.