Как искать циклы в графе

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

Поиск элементарных циклов в графе

Рассмотрим алгоритм поиска всех элементарных циклов в неориентированном графе. В этой статье будет приведено описание алгоритма и его реализация на языке программирования C#.

Циклом в графе называется такая конечная цепь, которая начинается и заканчивается в одной вершине. Цикл обозначается последовательностью вершин, которые он содержит, например: (3-5-6-7-3).

Кстати, про цепи, а именно про поиск элементарных цепей в графе мы недавно писали.

Цикл называется элементарным, если все вершины, входящие в него, различны (за исключением начальной и конечной).

Давайте рассмотрим пример. Пусть дан такой граф:

Перечислим все элементарные циклы в нем: 2-3-4-2, 2-3-5-4-2, 3-2-4-3, 3-2-4-5-3, 3-4-5-3, 4-3-2-4, 4-3-5-4, 4-2-3-5-4, 5-4-3-5, 5-4-2-3-5.

Допустим граф задается, как G = (V, E), где V – множество вершин графа, а E – множество ребер этого графа. Вершины и ребра представим объектами таких классов:

, где x, y – координаты центра вершины на плоскости.

, где v1, v2 – номера вершин, которые соединяет данное ребро.

Важно! Нумерация вершин начинается с нуля!

Множества вершин и ребер графа будем хранить в списках List<>:

Для поиска всех элементарных циклов в неориентированном графе будем использовать модификацию рекурсивного алгоритма “поиск в глубину” (DFS). DFS (Depth-first search) – это один из алгоритмов для обхода графа. Обязательно почитайте про него подробнее здесь.

Модифицируем алгоритм DFS в DFScycle. Прототип функции DFScycle будет таким:

, где u – номер вершины, в которой мы находимся в данный момент, endV – номер конечной вершины цикла, Е – список ребер, color[] – массив, в котором хранятся цвета вершин, unavailableEdge – см. ниже, cycle – список, в который заносится последовательность вершин искомого цикла.

В конечном итоге будем преобразовывать последовательность номеров вершин цикла из списка cycle в строку вида: “2-6-7-2″. Хранить всю совокупность элементарных циклов будем в списке строк:

Рассмотрим работу алгоритма DFScycle. В начальный момент времени все вершины графа окрашены в белый цвет. Необходимо выполнить следующее:

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

Теперь поговорим про параметр unavailableEdge. Вершину, для которой ищем цикл, перекрашивать в черный цвет не будем, иначе программа не сможет в нее вернуться, поскольку эта вершина окажется недоступной. Поэтому введем переменную unavailableEdge, в которую будем передавать номер последнего ребра, по которому осуществлялся переход между вершинами, соответственно это ребро на следующем шаге окажется недоступным для перехода. В действительности это необходимо только на первом уровне рекурсии, чтобы избежать некорректной работы алгоритма и вывода, например, ошибочного результата поиска 1-2-1 при наличии такого графа:

Вызовем процедуру DFScycle(…).

Процедура DFScycle(int u, int endV, List E, int[] color, int unavailableEdge, List cycle).

Примечание 1. Поскольку алгоритм обходит граф во все стороны, то выходит, что он обходит цикл в обе стороны, в итоге программа находит одинаковые циклы вида: 1-3-4-1, 1-4-3-1. Получаются своеобразные палиндромы. В реализации функции DFScycle присутствует механизм исключения таких палиндромов из списка результатов поиска.

Примечание 2. Поскольку в языке C# списки List передаются по ссылке (а не по значению), то для корректной работы алгоритма необходимо создавать копию списка cycle cycleNEW и передавать ее [копию] в новый вызов функции DFScycle().

Реализация процедуры DFScycle на языке программирования C#:

Источник

Как я простые циклы искал

Проснулся я как-то ближе к вечеру и решил — всё пора, пора уже сделать новую фичу в моей библиотеке. А за одно и проверку графа на циклы починить и ускорить. К утреннему обеду сделал новую фичу, улучшил код, сделал представление графа в удобном виде, и дошёл до задачи нахождения всех простых циклов в графе. Потягивая чашку холодной воды, открыл гугл, набрал «поиск всех простых циклов в графе» и увидел.

Увидел я не много… хотя было всего лишь 4 часа утра. Пару ссылок на алгоритмы ссылка1, ссылка2, и много намеком на то, что пора спать циклов в графе может быть много, и в общем случае задача не решаемая. И еще вопрос на хабре на эту тему, ответ на который меня тоже не спас — про поиск в глубину я и так знал.

