Алгоритмы с нуля
Графы: соберите движок зависимостей и маршрутизации
Читать про графовые алгоритмы — не то же самое, что собрать их в одну систему, которая обязана выбирать правильный инструмент под каждый запрос. Соберите небольшой движок, который один раз загружает граф, а затем отвечает на вопросы об упорядочивании, достижимости и кратчайших путях, выбирая BFS, Dijkstra, алгоритм Кана или union-find под каждый запрос и доказывая каждый ответ.
Превратите алгоритмы юнита в один композируемый движок: выберите представление, реализуйте обход, упорядочивание, взвешенные и невзвешенные кратчайшие пути с восстановлением пути и динамическую связность, затем проверьте каждое на графах, провоцирующих сбойные режимы (циклы, отрицательные рёбра, несвязные компоненты).
Соберите графовый движок, который загружает направленный, опционально взвешенный граф и отвечает на четыре типа запросов — topological order, невзвешенный кратчайший путь, взвешенный кратчайший путь и динамическая связность — каждый правильным алгоритмом и с проверяемым результатом, включая корректные отказы, когда алгоритм неприменим.
- Таблица результатов: для выбранных источника и цели — кратчайший путь BFS (и его число рёбер) рядом с кратчайшим путём Dijkstra (и его суммарной стоимостью), с конкретными последовательностями вершин, восстановленными из parent[], а не вручную.
- topological sort возвращает корректный полный порядок на DAG (каждое ребро направлено вперёд в списке, проверено программно) и корректно отказывает с множеством застрявших вершин на циклическом тестовом графе.
- Dijkstra отказывает на графе с отрицательным ребром с понятным сообщением, называющим Bellman-Ford, и даёт верные расстояния на неотрицательном графе (сверено с разобранным вручную маленьким примером).
- Union-Find корректно отвечает на сценарную последовательность запросов union/connected, счётчик компонент уменьшается ровно на один за каждый успешный union и не меняется на избыточном union, а find «почти O(1)» после сжатия (покажите длину пути до и после find).
- Абзац-вывод, называющий для каждого из четырёх типов запросов, какой алгоритм вы использовали и единственное свойство, сделавшее его корректным (уровневый порядок BFS, инвариант фиксации Dijkstra, проверка цикла по остатку в алгоритме Кана, связность через корень в DSU).
- Добавьте Bellman-Ford как пятый путь запроса, чтобы движок обрабатывал отрицательные рёбра и сообщал об отрицательном цикле при его наличии; маршрутизируйте запросы между Dijkstra и Bellman-Ford автоматически по тому, есть ли отрицательное ребро.
- Добавьте режим сетки: трактуйте 2D-сетку из открытых/закрытых клеток как неявный граф с 4-направленными соседями и отвечайте на поиск пути с наименьшим числом шагов через BFS, восстанавливая маршрут.
- Добавьте Kruskal's minimum spanning tree, используя ваш Union-Find для отклонения рёбер, замыкающих цикл, и сравните его суммарный вес с исходным графом.
- Замерьте adjacency list против adjacency matrix на разрежённом и плотном графе для одинаковых нагрузок перебора соседей и поиска ребра и подтвердите, что точка перелома совпадает с предсказанием O(V + E) против O(V в квадрате).
Это инженерный цикл за реальными графовыми системами: смоделируйте граф один раз с представлением под его плотность, затем маршрутизируйте каждый запрос к алгоритму, чей инвариант отвечает на вопрос — BFS для наименьшего числа рёбер, Dijkstra для неотрицательной стоимости, алгоритм Кана для порядка зависимостей, union-find для динамической связности — и отказывайте чисто, когда алгоритм неприменим (отрицательные рёбра, циклы). Восстанавливайте конкретные пути из parent[] и проверяйте каждый ответ, а не утверждайте его. Собрав это однажды, вы превращаете отдельные уроки юнита в один рефлекс принятия решений.