Обход графа BFS / DFS

O(V+E)

Обходим граф от стартового узла, храня множество посещённых, чтобы циклы не зациклили обход навечно: BFS расходится кольцами, давая расстояние в рёбрах, DFS ныряет по одному пути ради достижимости.

Сигналы

кратчайший путь в невзвешенном графеминимальное число шагов/рёбер между узламидостижим ли узел Y из узла Xисследовать кольцо за кольцом / слой за слоемграф задан списком смежности, возможны циклы

Шаблон

function bfsDistances(adj, source) {
    const dist = { [source]: 0 };
    const queue = [source];
    while (queue.length) {
        const node = queue.shift();
        for (const next of adj[node] || []) {
            if (!(next in dist)) {
                dist[next] = dist[node] + 1;
                queue.push(next);
            }
        }
    }
    return dist;
}

Похоже, но не то

Обход дерева: У дерева нет циклов и у каждого узла один родитель, поэтому обычному обходу множество посещённых не нужно. Граф может зациклиться сам на себя, поэтому BFS/DFS обязаны хранить посещённые узлы, иначе обход идёт вечно.

V, E до ~1e5, невзвешенный граф, нужна достижимость или расстояние в рёбрах -> O(V+E): каждый узел и ребро посещаются один раз.

Изучить этот паттерн