2011-gre-cs-practice-book.pdf/Q30 — различия между версиями

Версия 17:53, 19 декабря 2024

Вопрос: Q30-08c765

Дан ориентированный граф:

Что из перечисленного является топологической сортировкой вершин графа[1]?

Ответы

1. 5, 7, 10, 13, 14, 17, 20, 30
2. 10, 5, 13, 14, 7, 30, 17, 20
3. 10, 5, 13, 17, 20, 14, 7, 30
4. 10, 5, 20, 13, 17, 30, 14, 7
5. Правильный ответ: 10, 20, 5, 17, 13, 14, 7, 30

Объяснение

Исходники — вопрос 30 на 29 странице книги «2011-gre-cs-practice-book.pdf»

Начнём с конца, с вершины, из которой нет ни одного исходящего ребра. Она здесь единственная, это 30. Далее можно пойти либо в 7, либо в 20. Но из 20 можно попасть 7, значит эта вершина стоит раньше. Тогда идем выбираем 7. Та же дилемма между 14 и 17. Видно, что из 14 можно попасть в 17, но не наоборот. Пойдём так дальше до 13. Получили 13-14-7-30. Из 13 опять вилка - либо 5, либо 17. Но 5 идет раньше 17, поэтому получим 5-17-13-14-7-30. Далее очевидный выбор между 10 и 20. Получили 10-20-5-17-13-14-7-30. Решено: Urmat A 15:49, 19 декабря 2024 (UTC)