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

Тот же граф, другой обход

Вершины A–H; неориентированные рёбра AB, AC, BD, BE, CE, CF, DG, EG и FG. H изолирована. Изначально старт — A, цель — F. Граф и порядок соседей совпадают с примером BFS.

Сначала одна ветка, потом следующая

DFS сразу входит в ещё не обнаруженного соседа. Текущий вызов приостанавливается, пока не завершатся этот сосед и все его потомки. Только затем вызов продолжает проверку следующего соседа. Граф остаётся неподвижным: длина линии на рисунке не влияет на обход.

Визуализатор использует явные кадры вызовов, а не стек JavaScript. Каждый кадр хранит вершину и число уже проверенных соседей. Порядок совпадает с рекурсивным DFS при тех же списках смежности. Если просто положить в стек всех соседей сразу, дерево обхода может получиться другим.

Стек — текущая ветка обхода

В стеке находятся ровно незавершённые вызовы от старта до текущей вершины. На вершине стека — текущий вызов, остальные приостановлены. Отмечаем вершину обнаруженной до добавления кадра, поэтому входим в неё не более одного раза, даже при наличии цикла.

Указатель соседа в кадре увеличивается до входа в потомка. После возврата продолжаем со следующего соседа, а не проверяем одно ребро бесконечно. Завершённые вершины остаются обнаруженными, их предки не меняются. Страница обходит только компоненту старта, а не лес всех компонент графа.

Вход, приостановка, возврат

В исходном примере порядок обнаружения: A, B, D, G, E, C, F. В момент входа в F стек равен A, B, D, G, E, C, F. Все соседи F уже обнаружены: завершаем F и возвращаемся в C, затем в E и приостановленные вызовы выше. Порядок возвратов: F, C, E, G, D, B, A.

Обход обнаруживает и завершает 7 вершин и проверяет 18 записей соседей: каждое из 9 неориентированных рёбер достижимой компоненты читается с двух концов. Максимум стека — 7 кадров, включая A на глубине ноль. Восстановление пути эти счётчики не меняет. H остаётся необнаруженной; недостижимой её можно считать только после окончания обхода.

Шесть рёбер у DFS, два у BFS

Цепочка предков до F даёт A → B → D → G → E → C → F: 6 рёбер. Но существует A → C → F всего из 2 рёбер. DFS первым построил допустимый путь, а не кратчайший. Глубина 6 — положение F в этом дереве DFS, а не кратчайшее расстояние в графе.

Откройте связанный пример BFS, оставьте тот же граф и выберите цель F. BFS получит расстояние 2. Порядок соседей может изменить дерево DFS, глубины и длину пути; BFS всё равно гарантирует минимум рёбер в невзвешенном графе.

Плеер полностью обходит достижимую компоненту и затем идёт по предкам от цели к старту. При восстановлении зелёный частичный путь направлен обратно, окончательный — от старта к цели. Выберите H для недостижимой цели, сам старт для пути из нуля рёбер или «Без цели» только для обхода.

Память алгоритма и история плеера

Со списками смежности обход занимает O(V + E) времени, включая инициализацию записей всех вершин. Явный стек, состояния, глубины и предки требуют O(V) дополнительной памяти; хранение графа — O(V + E). Восстановление пути в худшем случае требует O(V) времени и памяти результата. У рекурсивного DFS такая же асимптотика стека вызовов, но можно упереться в ограничение глубины рекурсии среды.

Визуализатор дополнительно сохраняет O(V + E) неизменяемых снимков с O(V) данными вершин и стека в каждом. История требует O(V(V + E)) памяти плюс общий граф. Пресеты до восьми вершин ограничены читаемостью сцены, а не возможностями DFS.

Реализация на JavaScript

Код принимает корректный простой неориентированный граф как Map от id к упорядоченному массиву соседей, существующий старт и необязательную существующую цель. Он не меняет вход и совпадает с плеером по порядку обнаружения и возвратов, предкам, глубинам и счётчикам. Плеер дополнительно проверяет и копирует граф перед созданием снимков.

function depthFirstSearch(adjacency, start, target = null) {
    // A valid undirected graph: Map<vertexId, vertexId[]>.
    const depth = new Map([...adjacency.keys()].map(id => [id, null]));
    const parent = new Map([...adjacency.keys()].map(id => [id, null]));
    const order = [start], finishOrder = [];
    const stack = [{ vertex: start, nextNeighbor: 0 }];
    depth.set(start, 0);
    let edgeChecks = 0, maxStackSize = 1;

    while (stack.length) {
        const call = stack[stack.length - 1];
        const neighbors = adjacency.get(call.vertex);
        if (call.nextNeighbor === neighbors.length) {
            finishOrder.push(call.vertex);
            stack.pop();
            continue;
        }
        const neighbor = neighbors[call.nextNeighbor++];
        edgeChecks++;
        if (depth.get(neighbor) !== null) continue;
        parent.set(neighbor, call.vertex);
        depth.set(neighbor, depth.get(call.vertex) + 1);
        order.push(neighbor);
        stack.push({ vertex: neighbor, nextNeighbor: 0 });
        maxStackSize = Math.max(maxStackSize, stack.length);
    }

    const path = [];
    if (target !== null && depth.get(target) !== null) {
        for (let id = target; id !== null; id = parent.get(id)) path.push(id);
        path.reverse();
    }
    return { depth, parent, order, finishOrder, path, edgeChecks, maxStackSize };
}

Когда выбирать DFS

DFS полезен для проверки достижимости, поиска компонент связности и исследования ветвей. Для обнаружения циклов, топологической сортировки ориентированного ациклического графа и поиска сильно связанных компонент нужна дополнительная логика; этот пример её не реализует. В неориентированном графе уже обнаруженный сосед может быть просто предком, поэтому пропуск сам по себе не означает обнаружение цикла.

Для минимального числа рёбер в невзвешенном графе выбирайте BFS. Для минимальной суммарной стоимости ни этот DFS, ни обычный BFS не работают с произвольными весами. Обход определён на сайте; AlgiViz предоставляет оболочки неизменяемых шагов, временную шкалу и пользовательские объекты сцены.

Связанные материалы