⚡️ Алгоритм DFS

Depth-first search используется для рекурсивного обхода графа. Чаще всего он используется для поиска элементов, для поиска мостов графов или для преобразования дерева в строку.

Как он работает? Мы берём любую вершину и проходимся по её соседям до того, пока у нашей вершины не останется связей. У каждого соседа мы вызываем эту же функцию и проделываем ту же операцию.

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

Но вот рекурсия вызывает много проблем. Из-за переполнения стека мы не можем работать с большими графами.

#алгоритмы #графы