Вопросы и ответы
Топ за год Облако тегов  

Нужен эффективный алгоритм выборки всех циклов в графе.

алгоритмы графы DFS

well-noklip, 422 просмотра
2
Очевидным решением задачи поиска циклов в заданном графе является применение DFS или, проще говоря поиска в глубину. Но, кажется, есть более оптимальные алгоритмы решения (хотя в общем случае задача является NP-полной).
Ответы:
Cronopio
За 10 копеек?
well-noklip
Ну, во-первых, сейчас уже трудно цену поменять, во-вторых, эта тема не настолько острая, в любых книгах и поисковиках можно найти тучу информации. Но есть знающие люди, и я думаю, если ты знаешь, то цена не должна быть так важна, а если ты просто хочешь подзаработать, то вряд-ли ты сможешь Реально помочь.
DeadShot
Поиск в глубину, собственно, является естественным подходом для поиска циклов.
Однако, замечу, что лучше все-таки искать не все циклы графа поиском в глубину (решение "в лоб"), а только фундаментальное множество циклов. Т.к. каждый цикл графа может быть получен из циклов этого множества (фундаментального множества циклов) посредством операции симметрической разности (иногда получаются вырожденные случаи, но они легко отбрасываются).
well-noklip
DeadShot, какова вычислительная сложность предложенного алгоритма?
Я полагаю, что перебор всевозможных циклов, порождаемых фундаментальными - набор сочетаний из количества фундаментальных по 2.
DeadShot
> DeadShot, какова вычислительная сложность предложенного алгоритма?
Какая сложность может быть для NP-полных задач? [1]
well-noklip
А искать Эйлеровы циклы для всех подграфов? И вообще, кажется, что решение всё же связано с перебором циклов и подсчётом их длины... - Или я всё же понял плохо мысль про Эйлеров цикл.


17 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.