Алгоритмы с нуля
Графы: тест с множественным выбором
Суть Синтез по всему юниту графов в виде теста: компромиссы представлений, BFS против DFS, topological sort, инвариант фиксации Dijkstra и union-find.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на senior-высоте — в орбитеШесть вопросов, пронизывающих весь юнит. Каждый выбирает алгоритм или представление, которого реально требует задача, — это не определение для пересказа, а решение по моделированию, которое нужно обосновать.
Цель
Убедитесь, что вы связываете выбор представления, порядок обхода, упорядочивание, кратчайшие пути со весами и динамическую связность — синтез, к которому вели восемь уроков.
Викторина
Completed
В социальном графе 50 миллионов пользователей и ~200 связей у каждого (то есть E порядка 5 миллиардов направленных записей, намного меньше V в квадрате). Горячая операция — «перебрать друзей пользователя». Какое представление и почему?
Heads-up Матрице V на V здесь нужно ~2,5 квадриллиона ячеек — её невозможно хранить. Граф разрежённый (E намного меньше V в квадрате), поэтому adjacency list выигрывает и по памяти, и на самой горячей операции — переборе соседей.
Heads-up edge list компактен, но не умеет перебирать друзей одного пользователя без сканирования всех E рёбер. Для операции «перечислить соседей вершины» это O(E), намного хуже, чем O(degree) у списка.
Heads-up На этом масштабе матрица даже не помещается в память, а перебор соседей — O(V) на матрице против O(degree) на списке. Выбор решающий, а не косметический.
Викторина
Completed
Нужно найти маршрут между двумя точками на карте с наименьшим числом сегментов дороги, игнорируя расстояние. Нужно только число переходов. Какой алгоритм взять первым и что делает его корректным?
Heads-up Dijkstra здесь корректен, но избыточен: при всех весах, равных 1, он вырождается в BFS, платя лишний множитель log V за heap впустую. Для числа переходов первым берут BFS.
Heads-up DFS посещает все достижимые вершины, но в глубину; первый маршрут DFS до вершины не кратчайший. Только порядок BFS по уровням гарантирует наименьшее число рёбер.
Heads-up topological sort упорядочивает DAG по направлению зависимостей; он ничего не говорит о числе переходов и не определён на графе с циклами, а в дорожной сети циклы есть.
Викторина
Completed
Система сборки запускает алгоритм Кана (Kahn) на своём DAG зависимостей, и выходной порядок содержит только 18 из 20 целей сборки. О чём это говорит?
Heads-up Алгоритм Кана никогда не теряет вершину, которую можно законно упорядочить. Короткий вывод — однозначный сигнал: оставшиеся вершины образуют цикл или зависят от него, поэтому корректного порядка для них нет.
Heads-up Вершины с in-degree 0 — ПЕРВЫЕ, кого помещают в очередь и выводят, а не пропускают. Недостающие — наоборот: их in-degree никогда не падает до 0, потому что цикл постоянно их подпитывает.
Heads-up Добавление в конец даёт порядок, нарушающий зависимость, потому что они в цикле и не имеют согласованной позиции. Правильный ответ — сообщить о циклической зависимости, а не сочинять порядок.
Викторина
Completed
В графе цен некоторые рёбра представляют возвраты (отрицательная стоимость). Инженер запускает Dijkstra и иногда получает завышенные ответы. Почему и как это исправить?
Heads-up Heap прекрасно хранит отрицательные числа. Настоящий дефект — инвариант фиксации: settle закрепляет расстояние, которое позднее отрицательное ребро может подрезать. Ошибка алгоритмическая, не числовая.
Heads-up Dijkstra корректно работает на направленных графах. Проблема именно в отрицательных весах, а не в направлении рёбер. Исправление — Bellman-Ford, а не превращение графа в неориентированный.
Heads-up Запуск Dijkstra из каждого источника всё равно применяет сломанный инвариант фиксации на каждом запуске, поэтому отрицательные рёбра по-прежнему дают неверные ответы. Структурное исправление — Bellman-Ford.
Викторина
Completed
Рёбра приходят по одному в потоке, и после каждого нужно мгновенно отвечать «уже ли u и v в одной компоненте?». Какая структура подходит и почему повторный запуск BFS — неверный выбор?
Heads-up Ячейка матрицы говорит лишь о наличии ПРЯМОГО ребра u-v, а не о связности u и v через путь. Достижимость всё равно требует обхода; именно DSU инкрементально отслеживает принадлежность к компоненте.
Heads-up Корректно, но цена — O(V + E) на запрос, повторяемая для каждого приходящего ребра. DSU отвечает на тот же запрос за амортизированное O(alpha(n)) без повторного обхода — ради этого DSU и существует.
Heads-up topological sort упорядочивает DAG; он не отвечает на неориентированную связность и не определён, как только поток вводит цикл. DSU — структура для динамической связности.
Викторина
Completed
Коллега утверждает, что его union-find работает за O(1) на операцию, потому что он добавил path compression. Какова точная сложность и что упущено или преувеличено?
Heads-up Тарьян доказал нижнюю границу alpha(n) для этой структуры, поэтому это доказуемо НЕ истинное константное время на вызов. Честная оценка — амортизированное O(alpha(n)).
Heads-up O(log n) — это оценка для union by rank В ОДИНОЧКУ. С добавленным path compression амортизированная оценка падает ниже до O(alpha(n)). Назвать O(log n) — занизить оптимизированную структуру.
Heads-up path compression УКОРАЧИВАЕТ пути, перенаправляя узлы к корню; он улучшает время, а не ухудшает. O(n) — это цена неоптимизированной вырожденной цепочки, противоположность тому, что даёт сжатие.
Итог
Сквозная линия юнита — одно дерево решений по моделированию: выбирайте представление по плотности (list для разрежённых, matrix для плотных или O(1) поиска ребра); выбирайте обход по нужде (BFS для путей с наименьшим числом рёбер и уровней, DFS для глубины и структуры циклов); добавьте веса — и BFS уступает Dijkstra, но только при неотрицательных рёбрах, иначе Bellman-Ford. topological sort упорядочивает DAG и попутно ловит циклы, а union-find отвечает на динамическую связность за амортизированное O(alpha(n)) там, где повторять BFS было бы расточительно. Подбирайте алгоритм под форму задачи до того, как написать строку кода.