17 (1108016)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2015/2016Лекция 171Топологическая сортировка узлов ациклическогоориентированного графаАциклический граф можно использовать для графическогоизображения частично упорядоченного множества.Цель топологической сортировки:преобразовать частичный порядок в линейный.Графически это означает, чтовсе узлы графа нужно расположить на одной прямой такимобразом, чтобы все дуги графа были направлены в однусторону.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(*)Набор отношений (*) можно представить в виде следующегоациклического графа (см.

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

Каждый такой узел будем называть ведущим узлом.Шаг алгоритма: Выберем один из ведущих узлов и поместимего в начало линейного списка отсортированных узлов, удаливего из исходного графа.Поскольку граф, у которого удалили один из ведущих узлов,останется ациклическим, в нем будет хотя бы один ведущийузел. Следовательно, можно повторить шаг алгоритма.Легко видеть, что каждый узел графа рано или поздно станетведущим и попадет в формируемый линейный список,и алгоритм завершится через несколько шагов.5Топологическая сортировка узлов ациклическогоориентированного графаСтруктуры данных для представления узлов:Каждый узел исходного графа представляется спомощью дескриптора узла, который имеет вид:Ведомыми для узла n будут узлы, для которых n являетсяпредшественником.

Каждый узел графа (не только ведущий)может иметь один или несколько ведомых узлов.6Топологическая сортировка узлов ациклическогоориентированного графаСтруктуры данных для представления узлов:Дескриптор каждого узла содержит ссылки на ведомыеузлы. Так как заранее неясно, сколько у узла будетведомых узлов, эти ссылки помещаются в список.На рисунке представлен элемент списка ссылок.7Топологическая сортировка узлов ациклическогоориентированного графа1 фаза алгоритма: ввод исходного графаНа этой фазе вводятся пары ключей и из них формируетсяпредставление ациклического графа через дескрипторы узлови списки ведомых узлов.Исходные данные представлены в виде множествапар ключей (*), которые вводятся в произвольномпорядке.После ввода очередной пары x < y ключи x и y ищутсяв списке «ведущих» и в случае отсутствия добавляютсяк нему.В список ведомых узлов узла x добавляется ссылка наy, а счетчик предшественников y увеличивается на 1(начальные значения всех счетчиков равны 0).По окончании фазы ввода будет сформирована структура, показаннаяна следующем слайде (для множества пар ключей (*) ).8Топологическая сортировка узлов ациклическогоориентированного графа9Топологическая сортировка узлов ациклическогоориентированного графа2 фаза алгоритма: сортировка(1)В списке «ведущих» находим дескриптор узла z,у которого значение поля count равно 0.(2)Включаем узел z в результирующую цепочку.(3)Если у узла z есть «ведомые» узлы(значение поля trail не NULL)(a)просматриваем очередной элемент списка«ведомых» узловкорректируем поле count дескрипторасоответствующего «ведомого» узла.Переходим к шагу (1)(b)(4)Так как с каждой коррекцией поля count его значениеуменьшается на 1, постепенно все узлы включаютсяв результирующую цепочку.10Описание алгоритма топологической сортировки на языке Си#include <stdio.h>#include <stdlib.h>typedef struct ldr {char key;int count;struct ldr *next;struct trl *trail;} leader;typedef struct trl {struct ldr *id;struct trl *next;} trailer;leader *head, *tail;int lnum;/*дескриптор ведущего узла*//*дескриптор ведомого узла*//*два вспомогательных узла*//*счетчик ведущих узлов*/11Описание алгоритма топологической сортировки на языке Си/* поиск по ключу w */leader *find (char w) {leader *h = head;/* "барьер" на случай отсутствия w */tail->key = w;while (h->key != w)h = h->next;if (h == tail) {/* генерация нового ведущего узла */tail = malloc (sizeof (leader));/* старый tail становится новым элементом списка */lnum++;h->count = 0;h->trail = NULL;h->next = tail;}return h;12}Описание алгоритма топологической сортировки на языке Сиvoid init_list() {/* инициализация списка «ведущих» */leader *p, *q;trailer *t;char x, y;head = (leader *) malloc (sizeof (leader));tail = head;lnum = 0;/* начальная установка */while (1) {if (scanf ("%c %c", &x, &y) != 2)break;/* включение пары в список */p = find (x);q = find (y);/* коррекция списка */t = malloc (sizeof (trailer));t->id = q;t->next = p->trail;p->trail = t;q->count += 1;}}13Описание алгоритма топологической сортировки на языке Си/* Исходный список построен.

Организация нового списка */void sort_list() {leader *p, *q, *r;trailer *t;/* В выходной список включаются все узлы старогос count == 0 */p = head;head = NULL; /* голова выходного списка */while (p != tail) {q = p;p = q->next;if (q->count == 0) {/* включение q в выходной список */q->next = head;head = q;}}<...>14Описание алгоритма топологической сортировки на языке Си/* Фаза сортировки и вывода результатов из нового списка */<...>q = head; /* есть ведущий узел ->while (q != NULL) {printf ("%c\n", q->key);lnum--;t = q->trail;r = q;q = q->next;while (t != NULL) {p = t->id;p->count -= 1;if (p->count == 0) {p->next = q; // достаточноq = p;// правильнойr->next = p; // если нужен}t = t->next;}}/* lnum == 0 */}head != NULL */длясортировкикорректный список15Описание алгоритма топологической сортировки на языке Сиint main() {init_list ();sort_list ();return 0;}16.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций