Лекция 22. Топологическая сортировка (Электронные лекции)

Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.Лекция 22 Топологическая сортировка.22.1. Представление произвольного дерева в виде двоичного.22.1.1. В отличие от двоичного дерева произвольное дерево не может быть пустым (поопределению оно должно содержать хотя бы один узел – корень).

Каждый узелпроизвольного дерева может иметь 0, 1, 2, 3 и более детей.Поддеревья любого узла произвольного дерева образуют лес (лесом называетсяупорядоченный набор 0, 1, 2, и более деревьев).22.1.2. Существует естественный способ представления любого леса в виде двоичногодерева. Пример лес из двух деревьев, представленный на рисунке 1 можно представитьв виде двоичного дерева (рисунок 2).Такое приведение леса к двоичному деревусоответствием между лесом и двоичными деревьями.называетсяестественным1(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.22.1.3.

Определение. Пусть F = (T1, T2, …, Tn) – некоторый лес деревьев. Тогда двоичноедерево B(F), соответствующее F, можно определить следующим образом:(1) Если n = 0, то B(F) – пустое дерево.(2) Если n > 0, то корнем B(F) = B(T1, T2, …, Tn) является корень дерева T1, левымподдеревом B(F) является B(T11, T12, …, T1m), где T11, T12, …, T1m – поддеревья корняT1 (лес), правым поддеревом B(F) является B(T2, …, Tn).22.1.4. Для B(F) можно построить прошитое дерево (B(F) можно «прошить»). Прошитоедерево, соответствующее двоичному дереву с рисунка 6(а), представлено на рисунке 3.Отметим, что правые нити всегда проходят от младшего (крайнего справа) ребенка кего родителю.

Левые нити не имеют такой естественной интерпретации из-заотсутствия симметрии между левой и правой сторонами дерева.22.1.5. Идеи обхода двоичных деревьев можно применить к произвольным деревьям (илесам). К сожалению, отсутствие симметрии при отображении леса на двоичноедерево не позволяет легко сформулировать симметричный обход. Но прямой (preorder)и обратный (postorder) обходы можно перенести без всяких затруднений.22.1.5.1. Прямой обход леса (произвольного дерева).(1) Обработать корень первого дерева (T1).(2) Обойти поддеревья первого дерева (T11, T12, …, T1m).(3) Обойти остальные поддеревья (T2, …, Tn).22.1.5.2. Обратный обход леса (произвольного дерева).(1) Обойти поддеревья первого дерева (T11, T12, …, T1m).(2) Обработать корень первого дерева (T1).(3) Обойти остальные поддеревья (T2, …, Tn).22.1.5.3. Пример.Лес с рис.

5 можно представить с помощью следующей скобочной записи:(A(B, C(K)), D(E(H), F(J), G)). При прямом обходе узлы двух деревьевобходятся в порядке A B C K D E H F J G. Последняя последовательностьидентична скобочной записи, если из нее удалить скобки и узлы.2(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.Прямой порядок обхода называется также династическим, так как с помощьютакого обхода генеалогического дерева династии определяется наследникпрестола.При обратном порядке обхода каждый узел располагается после своихнаследников, что приводит к следующей скобочной структуре: ((B, K(C))A,(H(E), J(F), G)D).

Порядок обхода в этом случае будет: B K C A H E J F G D.Таким образом, обход леса в прямом порядке выполняется точно так, какобход соответствующего двоичного дерева в прямом порядке. Обход леса вобратном порядке выполняется точно так, как симметричный обходсоответствующего двоичного дерева (обратите внимание!).Следовательно, можно без изменений использовать алгоритмы (функции)Inorder() и Next_in().22.1.5.4.

Пример.Правую часть формулы y = 3 ⋅ ln( x + 1) − a / x 2 можно представить в видедерева (рисунок 4). Отметим, что хотя это дерево очень похоже на двоичное,здесь оно рассматривается как обычное дерево. Для этого дерева можнопостроить прошитое двоичное дерево (оно показано на рисунке 5).Это дерево содержит дополнительный узел y, являющийся заголовкомпрошитого двоичного дерева.3(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.При обходе узлов двоичного дерева, показанного на рисунке 9, получим:× 3 ln + x 1 / a ↑ x 2для обратного обхода 3 x 1 + ln × a x 2 ↑ / –для прямого обхода –(1)(2)Полученные алгебраические выражения называются бесскобочной польскойзаписью алгебраических выражений; при этом (1) называется префиксной(или прямой) польской записью, а (2) – постфиксной (или обратной) польскойзаписью.

Название связано с тем, что такая запись была впервые использованапольским математиком Яном Лукасевичем.Представление выражений в виде польской записи или в виде дерева,представленного на рисунке 9, используются в компиляторах, а также всистемах символьного преобразования выражений (например, в системахсимвольного дифференцирования, символьного интегрирования, символьногопреобразования алгебраических выражений и т.п.).22.2. Топологическая сортировка узлов ациклического ориентированного графа (элементовчастично-упорядоченного множества).22.2.1.Топологическая сортировка применима и к произвольным ациклическимориентированным графам (двоичное дерево – частный случай такого графа).Ациклический граф можно использовать для графического изображения частичноупорядоченного множества (когда в множестве есть отношение порядка, но не длявсех элементов: некоторые элементы несравнимы).

Цель топологической сортировкипреобразовать частичный порядок в линейный. Графически это означает, что все узлыграфа нужно расположить на одной прямой таким образом, чтобы все дуги графа,соединяющие его узлы, были направлены в одну сторону.4(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.22.2.2. Пример.Пусть частичный порядок задается следующим набором отношений между ключами:a < b, b < d, d < f, b < l, d < h, f < c, a < c,c < e, e < h, g < e, g < k, k < d, k < l(*)Этот набор отношений можно представить в виде ациклического графа (рисунок 6),причем каждое отношение представляет дугу указанного графаЗадача состоит в том, чтобы привести граф с рисунка 6 к линейному графу,показанному на рисунке 7.

Ключи после топологической сортировки будутрасположены, например, в следующем порядке: g k a b d f c e h l (понятно, чтотопологическая сортировка неоднозначна, так что это один из возможныхтопологических порядков). Последовательная обработка полученного линейногосписка узлов графа эквивалентна их обработке в порядке обхода графа.22.2.3. Описание алгоритма. Структуры данных. Находим узел x графа, у которого нетпредшествующих узлов (по крайней мере один такой элемент должен существовать,так как иначе у графа были бы циклы).

Этот узел, будем называть его «ведущим»5(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.узлом, поместим в начало линейного списка узлов и удалим из графа. Посколькуоставшийся граф останется ациклическим, можно применять описанноепреобразование до тех пор, пока все узлы графа не станут «ведущими» и перейдут влинейный список.Для более строгого описания алгоритма необходимо выбрать структуру представленияузлов графа.

Так как основной операцией является нахождение «ведущего» узла a,дескриптор каждого «ведущего» узла должен, помимо ключа a, содержать следующиехарактеристики: количество предшественников count (у «ведущего» узла значениеcount равно 0, по мере удаления узлов значение count уменьшается), указатель списка«ведомых» узлов; кроме перечисленных характеристик дескриптор узла (рисунок 8)должен содержать указатель следующего элемента линейного списка «ведущих»узлов. Каждый «ведомый» узел имеет еще один дескриптор (эти дескрипторыпомещаются в списки «ведомых» узлов), который содержит указатель спискадескрипторов «ведомых» узлов и указатель на дескриптор соответствующего узла всписке «ведущих» узлов (рисунок 9).22.2.4.

Описание алгоритма. Фаза ввода.Пусть исходные данные представлены в виде множества пар ключей (*). Пары ключейвводятся в произвольном порядке. После ввода очередной пары x < y ключи ищутся всписке «ведущих» (с помощью функции find) и в случае отсутствия добавляются кнему. Затем в список «ведомых» дляxдобавляется дескрипторyи счетчикпредшественников y увеличивается на 1 (сначала значения всех счетчиков равны 0).По окончании фазы ввода будет сформирована структура, показанная на рисунке 10.6(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.22.2.5.

Описание алгоритма. Фаза сортировки.На фазе сортировки строим цепочку дескрипторов, у которых счетчик имеет значение0, одновременно корректируя счетчики «ведомых» узлов. Так как с каждой такойкоррекцией значение счетчика уменьшается на 1, постепенно значения всех счетчиковстановятся равными 0, и соответствующие узлы включаются в результирующуюцепочку.22.2.6. Описание алгоритма топологической сортировки на языке Си.Программный файл:#include <stdio.h>#include <stdlib.h>typedef struct ldr {char key;int count;struct ldr *next;struct trl *trail;} leader;/*дескриптор ведущего узла*/typedef struct tlr {struct ldr *id;struct trl *next;} trailer;/*дескриптор ведомого узла*/leader *head, *tail; /*два вспомогательных узла*/int n;/*счетчик ведущих узлов*/leader *find(char w) {/* поиск по ключу w */7(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.leader *h;h = head;tail->key = w;/* "барьер" на случай отсутствия w*/while(h->key != w) h = h->next;if(h == tail) {/* генерация нового ведущего узла */tail = malloc(sizeof(leader)); /* новый tail *//* старый tail становится новым элементом списка */n += 1;h->count = 0;h->trail = NULL;h->next = tail;}return h;}void init_list() {/* инициализация списка «ведущих» */leader *p, *q;trailer *t;char x, y;head = malloc(sizeof(leader));tail = head;n = 0;/* начальная установка */while(признак конца ввода) {scanf("%c %c", &x, &y); /* ввод очередной пары: x y*//* включение пары в список */p = find(x);q = find(y);/* коррекция списка */t = malloc(sizeof(trailer));t->id = q;t->next = p->trail;p->trail = t;q->count += 1;}}/* Исходный список построен.

Организация нового списка */void sort_list() {leader *p, *q;trailer *t;/* В новый список включаются все узлы старого с count == 0 */p = head;head = NULL;while(p != tail) {q = p;8(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.p = q->next;if(q->count == 0) { /* включение q в новый список */q->next = head;head = q;}}/* Фаза сортировки и вывода результатов из нового списка */q = head;while(q != NULL) {printf("%c\n", q->key);n -= 1;t = q->trail;q = q->next;while(t != NULL) {p = t->id;p->count -= 1;if(p->count == 0){p->next = q;q = p;}t = t->next;/* здесь можно удалить ведомый элемент */}}}int main() {init_list();sort_list();return 0;}9(с) Кафедра системного программирования ф-та ВМК МГУ, 2010.