Задать вопрос
@sashx

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

Друзья, здравствуйте! Подскажите, как я могу найти максимальный по длине путь в графе с помощью обхода в ширину?
  • Вопрос задан
  • 149 просмотров
Подписаться 1 Простой 5 комментариев
Помогут разобраться в теме Все курсы
  • Яндекс Практикум
    Python-разработчик
    10 месяцев
    Далее
  • Skillfactory
    DevOps-инженер
    6 месяцев
    Далее
  • Хекслет
    Фронтенд-разработчик
    10 месяцев
    Далее
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Максимальный путь в графе с циклами найти тяжело. Обходом в ширину - вообще никак. Только полным перебором (что является скорее рекурсивным обходом в глубину, но с откатами).

Если граф дерево или ориентированный ациклический, то работает любой обход.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы