Что делает: bruh

Где применяется: топологическая сортировка (можно ли вообще топсортить), поиск MST (Краскал, Прим)

Общая идея:

При обходе DFS, если вершинка смежна с серой вершиной, то существует цикл; чтобы восстановить цикл, заводим стек.

Подробнее:

В случае **ориентированного графа** произведём серию обходов. То есть из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе из нее — в чёрный. И, если алгоритм пытается пойти в серую вершину, то это означает, что цикл найден.

В случае **неориентированного графа**, одно ребро не должно встречаться в цикле дважды по определению. Поэтому необходимо дополнительно проверять, что текущее рассматриваемое из вершины ребро не является тем ребром, по которому мы пришли в эту вершину.

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

Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в **стек**. Когда поиск в глубину нашел вершину, которая лежит на цикле, будем последовательно вынимать вершины из стека, пока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле

Реализация:

Просто проверка на цикл:

// псевдокод писала Я так что чекните если что не так!

string DFS(int u) {
	u.color = gray // помечаем, что вершинка находится в процессе обхода
		for v из G(V) do
			if v.color == gray // если вершина ведёт в открытую вершину
				return "There's a cycle!"
			if v.color == white
				DFS(v)
	u.color = black // после обхода всех смежных вершин помечаем, что вершина прошла DFS
}

Восстановление цикла:

// псевдокод писала Я так что чекните если что не так!

stack<int> Vertices
vector<int> Result

void DFS(int u) {
	u.color = gray // помечаем, что вершинка находится в процессе обхода
	Vertices.push(u) // добавляем вершину в стек
		for v из G(V) do
			if v.color == gray // если вершина ведёт в открытую вершину (есть цикл)
				return; // выходим из DFSа с заполненным стеком
			if v.color == white
				DFS(v)
	u.color = black // после обхода всех смежных вершин помечаем, что вершина прошла DFS
}

int main() {
	DFS(u)
	int cycle_start = Vertices.front() // извлекаем верхнюю вершинку из стека
																		// ака начало цикла
	Result.push_back(cycle.start)
	for elem из Vertices do // чекаем стек пока не найдет cycle_start
		if (elem != cycle_start)
			Result.push_back(elem) // записываем весь цикл
		else break;
}

‼ Особенности поиска и восстановления циклов:

Визуализация: этим я займусь чуть попозже