Максимальный цикл в графе - есть ответ

shl, 304 просмотра

Как применить обход графа в глубину к выделению в орграфе цикла максимальной длины?

Примечание:
Артемка,
эти действия нужно проводить для каждой белой (первый раз встречаемой) вершины? В интернете вопрос описан мутновато, типа задача в общем виде NP-полная, поэтому и не наотимизируешься особо.

Ответы:

Артёмка

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

Артёмка

Ну вот примерно так:
1. Начинаешь обход с какой-нибудь вершины.
2. Пробуешь пройти по ребру в другую вершину, увеличивая длину цикла на 1.
2.1. Если ты в этой вершине не был, идешь дальше.
2.2. Если же был, то проверяешь, та ли это вершина, с которой ты начал обход.
2.2.1. Если та, смотришь длину получившегося цикла, сравниваешь с максимальной.
2.2.2. Если не та, возвращаешься назад, уменьшая длину цикла, пробуешь пройти по следующему ребру. Если ребер больше нет, опять возвращаешься назад и т.д.
Если хочешь оптимизировать, можешь убрать те вершины, в которые ребра только входят, и те, из которых ребра только выходят, - они всё равно в цикл не войдут.

14 лет назад

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

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

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