Порядок зависимостей и поиск цикла
Топологический порядок ориентированного ациклического графа либо конкретный замкнутый путь, мешающий такому порядку.
Ваш пример
Разбор примера
1 → 2 → 3 → 4 → 5
| Позиция | Вершина |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
- На каждом шаге выбираем вершину без оставшихся предшественников.
- Каждое исходное ребро направлено от более ранней вершины к более поздней.
- Число вершин
- 5
Метод и условия расчёта
Алгоритм Кана удаляет вершины с нулевой входной степенью. Если удалены не все, поиск в глубину находит реальный ориентированный цикл.
Вопросы по теме
Что означает ребро u → v?
Действие u должно предшествовать v. Это зависимость, а не длительность и не ресурсный план.
Порядок всегда единственный?
Нет. Из доступных вершин выбираем наименьший номер, чтобы результат был воспроизводимым.
Графы и маршруты: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.