Порядок зависимостей и поиск цикла

Топологический порядок ориентированного ациклического графа либо конкретный замкнутый путь, мешающий такому порядку.

Ваш пример

До 40 вершин и 120 строк рёбер. Петля является циклом; вершина за циклом не обязательно сама входит в него.

Разбор примера

1 → 2 → 3 → 4 → 5

Один допустимый порядок
ПозицияВершина
11
22
33
44
55
  1. На каждом шаге выбираем вершину без оставшихся предшественников.
  2. Каждое исходное ребро направлено от более ранней вершины к более поздней.
Число вершин
5

Метод и условия расчёта

Алгоритм Кана удаляет вершины с нулевой входной степенью. Если удалены не все, поиск в глубину находит реальный ориентированный цикл.

Вопросы по теме

Что означает ребро u → v?

Действие u должно предшествовать v. Это зависимость, а не длительность и не ресурсный план.

Порядок всегда единственный?

Нет. Из доступных вершин выбираем наименьший номер, чтобы результат был воспроизводимым.

Графы и маршруты: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.