Но раз я решил, то даже NP сложную задачу решу за P тем более я пью воду, а не кофе — а она не может резко закончиться. И я знал, что в рамках моей задачи найти все циклы должно быть возможным за маленькое время, без суперкомпьютеров — не тот порядок величин у меня.

Немного отвлечемся от детектива, и поймем зачем мне это нужно.

Что за библиотека?

Библиотека называется DITranquillity написана на языке Swift, и её задача — внедрять зависимости. С задачей внедрения зависимостей библиотека справляется на ура, имеет возможности которые не умеют другие библиотеки на Swift, и делает это с хорошей скоростью.

Но зачем мне взбрело проверять циклы в графе зависимостей?

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

О проблеме я знал давно, но понимал, что в том виде, в каком сейчас хранится граф сделать быструю проверку сложно. Да и раз уж библиотека умеет проверять граф зависимостей, то сделать «Graph API» само напрашивается. «Graph API» — позволяет отдавать граф зависимостей для внешнего пользования, чтобы:

Особенно ради второго — кто как, а мне нравится смотреть на эти ужасные картинки и понимать как же все плохо.

Исходные данные

Давайте посмотрим, с чем предстоит работать:

Все замеры делаются в debug режиме, не в release, так как использовать проверку графа будут только в debug.

До этой ночи, время проверки составляло 95 минут.

После оптимизации время проверки уменьшилось до 3 секунд, то есть ускорение составило три порядка.

Этап 1. Представление графа

Возвращаемся к нашему детективу. Мой графне Монте Кристо, он ориентированный.
Каждая вершина графа это компонент, ну или проще информация о классе. До появления Graph API все компоненты хранились в словаре, и каждый раз приходилось в него лазить, еще и ключ создавать. Что не очень быстро. Поэтому, будучи в здравом уме, я понимал, что граф надо представить в удобном виде.

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

Но прежде чем напрягать мозги, пальцы уже сделали своё дело, и пока я думал какой сейчас час, на экране уже успел появиться код для создания графа в виде матрицы смежности. Жалко конечно, но код пришлось переписать — для моей задачи важнее как можно быстрее находить исходящие ребра, а вот входящие меня мало интересуют. Да и память в наше время безгранична — почему бы её не сэкономить?

Переписав код, получилось что-то на подобии такого:

Где Vertex информация о вершине, а Edge информация о переходе, в том числе и индексы, куда по этому ребру можно перейти.
Обращаю внимание что ребро хранит переход не один в один, а один в много. Это сделано специально, чтобы обеспечить уникальность рёбер, что в случае зависимостей очень важно, так как два перехода на две вершины, и один переход на две вершины означает разное.

Этап 2. Наивный поиск в глубину

Из начала статьи все же помнят, что к этому моменту было уже 4 часа утра, а значит, единственная идея, как реализовать поиск всех простых циклов была та, что я нашел в гугле, да и мой учитель всегда говорил — «прежде чем оптимизировать, убедись, что это необходимо». Поэтому первым делом я написал обычный поиск в глубину:

Запустил этот алгоритм, подождал 10 минут… И, конечно же, ушел спать — А то уже солнце появилось из-за верхушек зданий.

Пока спал, думал — а почему так долго? Про размер графа я уже писал, но в чем проблема данного алгоритма? Судорожно вспоминая дебажные логи вспомнил, что для многих вершин количество вызовов функции dfs составляет миллион, а для некоторых по 30 миллионов раз. То есть в среднем 900 вершин * 1000000 = 900.000.000 вызовов функции dfs…

Откуда такие бешеные цифры? Будь бы это обычный лес, то все бы работало быстро, но у нас же граф с циклами… ZZzzz.

Этап 3. Наивная оптимизация

Проснулся я снова не по завету после обеда, и первым делом было не пойти в туалет, и уж точно не поесть, а посмотреть, сколько же выполнялся мой алгоритм, а ну да всего-то полтора часа… Ну, ладно, я за ночь придумал, как оптимизировать!

В первой реализации ищутся циклы, проходящие только через указанную вершину, а все подциклы, найденные при поиске основных циклов, просто игнорируются. Возникает желание перестать их игнорировать — тогда получается, что можно выкидывать из рассмотрения все вершины, через которые мы уже прошли. Сделать это не так сложно, правда, когда пальцы не попадают по клавиатуре чуть сложнее, но каких-то полчаса и готово:

