Поиск в глубину DFS

Алгоритм поиска в глубину (dfs — depth-first-search) является одним из основных алгоритмов на графах и применяется как составная часть во многих других алгоритмах.

Пример
Пусть у нас есть неориентированный граф на n вершин, заданный нам в каком-либо виде (матрица смежности, список смежности или список рёбер). Также пусть нам дан номер вершины и нас просят найти компоненту связности, к которой эта вершина принадлежит.

Алгоритм

1. Встанем в текущую вершину графа
2. Отметим текущую вершину как посещённую
3. Посмотрим, с какими вершинами наша текущая вершина связана и возьмём из них первую, которая ещё не посещена
   • Если такая вершина нашлась, то пойдём в неё (шаг 1)
   • Если такой вершины не нашлось, то вернемся в вершину, из которой пришли в текущую

Ссылка на гифку с визуализацией DFS

Реализация через рекурсивную функцию

const int maxn = 1e5;

bool used[maxn];
vector<int> g[maxn];

// что-то ещё
// ***

void dfs(int v){
used[v] = true;
// способ пройтись по вектору/массиву по элементам
// переменная to будет принимать поочередно все значения вектора/массив от нулевого до последнего
// в данном случае g[v] - это целый вектор
for(int to : g[v]){
if(used[to])
continue;
dfs(to);
}
}

C

const int maxn = 1e5;



bool used[maxn];

vector<int> g[maxn];



// что-то ещё

// ***



void dfs(int v){

   used[v] = true;

   // способ пройтись по вектору/массиву по элементам

   // переменная to будет принимать поочередно все значения вектора/массив от нулевого до последнего

   // в данном случае g[v] - это целый вектор

   for(int to : g[v]){

       if(used[to])

           continue;

       dfs(to);

   }

}

Временная сложность алгоритма
Алгоритм работает за: О(N + M), где N и M - это количество вершин и ребер в графе, соответственно.