Поиск циклов
Материал из 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