1. Теория. DFS

«Чтобы понять глубину проблемы, нужно идти до самого дна, не отвлекаясь на боковые тропы, пока путь не исчерпает себя».
— Роберт Тарьян

Поиск в глубину (Depth-First Search, DFS) — это фундаментальная стратегия исследования связных структур данных (деревьев, графов, пространственных матриц). В отличие от поиска в ширину (BFS), который распространяется концентрическими волнами, DFS упорно движется вперед вдоль выбранного ребра до тех пор, пока не упрется в лист, тупик или ранее посещенную вершину, после чего откатывается назад к ближайшей развилке.

В предыдущем кластере 1. Теория. Backtracking мы применяли поиск с возвратом к неявным деревьям комбинаторных решений. DFS — это проекция той же парадигмы на физические топологии: структуры *TreeNode, списки смежности графов [][]int и двумерные координатные сетки [][]byte.

Для senior-разработчика на Go алгоритм DFS — это не просто рекурсивный обход, а точный выбор между стеком горутины и явным срезом-стеком, контроль над расходом памяти $O(H)$ против $O(W)$ и понимание механизмов предотвращения циклов.

Архитектура: Три порядка обхода дерева и неявный стек

В бинарных деревьях DFS естественным образом распадается на три канонических порядка в зависимости от момента обработки значения родительского узла относительно его потомков:

1. Preorder (Прямой обход): Узел $\rightarrow$ Левый $\rightarrow$ Правый (клонирование дерева, сериализация).
2. Inorder (Центрированный обход): Левый $\rightarrow$ Узел $\rightarrow$ Правый (для Binary Search Tree возвращает строго отсортированную последовательность).
3. Postorder (Обратный обход): Левый $\rightarrow$ Правый $\rightarrow$ Узел (удаление дерева, вычисление высоты, топологическая сортировка, снизу вверх).

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc

    Root["Корень: 1"]:::entry --> L["Левый: 2"]:::process
    Root --> R["Правый: 3"]:::process

    L --> L1["Лист: 4"]:::success
    L --> L2["Лист: 5"]:::success

    subgraph Stack["Стек рекурсии: Preorder обход (1 -> 2 -> 4 -> 5 -> 3)"]
        direction TB
        S1["Push(1) -> Обработка 1"]:::process
        S2["Push(2) -> Обработка 2"]:::process
        S3["Push(4) -> Обработка 4 -> Pop(4)"]:::process
        S4["Push(5) -> Обработка 5 -> Pop(5) -> Pop(2)"]:::process
        S5["Push(3) -> Обработка 3 -> Pop(3) -> Pop(1)"]:::success
    end
  

Фундаментальное сравнение: DFS против BFS

Выбор между поиском в глубину и ширину определяет архитектуру подсистем ядра, сборщиков мусора и сетевых анализаторов:

Идиоматичные реализации на Go

1. Рекурсивный DFS (Preorder)

Рекурсивный обход компактен, выразителен и использует непрерывный стек горутины:

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// dfsRecursive выполняет прямой обход дерева
// Временная сложность: O(N)
// Пространственная сложность: O(H) памяти стека
func dfsRecursive(root *TreeNode, visit func(int)) {
    if root == nil {
        return
    }
    visit(root.Val)                  // Preorder: обработка узла
    dfsRecursive(root.Left, visit)   // Рекурсивный спуск влево
    dfsRecursive(root.Right, visit)  // Рекурсивный спуск вправо
}

2. Итеративный DFS на плоском слайсе (Zero Allocations)

Если глубина графа неизвестна и может превышать $10^5$ (риск исчерпания памяти стека горутины), идиоматично использовать явный стек на срезе с предвыделенной емкостью:

package main

// dfsIterative эмулирует стек вызовов без рекурсии
func dfsIterative(root *TreeNode, visit func(int)) {
    if root == nil {
        return
    }

    // Стек указателей на узлы с предвыделенной емкостью под высоту дерева
    stack := make([]*TreeNode, 0, 64)
    stack = append(stack, root)

    for len(stack) > 0 {
        // Pop из вершины стека за O(1)
        idx := len(stack) - 1
        node := stack[idx]
        stack = stack[:idx]

        visit(node.Val)

        // В LIFO стеке правый потомок добавляется ПЕРВЫМ,
        // чтобы левый потомок извлекся и обработался РЬШЕ!
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
}

Взгляд под капот: Mechanical Sympathy

1. Непрерывный стек горутины и runtime.morestack

В Go каждая горутина создается с минимальным стеком размером 2 КБ.

• Когда рекурсивный DFS углубляется, компилятор на прологе каждой функции выполняет проверку исчерпания стека (CMPQ SP, 16(R14)).
• Если 2 КБ недостаточно, вызывается рантайм-функция runtime.morestack, которая аллоцирует блок памяти в 4 КБ, копирует существующие стековые кадры и сдвигает указатели.
• Для сбалансированного дерева глубины $H \le 64$ стек горутины даже не превысит стартовые 2 КБ! Вся рекурсия выполняется в горячем кэше первого уровня L1d.

2. Кэш-локальность списков смежности

При обходе графа adj [][]int:

• Использование среза срезов adj[v] обеспечивает строго последовательное чтение номеров соседей из памяти.
• Аппаратный Prefetcher процессора заблаговременно подтягивает смежные индексы в линии кэша, обеспечивая максимальную пропускную способность шины памяти.

Подводные камни и вопросы с собеседований

Резюме

Поиск в глубину (DFS) — базовый инструмент исследования структур:

• Память $O(H)$ делает его непревзойденным выбором для глубоких разветвленных деревьев.
• Рекурсия на стеке горутины в Go сверхэффективна благодаря continuous stacks.
• Итеративный стек на слайсе защищает от переполнения памяти на вырожденных графах.

В следующей статье мы подробно сравним накладные расходы рекурсивного и итеративного подходов: 2. Рекурсия и стек.