Алгоритмы с нуля
Графы: чтение кода и багов
Суть Читайте код графа и лог сборки, предсказывайте поведение и выбирайте самое результативное исправление: баг с visited-set, баг расстояний в BFS, Dijkstra на отрицательных рёбрах и цикл в topological sort.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на senior-высоте — в орбитеБаги в графах прячутся в том, где вы помечаете вершину, из какой очереди извлекаете и каким весам доверяете. Прочтите каждый фрагмент, предскажите его поведение на циклическом или взвешенном графе и выберите исправление, которое senior-инженер сделает первым.
Цель
Отработайте цикл, который вы запускаете на каждом дефекте графа: проследите фрагмент на маленьком циклическом или взвешенном примере, найдите нарушенный инвариант и возьмите наименьшее корректное исправление.
Фрагмент 1 — DFS, который зависает
function dfs(v, adj, visited) {
for (const w of adj[v]) { // пометка — ПОСЛЕ рекурсии ниже
if (!visited.has(w)) {
dfs(w, adj, visited);
}
}
visited.add(v); // помечается только на выходе
}
// в adj есть цикл: { 0: [1], 1: [2], 2: [0] } Викторина
Completed
Запустите это на циклическом графе 0->1->2->0, начиная с 0. Что произойдёт и как исправить?
Heads-up PUSH в post-order для topo sort происходит после того, как вход тоже защищён проверкой visited в начале. Здесь пометки на входе нет вообще, поэтому цикл вечно входит в 0 заново. Помечайте на входе, чтобы предотвратить повторный вход.
Heads-up Он никогда не завершается: без пометки до рекурсивного вызова 0->1->2->0->1->2... рекурсирует без предела, пока не переполнится стек. Пометка должна предшествовать циклу по соседям.
Heads-up Set — вполне корректная структура visited. Дефект во времени пометки — после рекурсии вместо до неё, — а не в типе данных.
Фрагмент 2 — BFS кратчайшего пути, дающий неверные расстояния
function bfs(src, adj) {
const dist = { [src]: 0 };
const queue = [src];
while (queue.length) {
const v = queue.shift();
for (const u of adj[v]) {
dist[u] = dist[v] + 1; // ставим каждый раз, когда видим u
queue.push(u); // и ставим в очередь каждый раз
}
}
return dist;
} Викторина
Completed
На графе, где у вершины несколько входящих рёбер, этот BFS завышает расстояния и может не завершиться на цикле. В чём именно баг?
Heads-up Сосед на одно ребро ДАЛЬШЕ от источника, поэтому dist[v] + 1 верно. Настоящий баг — отсутствие проверки «уже посещён», из-за которой поздние длинные приходы перезаписывают первый (кратчайший).
Heads-up Обычный BFS вычисляет корректные невзвешенные кратчайшие пути именно потому, что первое достижение — кратчайшее, но только если защищаться от повторного посещения. Алгоритм верен; в этой реализации забыли защиту.
Heads-up shift() уже удаляет из НАЧАЛА (FIFO), что верно для BFS. Извлечение из конца сделало бы это стеком (DFS). Баг — отсутствие проверки visited, а не конец очереди.
Фрагмент 3 — Dijkstra на графе с ребром-возвратом
// adj как [сосед, вес]: A:[[B,1]], B:[[C,-3]], A:[[C,4]]
// settled — Set; как только вершину извлекли, она окончательна
const [d, u] = heap.pop();
if (settled.has(u)) continue;
settled.add(u); // расстояние u ЗАФИКСИРОВАНО здесь
for (const [v, w] of adj[u]) {
if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; heap.push([dist[v], v]); }
} Викторина
Completed
С ребром B->C веса -3 Dijkstra фиксирует C через A->C (стоимость 4) до того, как обнаружит A->B->C (стоимость 1 + (-3) = -2). В чём корневая причина и какое исправление верное?
Heads-up Смена знака меняет задачу: возврат -3 не то же самое, что стоимость +3, и кратчайшие пути станут неверными. Отрицательные рёбра требуют алгоритма, который их допускает (Bellman-Ford), а не трюка со знаком.
Heads-up Релаксация зафиксированных вершин ломает гарантии завершения и всё равно не даёт корректного доказательства кратчайшего пути при отрицательных весах — может зациклиться на отрицательном цикле. Структурный ответ — Bellman-Ford, а не снятие проверки.
Heads-up Использование <= лишь добавляет избыточные обновления при равной стоимости; оно не восстанавливает инвариант фиксации при отрицательных рёбрах. Проблема — отрицательные веса против Dijkstra, решается Bellman-Ford.
Фрагмент 4 — topological sort, возвращающий мусор на цикле
function topo(adj) {
const inDeg = {};
for (const v in adj) inDeg[v] = 0;
for (const v in adj) for (const w of adj[v]) inDeg[w]++;
const q = Object.keys(adj).filter(v => inDeg[v] === 0);
const order = [];
while (q.length) {
const v = q.shift(); order.push(v);
for (const w of adj[v]) if (--inDeg[w] === 0) q.push(w);
}
return order; // возвращает order безусловно
}
// adj = { a:[b], b:[c], c:[a], d:[a] } // a->b->c->a — цикл Викторина
Completed
На этом графе (a->b->c->a — цикл, плюс d->a) что вернёт topo и какое исправление верное?
Heads-up Алгоритм Кана даёт полный порядок только для DAG. Здесь цикл a->b->c->a держит эти три на ненулевом in-degree, поэтому выводится только d. Функция должна распознать короткий вывод как цикл.
Heads-up У d in-degree 0 (на d ничто не указывает), поэтому d выводится. Результат — частичный ['d'], а не пустой. Исправление — проверка по числу оставшихся (leftover count), а не предположение о пустом результате.
Heads-up Ничто не бросается — цикл while просто опустошает очередь и выходит с частичным порядком. Опасность как раз в том, что он падает МОЛЧА; проверку order.length < V нужно добавить самому.
Итог
Каждый фрагмент нарушил один инвариант. DFS должен помечать вершину на ВХОДЕ, до рекурсии, иначе цикл входит снова вечно. BFS кратчайшего пути должен защищать первое достижение (пометка на enqueue), чтобы более длинный поздний маршрут не перезаписал кратчайший. Шаг фиксации Dijkstra верен только при неотрицательных весах; отрицательное ребро означает Bellman-Ford. А topological sort по Кану должен проверять число оставшихся — короткий вывод это цикл, а не корректный порядок. Проследите на крошечном циклическом или взвешенном графе, назовите нарушенный инвариант и примените наименьшее исправление.