Поиск в глубину (DFS - depth-first search) является одним из алгоритмов обхода графа. Суть данного метода состоит в том, что мы продвигаемся вглубь графа настолько, насколько это возможно. Данный алгоритм использует рекурсию. Чтобы нагляднее понять поиск в глубину, представьте лабиринт, который вам необходимо пройти. Если вы зашли в тупик - это означает, что вам необходимо вернуться на шаг назад и пойти далее, таким образом, рано или поздно, вы найдете выход (если он есть).

Принцип работы

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

Реализация для произвольного графа

bool used[100];
vector <vector<int>> graph(100);

void dfs(int vertex)
{
	cout << "Current vertex: " << vertex << endl;
	used[vertex] = true;
	for (auto u : graph[vertex])
	{
		if (!used[u])
			dfs(u);
	}
}

int main()
{
	int n;
	cout << "Enter the number of edges: ";
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	dfs(1); // начинаем обход с первой вершины
	return 0;
}

Область применения

Стоит отметить одну особенность данного алгоритма - поиск в глубину не ищет кратчайший путь (в отличие от BFS). Очевидным применением данного алгоритма будет прохождение лабиринта. На практике DFS чаще всего используют для проверки графа на связность, или более обобщённо, поиска компонент связности, поиска циклов и работы с деревьями.