Page 149 - Bkhargava_-_Grokaem_algoritmy

148 Глава 6. Поиск в ширину

6.3 Для каждого из следующих трех списков укажите, действителен он
или недействителен.

Б

1. ПРОСНУТЬСЯ 1. ПРОСНУТЬСЯ 1. ПРИНЯТЬ .П.УШ
l. ПРИНЯТЬ дУШ l. ПОЧИСТИТЬ ЗУБЫ L. ПРОСНУТЬСЯ
3. ПОЗАВТРАКАТЬ 3. ПОЗАВТРАКАТЬ 3. ПОЧИСТИТЬ ЗУБЫ
4. ПОЧИСТИТЬ ЗУБЫ 4. ПРИНЯТЬ .П.УШ 4. ПО.ЗАВТРАКАТЬ

6.4 Немного увеличим исходный граф. Постройте действительный список
для этого графа.

Можно сказать, что этот список в некотором смысле отсортирован. Если
задача А зависит от задачи В, то задача А находится в более поздней по­
зиции списка. Такая сортировка называется топологической; фактически
она предоставляет способ построения упорядоченного списка на основе
графа. Предположим, вы планируете свадьбу и у вас составлен большой
граф с множеством задач, но вы не знаете, с чего начать. Проведите топо­
логическую сортировку графа - и получите список задач, которые можно
выполнять одну за другой.

www.trk.kg