18. Топологическая сортировка. Временная сложность алгоритма.

 

До сих пор мы сортировали последовательности, элементы которых принадлежали полностью упорядоченному множеству, т.е. любые два элемента были сравнимы по ключу. Перейдем к рассмотрению последовательности, элементы которой принадлежат частично упорядоченному множеству. Это значит, что в ней обязательно найдется такая пара элементов a[i] и a[j] (i<>j), что a[i] и a[j] не сравнимы.

            Цель топологической сортировки - преобразовать частичный порядок в полный. Например, в условиях пр-ра 2 топологическая сортировка позволяет построить университетскую программу таким образом, что ни один курс не читается ранее тех, которые его поддерживают.

Основная идея топологической сортировки

            Поместим все сортируемые элементы в множество S. Среди этих элементов обязательно найдется хотя бы один элемент, не имеющий предшественников (если таких элементов нет, то либо сортируемая последовательность бесконечна, либо в соответствующем орграфе содержится цикл, что противоречит наличию отношения предшествования на множестве S). Элемент без предшественников помещается в голову результирующего списка R и вычеркивается из множества S. Из орграфа при этом удаляется соответствующая вершина со всеми инцидентными ей ребрами. К оставшемуся множеству S применяется тот же алгоритм до тех пор, пока оно не станет пустым.

            Пример. Реализуем этот алгоритм для орграфа на рис. 3.8.

            Шаг 0. S={САОД, ДМ, П, ФЛП}; R=ПУСТОМУ_МНОЖЕСТВУ. Первый встретившийся в S элемент без предшественников - ДМ.

            Шаг 1. S={САОД, П, ФЛП}; R={ДМ}. Первый встретившийся в S элемент без предшественников - П.

            Шаг 2. S={САОД, ФЛП}; R={ДМ, П}. Первый встретившийся в S элемент без предшественников - САОД.

            Шаг 3. S={ФЛП}; R={ДМ, П, САОД}. Первый встретившийся в S элемент без предшественников - ФЛП.

            Шаг 4. S=ПУСТОМУ_МНОЖЕСТВУ; R={ДМ, П, САОД, ФЛП}.

            Для этого алгоритма T(n)=O(n+m), где n - количество вершин соответствующего орграфа, а m - количество его ребер.

            Познакомимся подробнее с конкретной реализацией процедуры топологической сортировки. На фазе ввода создается списочная нелинейная структура, содержащая список лидеров и списки ведомых.             Элемент списка лидеров содержит четыре поля:

                        1. наименование (имя) элемента;

                        2. количество предшественников у этого элемента;

                        3. указатель на следующий элемент в списке лидеров;

                        4. указатель на первого ведомого.

            Элемент списка ведомых содержит два поля:

                        1. указатель на “себя” в списке лидеров;

                        2. указатель на следующего ведомого.

            Рис. 3.9.

 

            Нелинейная структура формируется в результате следующих действий. Пусть введена пара (y,z), означающая, что y<z. После этого необходимо:

            1. найти элементы с именами y и z в списке лидеров. Если одного из них (или обоих) там нет, то в список лидеров добавить отсутствующий элемент;

            2. в список ведомых элемента с именем y добавить элемент, идентифицирующий z;

            3. счетчик предшественников элемента с именем z увеличить на единицу.

            Пример. Пусть пары курсов (см. рис. 3.8) введены в следующем порядке:

(ДМ,САОД), (ДМ,ФЛП), (САОД,ФЛП), (П,САОД), (П,ФЛП).

На рис. 3.9 показана списочная структура, полученная в результате ввода этих данных.

 

            После того, как необходимая структура построена, можно приступать непосредственно к сортировке. Поскольку она будет состоять из повторяющихся выборов элемента с нулевым числом предшественников, все такие элементы помещают в стек FILO. Нет необходимости занимать место в памяти ЭВМ под этот стек. Дело в том, что список лидеров использовался только для правильного построения списка ведомых. Учитывая это обстоятельство, то же самое третье поле элемента в списке лидеров (указатель на следующий элемент) можно повторно использовать для образования стека FILO, хранящего элементы без предшественников.

            Формирование выходной последовательности включает в себя следующие действия:

            1. Взять верхний элемент из стека FILO.

            2. Вывести на печать имя y этого элемента.

            3. Уменьшить на единицу мощность множества S.

            4. У всех ведомых элемента с именем y уменьшить на единицу их счетчики количества предшественников в списке лидеров.

            5. Если счетчик некоторого элемента стал равен нулю, “кладем” этот элемент в стек FILO.

            Полный текст процедуры, реализующей топологическую сортировку, можно найти, например, в [2]. Здесь он не приводится ввиду большого объема.