Дальше по заповедям программиста «Программист ест, билд идёт» я ушел есть… Ем я быстро. Вернувшись через 10 минут и увидев, что все еще нет результата, я огорчился, и решил подумать, в чем же проблема:

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

Этап 4. А что если отсекать листья из поиска

Проснуться я уже успел, а значит самое время для листочка и карандаша. Посмотрев на цифры, нарисовав картинки на листочке, стало понятно, что листья обходить не имеет смысла, и даже не листья, а целые ветки, которые не имеют циклов. Смысл в них заходить, если мы ищем циклы? Вот их и будем отсекать. Пока это думал, руки уже все сделали, и даже нажали run… Ого, вот это оптимизация — глазом моргнуть не успел, а уже все нашло… Ой, а чего циклов так мало то нашлось… Эх… А всё ясно проблема в том, что я не налил себе стакан воды. На самом деле проблема вот в этой строчке:

Я решил, что в этом случае мы тоже наткнулись на лист, но это неверно. Давайте рассмотрим вот такой граф:

В этом графе есть под цикл B->E->C значит, этот if выполнится. Теперь предположим, что вначале мы идем так:
A->B->E->C->B. При таком проходе C, Е помечается как лист. После находим цикл A->B->D->A.
Но Цикл A->C->B->D->A будет упущен, так как вершина C помечена как лист.

Если это исправить и отбрасывать только листовые под ветки, то количество вызовов dfs снижается, но не значительно.

Этап 5. Делаем подготовку к поиску

Ладно, еще целых полдня впереди. Посмотрев картинки и различные дебажные логи, стало понятно, что есть ситуации, где функция dfs вызывается 30 миллионов раз, но находится всего 1-2 цикла. Такое возможно в случаях на подобии:

Где «Big» это какой-то большой граф с кучей циклов, но не имеющий цикла на A.

И тут возникает идея! Для всех вершин из Big и C, можно заранее узнать, что они не имеют переходов на A или B, а значит, при переходе на C понятно, что эту вершину не нужно рассматривать, так как из нее нельзя попасть в A.

Как это узнать? Заранее, для каждой вершины запустить или поиск в глубину, или в ширину, и не посещать одну вершину дважды. После сохранить посещенные вершины. Такой поиск в худшем случае на полном графе займет O(N^2) времени, а на реальных данных намного меньше.

Текст для статьи я писал гораздо дольше, чем код для реализации:

Готовясь к худшему, я запустил новую реализацию, и пошел смотреть в окно на ближайшее дерево, в 5 метрах — вдаль смотреть говорят полезно. И вот счастье — код полностью исполнился за 15 минут, что в 6-7 раз быстрее прошлого варианта. Порадовавшись мини победе, и порефачив код, я начал думать, что же делать — такой результат меня не устраивал.

Этап 6. Можно ли использовать прошлые результаты?

Все время пока я писал код, и пока спал, меня мучил вопрос — а можно ли как-то использовать результат прошлых вычислений. Ведь уже найдены все циклы через некоторую вершину, наверное, что-то это да значит для других циклов.
Чтобы понять, что это значит, мне понадобилось сделать три итерации, каждая из которых была оптимальней предыдущей.
Все началось с вопроса — «Зачем начинать поиск с новой вершины, если все исходящие ребра ведут в вершины, которые или не содержат цикла, или это вершина через которую уже были построены все циклы?». Потом поток мыслей дошел до того что проверку можно делать рекурсивно. Это позволило уменьшить время до 5 минут.

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

Посмотрев на это простое решение, я нажал run, и был уже готов снова отойти от компьютера, как вдруг — все проверки прошли… 6 секунд? Не, не может быть… Но по дебажным логам все циклы были найдены.

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

Такая проверка не только сильно ускоряет работу, но и полностью устраняет появление дублей, без необходимости их обрезать/сравнивать.
Что позволяет сэкономить время на способе хранения циклов — можно или вообще не хранить их или хранить в обычном массиве, а не множестве. Это экономит еще 5-10% времени исполнения.

Этап 6. Профайл

