☕ Java 🟣 Kotlin
Карта / Деревья и графы / BFS / DFS

BFS / DFS

BFS и DFS — два способа обойти дерево или граф, отличаются порядком, в котором посещают узлы.

DFS (поиск в глубину) — идёт вглубь до конца, потом возвращается. Использует стек (часто — рекурсию, она сама работает через стек вызовов):

void dfs(Node node, Set<Node> visited) {
    if (node == null || visited.contains(node)) return;
    visited.add(node);
    System.out.println(node.value);
    for (Node neighbor : node.neighbors) {
        dfs(neighbor, visited);
    }
}

BFS (поиск в ширину) — обходит слой за слоем, сначала всех соседей, потом соседей соседей. Использует очередь:

void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    queue.offer(start);
    visited.add(start);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.println(node.value);
        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}
DFS: 1→2→4 (вглубь), потом 1→3 1 2 3 4 
<text x="340" y="14" text-anchor="middle" font-size="11" fill="currentColor" opacity="0.6">BFS: 1, потом 2,3 (слой), потом 4</text>
<circle cx="340" cy="34" r="16" fill="#16a34a" fill-opacity="0.15" stroke="#16a34a" stroke-opacity="0.6"/><text x="340" y="39" text-anchor="middle" font-size="12" fill="currentColor">1</text>
<circle cx="300" cy="74" r="16" fill="#16a34a" fill-opacity="0.15" stroke="#16a34a" stroke-opacity="0.6"/><text x="300" y="79" text-anchor="middle" font-size="12" fill="currentColor">2</text>
<circle cx="380" cy="74" r="16" fill="#16a34a" fill-opacity="0.15" stroke="#16a34a" stroke-opacity="0.6"/><text x="380" y="79" text-anchor="middle" font-size="12" fill="currentColor">3</text>
<circle cx="300" cy="114" r="16" fill="currentColor" fill-opacity="0.1" stroke="currentColor" stroke-opacity="0.5"/><text x="300" y="119" text-anchor="middle" font-size="12" fill="currentColor">4</text>
Копнуть глубже

Когда что выбрать:

  • BFS — когда нужен кратчайший путь в невзвешенном графе (количество шагов), или нужно обойти “ближайшее окружение” сначала (например, друзья друзей в соцсети).
  • DFS — когда нужно проверить достижимость (есть ли путь вообще), найти все варианты/комбинации (backtracking), или когда важна простота реализации через рекурсию.

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

Сложность обоих — O(V + E): посещаем каждый узел (V — vertices, вершины) и каждое ребро (E — edges) по одному разу.

🎤 Закрыл тему, если можешь объяснить:
• разницу BFS (очередь, слоями) и DFS (стек/рекурсия, вглубь);
• когда выбрать BFS, а когда DFS, и зачем нужен `visited` (если дошёл до 2-го слоя).