Поиск в глубину (DFS) обходит граф как лабиринт: идёт по одному пути как можно глубже, а в тупике возвращается и пробует следующий. Ему нужны две вещи: множество посещённых вершин (иначе в графе с циклами он зациклится) и стек, который помнит, куда возвращаться. Графы хранятся как в теме Представление графов; в примерах словарь списков смежности.

След DFS из A: порядок посещения A B D E F C, рёбра дерева и одно обратное ребро
След DFS из A: порядок посещения A B D E F C, рёбра дерева и одно обратное ребро

Рекурсивный DFS

visit(u) помечает вершину, затем вызывает себя для каждого ещё не посещённого соседа. Порядок соседей определяет порядок обхода.

python
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

def dfs(graph, start):
    visited = set()
    order = []

    def visit(u):
        visited.add(u)                    # mark on entry
        order.append(u)
        for v in graph[u]:
            if v not in visited:
                visit(v)

    visit(start)
    return order

print(dfs(graph, "A"))
text
['A', 'B', 'D', 'E', 'F', 'C']

Здесь D — тупик: DFS возвращается в B и продолжает с E. Ребро A-C не используется: когда DFS доходит до C из F, вершина A уже посещена (обратное ребро). Жирные рёбра образуют дерево DFS.

Итеративный DFS со стеком

Стек рекурсии можно заменить своим: pop берёт последнюю добавленную вершину (LIFO). Если класть соседей через reversed, порядок обхода совпадёт с рекурсивным.

python
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}