Алгоритми та структури даних · Middle · Запитання 32 з 75
Як алгоритм Кана будує топологічний порядок?
- 1Сортує вершини за назвою й перевіряє ребра
- ✓Правильна відповідь: Раз у раз видаляє вершину без вхідних ребер
- 3Запускає DFS і виводить вершини в порядку першого відвідування
Пояснення
Тримаємо вхідні степені й чергу вершин зі степенем 0. Якщо черга спорожніла раніше, ніж виведено всі вершини, у графі є цикл. Версія на DFS виводить вершини у зворотному порядку завершення, а не відвідування.