Распечатать все циклы в ориентированном графе

Question

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

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO; #<- why?

(1) Какая польза от этого последнего утверждения? Краткое описание того, как работает al go, было бы очень полезно. Поскольку алгоритм в основном заключается в подсчете количества циклов от узла к тому же узлу, мы можем использовать другой массив, вызвать его как v и сделать следующий трюк:

def dfs(adj,node,start,visited):
    if (node in v):
        return

, а затем написать все остальное в целости и сохранности. Как часть основной функции,

for i in range(len(adj)):
    dfs(adj,i,i,visited)
    v.append(i)

делает работу аккуратно. Таким образом, в основном мы устанавливаем посещенный [узел] элементов (узлов) уже установленного цикла равным 0 (ложно) навсегда. Непростая временная сложность, но, тем не менее, это работает.

Для печати массива я планировал поместить все элементы в массив (назовите его A) и продолжать добавлять, пока не будет найден путь. Теперь, когда путь найден, вернитесь назад от начала (теперь A [last_elem]) к началу (то есть A [some_prev_elem]). Затем удалите элементы из A до положения, где рекурсия должна продолжаться (например, 0-> 1-> 2-> 0 и 0-> 1-> 3-> .. являются двумя ветвями дерева dfs, затем мы удаляем только последние два элемента A (которые равны 2 и 0), поскольку рекурсия продолжается с 1 сейчас).

(2) Я не могу реализовать алгоритм, который я только что написал. Это основной вопрос, но я думаю, что мне нужно понять (1) выше, чтобы понять код для печати всех циклов.

Я понимаю, что есть алгоритмы на inte rnet, я пытаясь использовать этот алгоритм.

Answer 1

Давайте попробуем нарисовать граф / дерево и стек вызовов DFS. По моему мнению, ключом к пониманию здесь является отслеживание того, как «посещенные» изменения. Например:

|step |node |visited
|1    |1    |{1: yes}     
|2    |2    |{1: yes, 2: yes}
|3    |6    |{1: yes, 2: yes, 6: yes}
|4    |7    |{1: yes, 2: yes, 6: no, 7: yes}
...

Вот интересная часть, пожалуйста, обратите внимание на то, как 6 изменилось в посещенных на 4-м шаге. Мы просто возвратили снова с 6-го узла на 2-й, и поэтому 6 не находится внутри текущего пути .

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

В моем примере это то, что в конечном итоге произойдет с узлом 1, и вы можете проверить его, если вы продолжаете заполнять таблицу вызовов DFS.