Изменения

Пусть дан граф без петель и кратных рёбер. Требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе.

Решим эту задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за <tex>O(ME)</tex>.

Пусть дан В случае <b>ориентированный графориентированного графа</b>. Произведём серию поисков в глубину в графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе {{---}} в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл.

В случае <b>неориентированного графа</b> любое ребро представляется как два ребра {{---}} прямое и обратное. Тогда мы посчитаем, что эти два ребра составляют цикл, что неверно. Чтобы избежать этого, будем передавать еще один параметр поиска в глубину {{---}} вершину, из которой мы пришли. Теперь мы считаем, что нашли цикл, если вершина, в которую мы хотим пойти серая и не является вершиной , из которой мы пришли.