DFS

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

При обходе графа мы используем вспомогательный массив used, в котором храним 1, если вершина была посещена или 0 иначе. В начале мы считаем, что все вершины не использовались, затем мы выбираем одну вершину, помечаем ее посещенной и запускаемся рекурсивно из всех ее соседей, тогда мы посетим все вершины, которые достижимы из данной, если же остались вершины с used = 0 значит они недостижимы.

Красивая визуализация: https://visualgo.net/en/dfsbfs

1 void dfs (int v) {
2   used[v] = 1;
3   for (auto to : g[v]) {
4       if (!used[to]) {
5           dfs(to);
6       }
7   }
8 }

Давайте оценим сложность алгоритма. Так как мы проверяем, что вершина еще не использовалась, то всего мы пройдет каждую вершину 1 раз, но при этом и ребро между двумя вершинами, мы рассматриваем только когда рассматривается один конец, то есть мы просмотрим каждое ребро не более одного раза, суммарно получаем оценку $O(N + M)$.

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin