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

DFS идёт вглубь по одному пути, пока не упрётся, затем возвращается и пробует другие ветви. Реализуется рекурсией или явным стеком. Применяется для поиска компонент, обнаружения циклов и топологической сортировки.

Сложность: время O(V + E); память: O(V) на стек рекурсии и посещённые вершины.

def dfs(graph, start, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(start)
    order.append(start)
    for nb in graph[start]:
        if nb not in visited:
            dfs(graph, nb, visited, order)
    return order