Результат в 5-6 секунд меня уже устраивал, но хотелось еще быстрее, на улице еще солнце даже светит! Поэтому я открыл профайл. Я понимал, что на языке Swift низкоуровневая оптимизация почти невозможна, но иногда находишь проблемы в неожиданных местах.
И какое было моё удивление, когда я обнаружил, что половину времени из 6 секунд занимают логи библиотеки… Особенно с учетом, что я их выключил. Как говорится — «ты видишь суслика? А он есть. «. У меня суслик оказался большим — на пол поля. Проблема была типичная — некоторое строковое выражение считалось всегда, независимо от необходимости писать его в логи.

Вроде изменения не значительные и, кажется, что второй код должен работать медленнее — и на многих языках второй код будет работать медленнее, но на Swift он быстрее на 5-10%.

Итоги

А какие могут быть итоги? Цифры говорят сами за себя — было 95 минут, стало 2.5-3 секунды, да еще и добавилось новых проверок.

Три секунды тоже выглядит не шустро, но не стоит забывать, что это на большом и не красивом графе зависимостей — такие днем с огнем не сыщешь в мобильной разработке.
Да и на другом проекте, который больше похож на средний мобильный проект, время с 15 минут уменьшилось до менее секунды, при этом на более слабом железе.

Ну а появлению статьи благодарим гугл — который не захотел мне помогать, и я придумывал все из головы, хоть и понимаю, что Америку я не открыл.

Весь код на языке Swift можно найти в папке.

Немного рекламы и Планы

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

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

P.S. Если отключить 5 этап полностью, это который добавление доп. действия перед началом поиска, то скорость работы понизится в 1.5 раза — до 4.5 секунд. То есть в этой операции даже после всех других оптимизаций есть толк.

P.P.S. Некоторые факты из статьи выдуманные, для придания красоты картины. Но, я на самом деле пью только чистую воду, и не пью чай/кофе/алкоголь.

UPD: По просьбе добавляю ссылку на сам граф. Он описан в dot формате, имена вершин просто нумерацией. Ссылка
Посмотреть на то как это выглядит визуально можно по этой ссылке.

UPD: banshchikov нашёл другой алгоритм Donald B. Johnson. Более того есть его реализация на swift.
Я решил сравнить свой алгоритм, и этот алгоритм на имеющемся графе.
Вот что получилось:

Время измерялось только на поиск циклов. Сторонняя библиотека конвертирует входные данные в удобные ей, но подобная конвертация должна занимать не более 0.1 секунды. А как видно время отличается на порядок (а в релизе на два). И списать такую большую разницу на неоптимальную реализацию нельзя.

Источник

Как искать циклы в графе

Поиск всех циклов в графе

При изучении алгоритма на e-maxx Проверка графа на ацикличность и нахождение цикла понял, что алгоритм прекращает работу при нахождении первого цикла. Как найти все циклы в графе? Я переделал исходный алгоритм. При реализации моего алгоритма, некоторые циклы упускаются из вида. Например:

Ребра в неориент. графе: 1 2 1 3 2 3 2 4 3 4 Циклы: 1 2 3 1 2 3 4 2 1 2 4 3 1

Мой алгоритм find_cycles() не находит третий цикл. Как можно это исправить?

Все циклы — это все простые циклы? (Если нет, то их обычно бесконечно много.)

В полном графе из n вершин различных простых циклов — порядка n!. Так что в любом случае решение, работающее для произвольного графа, будет не быстрее перебора. Перебор отличается от поиска в глубину тем, что при выходе из рекурсивной функции следует вообще снимать пометку ( color[v] = 0; ).

При выходе она у меня снимается же? ( color[v] = 2; )

Вообще снимать — это вернуть в исходное состояние. Чтобы if(color[to] == 0) не отличил.

Значит для задач это бысмысленное дело? Т.е. в задачах это не нужно?

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

Интересно, что можно «быстро» найти базис «простых циклов».

Или формально: сопоставим циклу битовую строку длинной E (число ребер), ясно, что сумма таких битовых строк даст битовую строку, соответствующую циркуляции. То есть можно найти базис в лин. пространстве циркуляций. Таким базисом будет следующий набор циклов: строим остовный лес, далее берем любое ребро не из леса, и получаем, отбросив ненужную часть леса, цикл. Несложно заметить, что это базис. таким образом размеренность пространства: E-(V-C), C-число компонент связности.

Лучше бы дали ссылку, например, сюда или на какую-нибудь книгу. Потому что если человек не сильно хорошо разбирается в линейной алгебре (а таких тут, кажется, большинство), то ему с Вашего объяснения ничего ясно не будет.

