Задача с ориентированным графом [дубликат]

119

20 декабря 2020, 09:40

На этот вопрос уже дан ответ здесь:

Подскажите пожалуйста, класный алгоритм на поиск минимальных циклов в орграфе, С++ [закрыт] (1 ответ)

Закрыт 1 год назад.

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

Answer 1

Вам поможет поиск в ширину.

Запускаете поиск в ширину, как только "волновой фронт" соприкоснётся сам с собой - вы нашли минимальный цикл.

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

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