Мне дан список ребер (каждое из которых имеет свойства «От» и «До», которые указывают, какие вершины они соединяют).
Я хочу либо вернуть ноль, если они не образуют цикл в этом (неориентированном) графе, либо вернуть список, образующий цикл.
Кто-нибудь знает, как бы я поступил с такой проблемой? Я не знаю.
Алгоритмы этого типа называются алгоритмами обнаружения цикла графа. Есть некоторые сложности в выборе алгоритмов в зависимости от потребностей приложения или контекста проблемы. Например, вы хотите найти первый цикл, самый короткий цикл, самый длинный цикл, все циклы, является ли график однонаправленным или двунаправленным и т. д.?
Существует множество алгоритмов обнаружения циклов на выбор, в зависимости от необходимости и допустимой вычислительной сложности, а также характера цикла (например, поиск первого, самого длинного и т. д.). Некоторые общие алгоритмы включают следующее:
Конкретный алгоритм, который вы выберете, будет зависеть от ваших потребностей и от того, насколько эффективным должен быть алгоритм. Если требуется серьезная эффективность, я бы посоветовал просмотреть некоторые научные статьи по этой теме и сравнить и сопоставить некоторые компромиссы различных алгоритмов.
Способ, которым меня научили делать это, включает в себя сохранение списка посещенных вершин.
Перемещайтесь по графу, сохраняя каждую вершину и добавляя ее в список. Каждый ход сравнивайте текущую вершину со списком — если она присутствует, вы посещали ее раньше и, следовательно, находитесь в цикле.