Источник

Поиск всех циклов в ориентированном графе

Как я могу найти (перебрать) ВСЕ циклы в ориентированном графе от/до заданного node?

Например, я хочу что-то вроде этого:

ОТВЕТЫ

Ответ 1

Я нашел эту страницу в своем поиске и так как циклы не такие же, как сильно связанные компоненты, я продолжал искать и, наконец, нашел эффективный алгоритм, который перечисляет все (элементарные) циклы ориентированного графа. Это от Дональда Б. Джонсона, и документ можно найти по следующей ссылке:

Реализацию java можно найти в:

В математической демонстрации алгоритма Джонсона можно найти здесь, реализация может быть загружена с правой стороны ( «Загрузить код автора» ).

Примечание. На самом деле для этой проблемы существует множество алгоритмов. Некоторые из них перечислены в этой статье:

Согласно статье, алгоритм Джонсона является самым быстрым.

Ответ 2

Глубокий первый поиск с обратным следом должен работать здесь. Храните массив логических значений, чтобы отслеживать, посещали ли вы ранее node. Если у вас заканчиваются новые узлы, чтобы перейти (без удара node, которые вы уже были), тогда просто отступите назад и попробуйте другую ветку.

DFS легко реализовать, если у вас есть список смежности для представления графика. Например, adj [A] = указывает, что B и C являются дочерними элементами A.

Вызвать вышеуказанную функцию с помощью запуска node:

Ответ 3

Один из базовых алгоритмов для поиска всех простых циклов в ориентированном графе таков: выполните первый шаг по пересечению всех простых путей (тех, которые не пересекаются) на графике. Каждый раз, когда текущий node имеет преемника в стеке, обнаруживается простой цикл. Он состоит из элементов в стеке, начиная с идентифицированного преемника и заканчивая вершиной стека. Глубина первого обхода всех простых путей аналогична первому поиску глубины, но вы не отмечаете/не записываете посещенные узлы, отличные от тех, которые в настоящее время находятся в стеке, как точки остановки.

Алгоритм грубой силы выше ужасно неэффективен и в дополнение к этому генерирует несколько копий циклов. Однако это является отправной точкой множества практических алгоритмов, которые применяют различные улучшения для повышения производительности и предотвращения дублирования циклов. Я с удивлением обнаружил, что эти алгоритмы недоступны в учебниках и в Интернете. Поэтому я провел некоторое исследование и реализовал 4 таких алгоритма и 1 алгоритм для циклов в неориентированных графах в библиотеке Java с открытым исходным кодом: http://code.google.com/p/niographs/.

Кстати, поскольку я упоминал неориентированные графики: алгоритм для них различен. Постройте остовное дерево, а затем каждое ребро, которое не является частью дерева, образует простой цикл вместе с некоторыми ребрами в дереве. Циклы, найденные таким образом, образуют так называемую базу циклов. Все простые циклы можно найти, объединив 2 или более различных базовых цикла. Более подробно см., Например, это: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf.

Ответ 4

Он реализует алгоритм Джонсона, упомянутый в наилучшем ответе на этот вопрос, но его выполнение довольно просто.

Короче вам нужно следующее:

Ответ: [[‘a’, ‘b’, ‘d’, ‘e’], [‘a’, ‘b’, ‘c’]]

Ответ 5

Сильно соединенные компоненты найдут все подграфы, которые содержат по крайней мере один цикл, а не все возможные циклы на графике. например если вы берете все сильно связанные компоненты и сворачиваете/группируете/объединяете каждый из них в один node (т.е. node на компонент), вы получите дерево без циклов (фактически DAG). Каждый компонент (который в основном является подграфом с по меньшей мере одним циклом в нем) может содержать гораздо больше возможных циклов внутри, поэтому SCC НЕ найдет все возможные циклы, он найдет все возможные группы, которые имеют по крайней мере один цикл, и если вы группируете их, то график не будет иметь циклов.

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

Ответ 6

Мне дали это как вопрос интервью один раз, я подозреваю, что это случилось с вами, и вы приезжаете сюда за помощью. Разделите проблему на три вопроса, и вам станет легче.

Проблема 1) Используйте шаблон итератора, чтобы обеспечить способ повторения результатов маршрута. Хорошим местом для логики, чтобы получить следующий маршрут, вероятно, является «moveNext» вашего итератора. Чтобы найти правильный маршрут, это зависит от вашей структуры данных. Для меня это была таблица sql, полная допустимых возможностей маршрута, поэтому мне пришлось создать запрос, чтобы получить действительные адресаты с учетом источника.

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

