Поиск циклов

Материал из Algocode wiki
Версия от 13:31, 26 сентября 2019; Глеб (обсуждение | вклад) (Новая страница: «Циклом в графе $G$ называется ненулевой путь, ведущий из вершины $v$ в саму себя. Граф назыв...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Циклом в графе $G$ называется ненулевой путь, ведущий из вершины $v$ в саму себя. Граф называют ацикличным, если в нем нет циклов.

В обычном dfs мы используем два цвета (1 - вершина посещена, 0 - не посещена), если же нам надо найти цикл, то давайте хранить 3 цвета:

  • 0 - вершина не просмотрена
  • 1 - мы входили DFS-ом в эту вершину, но еще не вышли (а значит из нее есть путь до текущей),
  • 2 - мы входили DFS-ом в эту вершину

Заметим, что цикл будет тогда и только тогда, когда мы пытаемся войти в вершину с цветом 1.

 1 void dfs (int v) {
 2     used[v] = 1;
 3     for (size_t i=0; i < g[v].size(); ++i) {
 4         int to = g[v][i];
 5         if (used[to] == 0){
 6             p[to] = v;
 7             dfs (to);
 8         }
 9         else if (used[to] == 1 && to != p[v]) {
10             cycle = true;
11         }
12     }
13     used[v] = 2;
14 }



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin