2011-gre-cs-practice-book.pdf/Q30

Вопрос: Q30-08c765

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

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

Ответы

• 5, 7, 10, 13, 14, 17, 20, 30
• 10, 5, 13, 14, 7, 30, 17, 20
• 10, 5, 13, 17, 20, 14, 7, 30
• 10, 5, 20, 13, 17, 30, 14, 7
• Правильный ответ: 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.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.