Задача 3) Если в какой-то момент вы видите, что вы удваиваете назад, вы можете вытащить вещи из коллекции и «создать резервную копию». Затем с этого момента попробуйте снова «двигаться вперед».

Взлом: если вы используете Sql Server 2008, есть некоторые новые «иерархические» вещи, которые вы можете использовать для быстрого решения этой проблемы, если вы структурируете свои данные в дереве.

Ответ 7

Существует два этапа (алгоритмы), связанные с поиском всех циклов в DAG.

Первым шагом является использование алгоритма Тарьяна для нахождения набора сильно связанных компонентов.

Вот ссылка на реализацию Java с тестовым примером:

Ответ 8

В случае неориентированного графика, опубликованная недавно публикация (Оптимальный список циклов и st-путей в неориентированных графах) предлагает асимптотически оптимальное решение. Вы можете прочитать его здесь http://arxiv.org/abs/1205.2766 или здесь http://dl.acm.org/citation.cfm?id=2627951 Я знаю, что он не отвечает на ваш вопрос, но поскольку название вашего вопроса не указывает направление, оно может быть полезно для поиска Google

Ответ 9

Начните с node X и проверьте все дочерние узлы (родительский и дочерний узлы эквивалентны, если они ненаправлены). Отметьте эти дочерние узлы как дети X. Из любого такого дочернего node A отметьте его дочерними элементами дочерних элементов A, X ‘, где X’ отмечен как 2 шага.). Если вы позже нажмете X и отметьте его как дочерний элемент X », это означает, что X находится в цикле 3 node. Откат к нему родительский легко (как есть, алгоритм не поддерживает этого, так что вы обнаружите, какой из родителей имеет X).

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

Ответ 10

Если вы хотите найти все элементарные схемы на графике, вы можете использовать алгоритм EC, написанный JAMES C. TIERNAN, найденный на бумаге с 1970 года.

очень оригинальный алгоритм EC, который мне удалось реализовать в php (надеюсь, что ошибок здесь нет). Он может также найти петли, если они есть. Цепи в этой реализации (которые пытаются клонировать оригинал) представляют собой ненулевые элементы. Ноль здесь означает несуществование (нулевое, как мы его знаем).

В обоих случаях требуется, чтобы узлы были последовательными.

Возможно, вам придется изучить оригинальную бумагу, Джеймс С. Тиернан Элементарный алгоритм цепи

Я проанализировал и задокументировал EC, но, к сожалению, документация находится на греческом языке.

Ответ 11

Ответ 12

Вы не можете сделать небольшую рекурсивную функцию для перемещения узлов?

если у вас тонна узлов, у вас закончится стек

Ответ 13

Я наткнулся на следующий алгоритм, который кажется более эффективным, чем алгоритм Джонсона (по крайней мере для больших графов). Однако я не уверен в его производительности по сравнению с алгоритмом Тарьяна.
Кроме того, я только проверил это для треугольников. Если вы заинтересованы, см. «Алгоритмы лингвистики и подграфа» Норришиджа Чиба и Такао Нисизики (http://dx.doi.org/10.1137/0214017)

Ответ 14

Решение Javascript с использованием связанных списков ссылок. Могут быть модернизированы до непересекающихся множеств леса для более быстрого времени выполнения.

Ответ 15

DFS с начала node s, отслеживать путь DFS во время обхода и записывать путь, если вы найдете ребро из node v в пути к s. (v, s) является обратным краем в дереве DFS и, таким образом, указывает цикл, содержащий s.

Ответ 16

Что касается вашего вопроса о перестановочном цикле, читайте здесь: https://www.codechef.com/problems/PCYCLE

Вы можете попробовать этот код (введите размер и число цифр):

Ответ 17

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

Джонсон-алгоритм действительно дает все уникальные простые циклы и имеет хорошую временную и пространственную сложность.

Но если вы хотите просто найти MINIMAL-циклы (это означает, что может быть больше одного цикла, проходящего через любую вершину, и мы заинтересованы в поиске минимальных). И ваш график не очень большой, вы можете попытаться использовать простой ниже. Это ОЧЕНЬ просто, но довольно медленно по сравнению с Джонсоном.

Источник