Depth-first search используется для рекурсивного обхода графа. Чаще всего он используется для поиска элементов, для поиска мостов графов или для преобразования дерева в строку. Как он работает? Мы берём любую вершину и проходимся по её соседям до того, пока у нашей вершины не останется связей. У каждого соседа мы вызываем эту же функцию и проделываем ту же операцию. Главное не забыть записать вершину в посещённые, чтобы избежать циклического прохода по одним и тем же элементам графа. Но вот рекурсия вызывает много проблем. Из-за переполнения стека мы не можем работать с большими графами. #python #алгоритмы #графы #
Depth-first search используется для рекурсивного обхода графа. Чаще всего он используется для поиска элементов, для поиска мостов графов или для преобразования дерева в строку.
Как он работает? Мы берём любую вершину и проходимся по её соседям до того, пока у нашей вершины не останется связей. У каждого соседа мы вызываем эту же функцию и проделываем ту же операцию.
Главное не забыть записать вершину в посещённые, чтобы избежать циклического прохода по одним и тем же элементам графа.
Но вот рекурсия вызывает много проблем. Из-за переполнения стека мы не можем работать с большими графами.
#python
#алгоритмы #графы #