Выполнение DFS и BFS на ориентированном графе

Question

Предположим, у нас есть график, таких как:

Если вы хотите путь от 0 до 5, в каком порядке мы посещаем узлы, если мы выполняем DFS и BFS на этом графике (предположим, что самый нижний элемент всегда нажимается первым). У меня возникли проблемы с концепцией того, как алгоритмы будут работать для графика с циклами, и я надеялся, что кто-то сможет описать процедуру, на которую каждый принимает такой график.

Answer 1

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

Стек сверху донизу.

ДФС:

empty stack 
visiting 0: stack: 2, 1, visited: 0 
visiting 2: stack: 5, 3, 1 visited: 0, 2 
visiting 5: stack: 4, 3, 1 visited: 0, 2, 5 
visiting 4: stack: 3, 2, 3, 1 visited: 0, 2, 4, 5 
visiting 3: stack: 4, 2, 3, 1 visited: 0, 2, 3, 4, 5 
visiting 4: (nothing to do) - stack: 2, 3, 1 visited: 0, 2, 3, 4, 5 
visiting 2: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5 
visiting 3: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5 
visiting 1: stack: 3, 0 visited: 0, 1, 2, 3, 4, 5 
visiting 3: (nothing to do) - stack: 1 visited: 0, 1, 2, 3, 4, 5 
visiting 1: (nothing to do) - stack empty visited: 0, 1, 2, 3, 4, 5 
DONE 

Подобным же образом сделать для BFS.