Что делает: обходит граф в глубину (Depth-First Search)

Где применяется: проверка связности графа, поиск цикла, поиск компонент связности, топологическая сортировка, ваще много где можно (даже в динамическом программировании, вроде как, как и в жадных алгоритмах так то)

Общая идея:

Для каждой не пройденной вершины найти все не пройденные смежные вершины и повторить поиск для них

Реализация:

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

int main() {
	for u из G(V) do
		u.color = white // помечаем все вершинки белым O(|V|)
	for u из G(V) do
		if (u.color == white) // запускаем DFS для всех не пройденных вершинок
			DFS(u)
}

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

По необходимости можно использовать два цвета - белый и чёрный. Серый цвет нужен, например, для проверки и поиска циклов в графе. При белом/чёрном можно заменить color на массив visited[], и при заходе в DFS сразу помечать вершинку как visited[v] = true.

‼ Особенности DFS:

1. можно узнать время входа и выхода вершинок (белый/черный цвета соответственно). Используется для конденсации и ещё какого то алгоритма, когда найду заменю эту часть.
2. во время DFS образуется граф предшествования (лес из деревьев поиска в глубину)
3. можно использовать как на ориентированных, так и на неориентированных графах
4. может быть использован для классификации ребер графа (ребра деревьев, обратные ребра, прямые ребра, перекрестные ребра). если будет не лень распишу но мне скорее всего лень, так что если что есть на нирке

Визуализация: