Блог

Пытаюсь найти все циклы в a directed graph , через DFS . Но возникла проблема.

Проблема

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

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

Пример

График:

 1 -> [2, 4]
2 -> [3]
3 -> [4]
4 -> [1]
  

Существует 2 цикла между 1 и 4 :

• (A) 1 -> 2 -> 3 -> 4 -> 1
• (B) 1 -> 4 -> 1

Цикл B не может быть обнаружен, если A обнаружен первым, потому 4 что будет пропущен из-за посещения, и он никогда не возвращается к 1.

Текущие идеи

• Одним из возможных решений является запуск с каждого узла, даже если он уже посещен. Но я хочу лучшее решение.
• Вычислить и запомнить хэш пути, пропустить только тогда, когда существует тот же хэш? Это займет немного памяти, верно? И, все еще возможно, что 2 разных пути с одинаковым хэшем ведут к одному и тому же узлу, это не может полностью решить проблему.

Есть идеи?

Кредиты: https://www.hackerearth.com/practice/notes/finding-all-elementry-cycles-in-a-directed-graph /

 integer list array A(n);logical array marked(n);integer stack current_stack ;integer stack marked_stack;/* A(n) is the array of list wich is adjacency list representation*/
 integer procedure intialize(); /*initialize the values*/
    begin;
    for i in n do 
         marked(i):=false
integer procedure print_cycles();
    begin
        for i in current_stack do
            print i ;       
logical procedure backtrack(k) do
    begin
        logical flag=false;
        current_stack->push(k);
        marked_stack->push(k);
        marked(n):=true;
        for i in A(k) do
            if i < s; /* To find only disticnt cycles in topological manner*/
               delete A(i);
            if i==s; /Cycle found */
                print_cycles()
            if marked(i):= false;
                backtrack(n); /*continue dfs*/
        if flag :=true;
            for i in marked_stack do /*unmark the elements that have been visited in any of the cycles starting from s*/
                marked(i):=false;
        current_stack->pop(k);
        backtrack:=flag
    end   backtrack(k)
begin 
    integer procedure backtrack_Util();
        begin
            for s in n do
               backtrack(s);
               while marked_stack(s)->empty do
                    for i in marked_stack do
                        marked(i):=false
     end backtrack_Util()
  

Мы хотим найти отдельные циклы. Следовательно, нам нужно посещать вершины в некотором порядке. В этом порядке нам нужно найти циклы, начинающиеся с этой вершины, и цикл не должен содержать никаких вершин, которые находятся перед начальной вершиной в порядке. Как получить этот порядок? Слова topological manner в одном из комментариев выше неоднозначны, topological sort что не так. Я думаю, что мы можем выбрать порядок так же просто, как номер вершины, например 0,1,2, .., v. Допустим, мы хотим найти цикл, начинающийся с 2. Чтобы избежать нахождения повторяющихся циклов, мы не будем использовать вершины 0 и 1. Если существует какой-либо цикл, состоящий из ребер от 2 до 1 или от 2 до 0, он уже был бы учтен при нахождении циклов, начинающихся с 0 или 1.

Позвольте мне представить конкретную ссылку, которая поможет вам с этой задачей. Это алгоритм Джонсона. По-видимому, это самый быстрый способ выполнить задачу.

На странице 3 упоминается:

Чтобы избежать дублирования цепей, вершина v блокируется, когда она добавляется к некоторому элементарному пути, начинающемуся с s. Он остается заблокированным до тех пор, пока каждый путь от v до s пересекает текущий элементарный путь в вершине, отличной от s. Кроме того, вершина не становится корневой вершиной для построения элементарных путей, если она не является наименьшей вершиной хотя бы в одном элементарном контуре.

Вы также можете посмотреть это видео на YouTube для большего понимания.

Я думаю, что эта информация приемлема.