Топологическая сортировка + динамическое программирование.
ДАГ (DAG) — ориентированный граф без циклов. Главное свойство: можно топологически отсортировать вершины. На этом основан алгоритм подсчёта путей за O(V+E).
В логических схемах сигнал проходит от входов к выходу, и важно найти путь (или все пути), которые сигнал может пройти. В главе 17.2 вы научились описывать граф и считать степени вершин. Теперь — следующий шаг: в графах без циклов (ДАГ) можно точно посчитать, сколько существует путей из одной точки в другую. Это нужно для анализа сложности схем, подсчёта вариантов сборки проекта, планирования последовательности задач. ДАГ — основа для понимания того, как работают проекты сборки (make, npm), как устроены криптовалюты без блокчейна (IOTA, Nano), как планируются вычисления в нейросетях.
Какие файлы должны быть собраны до других. Порядок зависимостей.
Вместо линейной цепочки — граф транзакций. Быстрее и масштабируемее.
Слои нейросети — вершины, зависимости по данным — рёбра.
Критический путь, анализ сроков. ДАГ помогает планировать.
ДАГ (Directed Acyclic Graph) — ориентированный граф, в котором нет циклов.
Топологическая сортировка — линейное упорядочивание вершин, в котором каждое ребро u→v идёт «вперёд» (u раньше v).
Существует тогда и только тогда, когда граф — ДАГ.
Рёбра: 1→2, 1→3, 2→4, 2→5, 3→5, 4→6, 5→6.
Топсорт: 1, 2, 3, 4, 5, 6 (один из вариантов).
ДАГ (Directed Acyclic Graph) — ориентированный граф без циклов. Это значит, что顺着 рёбрам можно дойти от любой вершины только в одном направлении, и зацикливание невозможно.
В информатике ДАГ используется для:
Пусть dp[v] — количество путей от стартовой вершины s до вершины v.
Алгоритм: находим вершины с in-degree = 0, добавляем в очередь, удаляем их рёбра, повторяем. Результат — порядок, при котором все предки любой вершины уже обработаны.
Время: O(V + E) — один проход по всем вершинам и рёбрам. Память: O(V) для хранения dp.
Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных во взвешенном графе без отрицательных рёбер.
1. dist[s]=0, остальным =∞
2. Повторять:
a) выбрать необработанную вершину с мин dist
b) пометить её обработанной
c) для каждого ребра u→v с весом w:
если dist[u]+w < dist[v]:
dist[v] = dist[u]+w
prev[v] = u
3. Повторять пока очередь не пуста