Ориентированные графы
Рёбра имеют направление (дуги). Степени входа/выхода вершин. Применение: сети (интернет, дороги с односторонним движением), зависимости (таск-менеджеры). Алгоритмы: топологическая сортировка (Kahn, 1962), поиск сильно связных компонент (Tarjan, 1972).
Ориентированные графы
DAG (Направленный ациклический граф)
Ориентированный граф без циклов. Основа: Git (коммиты), блокчейн (IOTA), зависимости пакетов (npm), Apache Spark (вычислительный граф).
Топологическая сортировка и циклы
Для ориентированных ациклических графов строят топологический порядок, полезный в задачах зависимостей. Наличие циклов меняет класс задач и требует алгоритмов поиска сильно связанных компонентов.