нужен графический алгоритм, похожий на DFS
-
22-09-2019 - |
Вопрос
Мне любопытно, существует ли конкретный алгоритм графа, который пересекает невзвешенный ациклический ориентированный граф, выбирая начальный узел и затем переходя через DFS.Если обнаружен узел, у которого есть неотысканные предшественники, то он должен отслеживать входящие пути до тех пор, пока не будут исследованы все пути для запуска.
Я нашел категория Википедии для графовых алгоритмов но здесь есть небольшое море алгоритмов, и я не знаком с большинством из них.
Редактировать:пример:учитывая график {AB, EB, BC, BD}, пересекаем как:{A, B, E, B, C, D} или уникальный порядок как {A,B, E, C, D}.Обратите внимание, что этот алгоритм, в отличие от BFS или DFS, не требует повторного запуска на новом начальном узле, если все пути первого начального узла исчерпаны.
Решение
В 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)
Другие советы
То, что вы ищете, - это топологическая сортировка.Насколько мне известно, нет простого способа обойти график в его топологически отсортированном порядке без каких-либо предварительных вычислений.
Стандартный способ получить верхнюю сортировку - выполнить стандартную 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, чтобы исправить это.
Если вы ищете 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