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

Министерство образования и науки Российской Федерации ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО «Северо-Кавказский государственный технический университет»

Факультет информационных технологий и телекоммуникаций

«Допустить к защите»

Заведующий кафедрой ЗИ А. Ф. Чипига КУРСОВАЯ РАБОТА НА ТЕМУ:

Исследование алгоритмов топологической сортировки Автор дипломного проекта Давлет-Кильдеева Екатерина Витальевна Специальность

90 105 «Комплексное обеспечение информационной безопасности автоматизированных систем»

Группа БАС-081

Обозначение курсового проекта КР-СевКавГТУ-94 374−11

Проектировал Е.В.Давлет-Кильдеева Руководитель работы Р. А. Воронкин Ставрополь, 2011

1. ОБЩИЕ ПРИНЦИПЫ ОРГАНИЗАЦИИ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ

1.1 Основные понятия

1.2 Анализ структуры программы топологической сортировки

1.3 Вывод

2. СПОСОБЫ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ

2.1 Алгоритм Демукрона

2.2 Метод топологической сортировки с помощью обхода в глубину

2.3 Вывод

3. РЕАЛИЗАЦИЯ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ В ПРОГРАММНОЙ СРЕДЕ

3.1 Программа, реализующая топологическую сортировку методом Демукрона

3.2 Процедура топологической сортировки, реализующая метод обхода в глубину

3.3 Вывод

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Приложение 1

В словарях слово «сортировка» определяется как процесс разделения объектов по виду или сорту, но программисты традиционно используют его в гораздо более узком смысле, обозначая им такую перестановку предметов, при которой они располагаются в порядке возрастания или убывания. Хотя сортировка традиционно и большей частью использовалась для обработки коммерческих данных, в действительности она является инструментом, полезным в самых разных ситуациях, и поэтому о ней не следует забывать. Появление изощренных алгоритмов сортировки говорит о том, что она сама по себе очень интересна как объект исследования.

Среди всех широко известных методов упорядочивания элементов следует выделить алгоритмы сортировки на графах, а именно топологическую сортировку. Цель данной сортировки — преобразовать частичный порядок в линейный. Графически это означает расположение вершин графика в ряд так, чтобы все стрелки были направлены вправо.

Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его типологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Формально топологическую сортировку можно реализовать по-разному. Примером использования может служить создание карты сайта, где имеет место древовидная система разделов.

Тема топологической сортировки слабо проработана в современной литературе: большинство авторов уделяют в основном внимание наиболее быстрым видам сортировок, а сортировки на графах практически не рассматриваются.

Итак, целью данной курсовой работы является — исследование методов топологической сортировки.

Поставленная цель раскрывается через следующие задачи:

— Проанализировать общие принципы организации топологической сортировки;

— Изучить способы топологической сортировки;

— Исследовать реализацию топологической сортировки в программной среде;

— Сделать выводы по исследованию.

1. ОБЩИЕ ПРИНЦИПЫ ОРГАНИЗАЦИИ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ

1.1 Основные понятия

Множество M называется частично упорядоченным, если над его элементами определено отношение, которое мы назовем «x предшествует y» и обозначим x << y, удовлетворяющее следующим свойствам для любых элементов x, y и z из M:

1. не x << x (антирефлексивность),

2. если x <<< x (антисимметричность),

3. если x << y и y << z, то x << z (транзитивность).

Мы будем предполагать, что M — конечное множество.

Частичное упорядочение на конечном множестве всегда можно проиллюстрировать с помощью диаграммы некоторого графа, в которой элементы представляются вершинами графа, а отношения представляются дугами между этими вершинами; x << y означает, что от вершины, помеченной x, к вершине y существует путь, идущий вдоль дуг в соответствии с их направлением. Свойство частичного упорядочения означает, что в диаграмме графа нет замкнутых контуров.

Проблема топологической сортировки состоит в том, чтобы «перевести частичное упорядочение в линейное упорядочение», т. е. расположить элементы в такую последовательность a1, a2, …, an, что если aj<

Чтобы найти одно из возможных линейных упорядочений начинаем с того, что выбираем какой-либо элемент, которому не предшествует никакой другой (хотя бы один такой элемент существует, иначе имелся бы цикл). Этот элемент помещается в начало списка и исключается из множества M. Оставшееся множество по-прежнему частично упорядочено; таким образом, можно вновь применить тот же самый алгоритм, пока множество не станет пустым. Этот алгоритм оказался бы непригодным в единственном случае, когда образовалось бы непустое частично упорядоченное множество, в котором каждому элементу предшествует другой.

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

— ключом;

— множеством следующих за ним элементов («последователей»);

— счетчиком предшествующих элементов («предшественников»).

Поскольку n — число элементов в M не задано априори, то это множество удобно организовать в виде линейного однонаправленного списка. Следовательно, каждый узел содержит еще поле, связывающее его со следующим узлом списка.

Мы будем считать, что ключи — это целые числа (необязательно последовательные от 1 до n). Аналогично множество последователей каждого элемента можно представить в виде линейного однонаправленного списка. Каждый узел списка последователей неким образом идентифицирован и связан со следующим узлом этого списка.

Если мы назовем узлы главного списка, в котором каждый элемент из M содержится ровно один раз, ведущими (Leaders), а узлы списка последователей ведомыми (Trailers), то мы получим такие описания типов данных [2]:

struct Leader

{

int Key;

int Count;

Trailer* Trail;

Leader* Next;

};

struct Trailer

{

Leader* Id;

Trailer* Next;

};

Теперь легко видеть, что описанная структура является структурой Вирта некоторого ориентированного графа.

1.2 Анализ структуры программы топологической сортировки

Первая часть программы топологической сортировки должна преобразовать входные данные в структуру списка. Это производится последовательным чтением пар ключей x и y (x<

Обозначим ссылки на их представления в списке ведущих через p и q. Эти записи ищутся в списке и, если их там нет, добавляются к нему. Эту задачу выполняет функция L («Located»). Затем к списку ведомых для элемента x добавляется новый узел, идентифицированный как y, счетчик предшественников для y увеличивается на 1. Такой алгоритм соответствует фазе ввода.

//Фаза ввода.

cout << «Задайте отношение частичного поpядка… n» ;

cout << «Элемент «;

cin >> x;

cout << «пpедшествует элементу «;

while (x≠0)

{

cin >> y;

p = L (x);

q = L (y);

t = new (Trailer); t->Id = q; t->Next = p->Trail;

p->Trail = t; q->Count += 1;

cout << «Элемент «;

cin >> x;

cout << «пpедшествует элементу «;

}

В этом фрагменте программы есть обращения к функции L (w), возвращающей ссылку на компоненту списка с ключом w.

На рисунке показана структура, сформированная при обработке входных данных вида: 1<<4, 1<<2, 4<<8, 5<<8, 2<<8 с помощью этого алгоритма:

Рисунок 1.2.1. — Структура Вирта

После того, как на фазе ввода построена некоторая структура данных, можно провести саму топологическую сортировку, описанную выше. Но поскольку она состоит в последовательном выборе элемента с нулевым счетчиком предшественников, видимо, разумно вначале собрать все такие элементы в некоторый новый список. Поскольку мы знаем, что исходный список ведущих впоследствии не понадобится, то же самое поле Next можно использовать повторно для помещения в список ведущих, не имеющих предшественников. Такая замена одного списка на другой часто встречается при работе со списками.

Это подробно описано в следующем программном фрагменте:

//Поиск ведущих с нулевым количеством предшественников.

p = Head; Head = NULL;

while (p≠Tail)

{

q = p; p = p->Next;

if (q->Count==0)

{ q->Next = Head; Head = q; }

}

Для удобства новая цепочка строится в обратном порядке.

Для нашего примера мы увидим, что список ведущих заменяется на список вида:

Рисунок 1.2.2. — Результат преобразования

После всех этих подготовительных действий, направленных на то, чтобы выработать подходящее представление частично упорядоченного множества M, мы можем, наконец, перейти к собственно топологической сортировке, т. е. формированию выходной последовательности.

Это можно описать следующим образом:

//Фаза вывода.

cout << «Результат…n» ;

q = Head;

while (q≠NULL)

{

//Вывести элемент, а затем исключить его.

cout << q->Key << ««;

z -= 1;

t = q->Trail;

q = q->Next;

while (t≠NULL)

{

// Уменьшить счетчик предшественников у всех его

// последователей в списке ведомых t; если какой;

// либо счетчик стал равен 0, то добавить этот

// элемент к списку ведущих q;

// p — вспомогательная переменная, указывающая на

// ведущий узел, счетчик которого нужно уменьшить

// и проверить на равенство нулю.

p = t->Id;

p->Count -= 1;

if (p->Count==0) //Включение *p в список ведущих.

{ p->Next = q; q = p; }

t = t->Next;

}

}

Следует обратить внимание, что был введен счетчик z для подсчета ведущих узлов, сформированных на фазе ввода. Этот счетчик уменьшается каждый раз, когда ведущий узел выводится на фазе вывода. Поэтому он должен вновь стать равным нулю в конце работы программы. Если это не так, то в структуре остались элементы и среди них нет таких, у которых отсутствуют предшественники. Очевидно, что в этом случае множество M не является частично упорядоченным.

Приведенная выше программа фазы вывода служит примером работы со списком, который «пульсирует», т. е. элементы которого добавляются и удаляются в непредсказуемом порядке. Следовательно, это пример процесса, полностью использующего гибкость, которую обеспечивает связанный список.

1.3 Вывод

Были изучены основные понятия топологической сортировки, также была рассмотрена проблема топологической сортировки. Во второй части главы сделан анализ структуры программы топологической сортировки, алгоритм которой позаимствован у Н.Вирта.

2. СПОСОБЫ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ

2.1 Алгоритм Демукрона

Топологическая сортировка (Topological sort) — один из основных алгоритмов на графах, применяется для решения множества более сложных задач. Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.

Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф (рисунок 2.1.1.) (в некоторых задачах встречаются бесконтурные ориентированные графы, имеющие бесконечные множества вершин и дуг). Такие графы называют бесконечными сетями. Мы рассматриваем только конечные сети. Кроме того, в литературе по теории графов термин «сеть» иногда используется в ином смысле — для объекта, более сложного, чем граф).

Рисунок 2.1.1. — Пример ориентированного графа, к которому применима топологическая сортировка.

Поскольку сеть является бесконтурным графом, можно показать, что существуют вершины (узлы) сети с нулевой полустепенью исхода, а также вершины (узлы) с нулевой полустепенью захода. Первые называют стоками или выходами сети, а вторые — источниками или входами сети.

Уровень вершины сети — это натуральное число, определяемое следующим образом:

1) если полустепень захода вершины равна 0, то ее уровень равен 0 и наоборот (т.е. нулевой уровень N0 — это множество всех входов);

2) если множества Ni вершин уровня i определены для всех i? k, то уровень Nk+1 содержит те и только те вершины, предшественники которых принадлежат любому из уровней с номером от 0 до k, причем существует хотя бы один предшественник уровня k, т. е.

Nk+1= (2.1.1.)

где Г-1(v) = { х: х > v } — множество предшественников вершины v.

Уровень вершины сети можно интерпретировать как длину максимального пути от входов сети до этой вершины.

Порядковой функцией сети G = (V, Е) называют отображение ord: V > N, сопоставляющее каждой вершине сети номер ее уровня.

Во многих прикладных задачах возникает проблема такого упорядочения вершин сети, при котором вершины, принадлежащие одному уровню, располагаются друг под другом, а дуги ориентированного графа ведут в его изображении на плоскости от вершин с меньшим уровнем к вершинам с большим уровням слева направо. Подобного рода проблема называется проблемой топологической сортировки, поскольку необходимо расположить вершины графа на плоскости так, чтобы отчетливо было видно распределение вершин по уровням. Само расположение при этом может быть разным, лишь бы оно имело «слоистую» структуру, в которой каждый слой составляют вершины одного уровня (рисунок 2.1.2).

Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно).

Рисунок 2.1.2. — Сеть и результат применения топологической сортировки сети.

Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов.

Формально топологическую сортировку можно реализовать по-разному.

Один из методов вычислении порядковой функции сети — алгоритм Демукрона. Предполагается, что вершины сети пронумерованы от 1 до n.

Наглядно процесс определения уровней вершин можно представить следующим образом. Нулевой уровень образуют входы сети — вершины с полустепенью захода, равной 0. Удалив из сети все вершины нулевого уровня и исходящие из них дуги, вновь получим сеть, входами которой будут вершины первого уровня исходной сети. Указанный процесс «послойного» удаления вершин следует продолжать до тех пор, пока все вершины исходной сети не будут распределены по уровням.

Алгоритм Демукрона использует матрицу смежности вершин В типа n x n в качестве средства представления сети и основан непосредственно на определении уровня вершины и свойствах матрицы В. Можно увидеть, что сумма элементов k-го столбца матрицы В равна полустепени захода вершины Vk. Поэтому, просуммировав элементы матрицы по всем столбцам и выбрав вершины, соответствующие столбцам с нулевой суммой, получим множество вершин нулевого уровня — входы сети.

Безусловно, «физически» удалять вершины и дуги из сети и вычеркивать из матрицы В строки, соответствующие удаляемым вершинам, нет необходимости. Процесс вычисления порядковой функции можно организовать следующим образом. Запишем суммы элементов столбцов матрицы В в вектор М длины n. При этом элемент mk вектора М будет содержать полустепень захода вершины Vk. Пусть из сети удалена вершина Vi и все исходящие из нее дуги. Заметим, что элемент bik равен 1, если из вершины Vi идет дуга в вершину Vk, и равен 0 в противном случае. Поэтому, чтобы получить новую полустепень захода вершины Vk, необходимо из элемента mk вектора М вычесть элемент bik матрицы В. Чтобы пересчитать полустепени захода всех вершин сети, оставшихся в ней после удаления вершины Vi, надо из вектора М вычесть i-ю строку матрицы В.

Если на очередном шаге входами сети являются вершины Vi, …, Vir, то для определения следующего «слоя» вершин нужно из вектора М вычесть строки матрицы В с номерами i1, …, ir и зафиксировать новые нулевые элементы вектора М, появившиеся после вычитания. Фиксировать следует именно новые нулевые элементы, поскольку элементы вектора М, соответствующие вершинам, лежащим на предыдущих уровнях, стали равными 0 на предыдущих шагах алгоритма.

Заметим, что порядковую функцию сети можно задать, указав множества вершин, принадлежащих каждому уровню, или сопоставив каждой вершине ее номер уровня. Первый способ более удобен при теоретических рассуждениях, второй — при вычислениях.

Алгоритм обрабатывает матрицу В смежности вершин графа порядка n. В результате работы алгоритма получаем массив Ord длины n, i-й элемент которого равен номеру уровня вершины Vi.

0. Сформировать множество V1 вершин сети. Значение счетчика уровней k положить равным 0. Найти суммы элементов по всем столбцам матрицы В (полустепени захода вершин) и заполнить ими массив М.

1. Бели множество V1 не пусто, перейти на шаг 2, если иначе, то перейти на шаг 3.

2. Определить множество I номеров всех новых нулевых элементов массива М, т. е. таких, что соответствующие этим номерам вершины принадлежат множеству V1.

3. Присвоить элементам массива Ord с номерами из множества I номер уровня k и удалить вершины с этими номерами из множества V1 («замаскировать» вершины). Вычесть из массива М строки матрицы В, соответствующие вершинам с номерами из множества I (т.е. вершинам последнего вычисленного уровня).

4. Увеличить счетчик уровней на 1 (k = k + 1). Вернуться на шаг 1.

5. Закончить работу.

Пример. Применим алгоритм Демукрона к сети, представленной на рисунке 2.1.2. Матрица смежности вершин сети имеет следующий вид:

Рисунок 2.1.3. — Матрица смежности вершин сети.

Приведем последовательность значений массива М, соответствующую итерациям алгоритма и множества Ni вершин i-го уровня (рисунок 2.1.4). Прочерки соответствуют вершинам, не принадлежащим множеству V1 («замаскированные» вершины) на соответствующем этапе алгоритма.

Рисунок 2.1.4. — Значения массива М.

Алгоритм Демукрона может быть модифицирован так, чтобы он останавливался, если ориентированный граф, поданный на вход, не является сетью, и сообщал об этом. Можно увидеть, что анализируемый граф не будет сетью тогда и только тогда, когда при очередном перевычислении массива М не появятся новые нули.

2.2 Метод топологической сортировки с помощью обхода в глубину

Поиск в глубину (или обход в глубину) является одним из основных и наиболее часто употребляемых алгоритмов анализа графов.

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

Наиболее подходящим способом для реализации данного алгоритма является рекурсия. В этом случае все возвраты вдоль пройденного пути будут осуществляться автоматически, в результате работы механизма реализации рекурсии в языке программирования (заметим, что не все языки позволяют записывать в явном виде рекурсивные алгоритмы).

Исходный граф G = (V, Е), где V — множество вершин графа, а Е — множество его ребер, может быть как ориентированным, так и неориентированным.

Переходя в вершину и из вершины v по ребру (и, и), мы запоминаем предшественника и при обходе в глубину: р[и] = v. Для вершин, у которых предшественников нет, положим р[и] = -1. Таким образом, получается дерево поиска в глубину. Если поиск повторяется из нескольких вершин, то получается несколько деревьев, образующих лес поиска в глубину. Лес поиска в глубину состоит из всех вершин исходного графа и ребер, по которым эти вершины впервые достигнуты.

Для наглядности будем считать, что в процессе работы алгоритма вершины графа могут быть белыми, серыми и черными. Изначально все вершины помечены белым цветом: color[o] =white. Впервые обнаружив вершину v, мы красим ее серым: цветом color[o] = grey. По окончании обработки всех исходящих ребер красим вершину и в черный цвет: color[o] = black.

Таким образом, белый цвет соответствует тому, что вершина еще не обнаружена, серый — тому, что вершина уже обнаружена, но обработаны еще не все исходящие из нее ребра, черный — тому, что вершина уже обнаружена и все исходящие из нее ребра обработаны.

Помимо того, для каждой вершины в процессе поиска в глубину полезно запоминать еще два параметра: в d[v] будем записывать «время» первого попадания в вершину, а в f[v] - «время» окончания обработки всех исходящих из v ребер. При этом d[v] и f[v] представляют собой целые числа из диапазона от 1 до 2|V|, где |V| - число вершин графа.

Вершина v будет белой до момента d[v], серой между d[v] и f[v], черной после f[v].

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

Ниже приводится схема возможной реализации поиска в глубину Depth-first search (Dfs):

1 Procedure Dfs (v);

2 begin

3 color[v] := grey;

4 time := time + 1; d[v] := time;

//цикл по всем ребрам, исходящим из v

5 for {u: (v, u) 2 E} do

6 if color[u] = white then begin

7 p[u] := v;

8 Dfs (u)

9 end;

10 color[v] := black;

11 time := time + 1; f[v] := time

12 end;

// основная программа

13 for {v 2 V} do begin

// инициализация значений

14 color[v] := white;

15 p[v] := -1;

16 d[v] := 0; f[v] := 0

17 end;

18 time := 0;

//цикл по всем вершинам

19 for {v 2 V} do

20 if color[v] = white then Dfs (v);

Рассмотрим пошаговое исполнение алгоритма на примере конкретного ориентированного графа (рисунок 2.2.1.) (жирным помечаются ребра, вошедшие в лес поиска в глубину).

Рисунок 2.2.1. — Пошаговое исполнение алгоритма.

Подсчитаем общее число операций при выполнении поиска в глубину на графе G = (V, Е). Изначальная инициализация данных (строки 13 — 18 алгоритма) и внешний цикл по вершинам (строки 19 — 20) требуют 0(V) времени. Для каждой вершины процедура Dfs вызывается ровно один раз, причем время работы каждого вызова определяется временем, необходимым на просмотр всех исходящих из вершины ребер (5 — 9). Это время зависит от способа хранения графа.

Если хранить граф в виде матрицы смежности, то цикл в процедуре Dfs (строки 5 — 9) занимает 0(V) времени. Тогда суммарное время работы всех вызовов Dfs равно 0(V2). Таким образом, время работы поиска в глубину при использовании матрицы смежности равно 0(V2).

Если же хранить граф списками смежности или списком ребер, то цикл (5−9) занимает О (число исходящих из вершины ребер) времени. Суммарное время работы всех вызовов Dfs равно 0(E), так как каждое ребро просматривается лишь однажды. Таким образом, время работы поиска в глубину при использовании списков смежности или списка ребер равно 0(V+E).

В графах, где число ребер Е не велико (порядка числа вершин V), второй способ хранения, несмотря на несколько более сложную реализацию, дает ощутимый выигрыш во времени.

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

На рис. 5 представлен граф и один из вариантов его топологической сортировки: 1, 5, 2, 6, 3, 4. Заметим, что, например, вершину с номером 6 можно поставить в любое место топологической сортировки этого графа. Вершины 1 и 5 также могут располагаться в другом порядке (сначала 5, а затем 1). В остальном порядок топологической сортировки вершин данного графа фиксирован.

Алгоритм нахождения топологической сортировки также основан на поиске в глубину. Применим поиск в глубину к нашему графу G (рисунок 2.2.2.). Завершая обработку каждой вершины (делая ее черной), заносим ее в начало списка. По окончании обработки всех вершин полученный список будет содержать топологическую сортировку данного графа. Обозначим количество вершин в графе п. Так как в результирующий список должны попасть все п вершин нашего графа, то реализовать его можно на обычном массиве, записывая в него элементы списка начиная с n-го места в массиве и заканчивая первым.

Рисунок 2.2.2. — Применение поиска в глубину к графу.

Покажем, что полученный список действительно удовлетворяет основному свойству топологической сортировки: все ребра ведут от вершин с меньшим номером к вершинам с большим номером в нашем списке. Предположим противное: пусть существует ребро (и, и) такое, что вершина и встречается в нашем списке раньше вершины v. Но тогда обработка вершины v была завершена раньше, чем обработка вершины и. Это означает, что в момент окончания обработки вершины v вершина и могла быть либо белой, либо серой. В первом случае мы должны были бы пройти по ребру (и, и), но не сделали этого. Во втором случае поиск в глубину нашел бы обратное ребро, т. е. граф G содержал бы циклы. Оба случая приводят к противоречию, а значит, наше предположение неверно и указанный список действительно является топологической сортировкой.

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

1 Procedure Dfs (v);

2 begin

3 color[v] := grey;

4 for {u:(v, u) 2 E} do begin

5 if color[u] = white then Dfs (v)

6 else if color[u] = grey then

7 {граф имеет циклы, конец}

8 end;

9 inc (num); list[n-num+1] := v;

10 color[v] := black

11 end;

//основная программа

12 for v := 1 to n do begin

13 color[v] := white; list[v] := 0

14 end;

15 num := 0;

16 for v := 1 to n do

17 if color[v] = white then Dfs (v);

//печатаем вариант топологической сортировки

18 for v := 1 to n печать (list[v]);

По окончании работы алгоритма массив list будет содержать топологическую сортировку данного графа. Условие в строке 6 осуществляет проверку на наличие циклов (ориентированный граф не имеет циклов тогда и только тогда, когда поиск в глубину не находит в нем обратных ребер). При нахождении обратного ребра (строка 7) следует выдать соответствующее сообщение и завершить исполнение алгоритма. Последнее для рекурсивного алгоритма не совсем тривиально.

2.3 Вывод

В данной главе были исследованы основные способы топологической сортировки, а именно метод Демукрона и метод топологической сортировки с помощью обхода в глубину. Метод Демукрона реализован с использованием матрицы смежности. Алгоритм топологической сортировки с помощью обхода в глубину основан на рекурсии.

3. РЕАЛИЗАЦИЯ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ В ПРОГРАММНОЙ СРЕДЕ

3.1 Программа, реализующая топологическую сортировку методом Демукрона

Пример топологической сортировки заимствованный у Д. Кнута:

#include «stdafx.h»

#include

#include

typedef struct Leader *Lref;//1

typedef struct Trailer *Tref;//2

//3

typedef struct Leader

{

int key;//4

int count;//5

Tref Trail;

Lref next;

};

//6

typedef struct Trailer

{

Lref Id;

Tref next;

};

class spisok {

private:

Lref head;//7

Lref tail;//8

int z;//9

public:

spisok (){//10

head = tail = new (Leader); z=0;};

Lref L (int);

void poisk ();

void vyvod ();

};

void spisok: poisk ()

{

Lref p, q;//11

p=head;

head = NULL;

while (p≠tail)

{

q=p;

p=p->next;

if (q->count==0)

{q->next=head;

head=q;}

}

}

Lref spisok: L (int w)

//12

{

Lref h=head;

tail->key=w;

while (h->key≠w)

h=h->next;

if (h=tail)//13

{

tail = new (Leader); z++;

h->count=0;

h->Trail = NULL; h->next=tail;

}

return h;

}

void spisok: vyvod ()

{

Lref p, q;

Tref t;

cout << endl;

cout << «Результат…n» ;

q=head;

while (q≠NULL)

{

cout << q->key << ««;

z—;

t= q->Trail;

q=q->next;

while (t≠NULL)

{

p=t->Id;

p->count—;

if (p->count==0)//14

{ p->next=q;

q=p;}

t=t->next;

}

}

if (z≠0)

cout <<" nМножество не является частично упорядоченным! n" ;

return 0;

getch ();

}

void main ()

{

spisok A;

Lref p, q;

Tref t;

int x, y;//15

//16

cout <<" Задайте отношение частичного порядкаn" ;

cout <<" Элемент «;

cin >> x;

cout <<" предшествует элементу «;

while (x≠0)

{

cin >> y;

p=A.L (x);

q=A.L (y);

t= new (Trailer);

t->Id=q;

t->next=p->Trail;

p->Trail=t;

q->count+=1;

cout <<" Элемент «;

cin >> x;

cout <<" предшествует элементу «;

}

//17

A.poisk ();

//18

A.vyvod ();

}

Здесь операторы:

1 — Тип: указатель на заголовочный узел;

2 — Тип: указатель на дуговой узел;

3 — Описание типа заголовочного узла;

4 — Информационное поле;

5 — Количество предшественников;

6 — Описание типа дугового узла;

7 — Указатель на список заголовочных узлов;

8 — Указатель на фиктивный элемент в конце списка заголовочных узлов;

9 — Количество узлов, не имеющих предшественников;

10 — Инициализация списка заголовочных узлов;

11 — Рабочие указатели;

12 — Функция возвращает указатель на ведущего с ключом w;

13 — В списке нет элемента с ключом w;

14 — Включение (*p) в список ведущих;

15 — Рабочие переменные;

16 — Фаза ввода;

17 — Поиск ведущих с нулевым количеством предшественников;

18 — Фаза вывода.

Тестовые пpимеpы:

1) Система отношений порядка имеет вид:

9>2, 3>7, 7>5, 5>8, 8>6, 4>6, 1>3, 7>4, 9>5, 2>8.

Программа топологической сортировки выдаст следующий результат:

1 3 7 4 9 2 5 8 6

2) Более содержательный пример использования программы топологической сортировки [4, с.261−262]:

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

— не принято подавать за обедом более четырех вин, не считая шампанского;

— последовательность вин на столе подчиняется некоторым соотношениям порядка, признаваемым всеми знатоками.

Эти соотношения порядка таковы:

белое сухое < белое бархатистое, белое бархатистое < белое сладкое, красное легкое < красное крепкое, белое (за исключением сладкого) < красное, крепкое < белое сладкое.

При этом знак < указывает, что вино, стоящее слева от него, должно быть подано прежде вина, которое стоит справа. Мы хотим отметить то, что эти соотношения вносят в любой винный погреб частичное упорядочение с точки зрения математика.

Закодируем сорта вин следующим образом:

1 — белое сухое,

2 — белое бархатистое,

3 — белое сладкое,

4 — красное легкое,

5 — красное крепкое.

Тогда система отношений порядка примет вид:

1<2, 2<3, 4<5, 1<4, 1<5, 2<4, 2<5, 4<3, 5<3,

а программа топологической сортировки выдаст следующий результат:

1 2 4 5 3

Hо так как не принято подавать за обедом более четырех вин, а шампанское в нашем перечне сортов вин отсутствует, то возможны лишь следующие варианты:

2 4 5 3 1 2 4 3

1 2 5 3 1 2 4 5

1 4 5 3

Цель топологической сортировки — преобразовать частичный порядок в линейный. Графически это означает расположить вершины графа в ряд так, чтобы все стрелки были направлены вправо. Реализация в программной среде с++ алгоритма одного из возможных преобразований частичного порядка в линейный приведен в приложении 1.

3.2 Процедура топологической сортировки, реализующая метод обхода в глубину

Процедура возвращает true, если граф был топологически отсортирован, иначе возвращается false.

Color — массив, в котором хранятся цвета вершин (0 — белый, 1 — серый, 2 — черный).

N — количество вершин.

Edges — массив списков смежных вершин.

Numbers — массив, в котором сохраняются новые номера вершин.

Stack — стек, в котором складываются вершины после их обработки.

Cycle — принимает значение true, если в графе найден цикл.

1 boolean topological_sort (){

2 boolean Cycle;

3 for (int i = 1;i <= N;i ++){

4 Cycle = dfs (i);

5 if (Cycle)return false;

6 }

7 for (int i = 1;i <= n;i ++){

8 Numbers[Stack.pop ()] = i;

9 }

10 return true;

11 }

12 boolean dfs (int v){

13 if (Color[v] == 1) return true;

14 if (Color[v] == 2) return false;

15 Color[v] = 1;

16 for (int i = 0;i < Edges[v]. size ();i ++){

17 if (dfs (Edges[v]. get (i)))return true;

18 }

19 Stack. push (v);

20 Color[v] = 2;

21 return false;

22 }

Комментарий

3−6. Вызывается обход в глубину от всех вершин. Заканчиваем работу алгоритма, если обнаружен цикл.

7−9. Заносим в массив новые номера вершин.

13−14. Если вершина серая, то мы обнаружили цикл. Заканчиваем поиск в глубину.

14. Если вершина черная, то заканчиваем ее обработку.

15. Красим вершину в серый цвет.

16−18. Обрабатываем список смежных с ней вершин.

19. Кладем вершину в стек.

20. Красим вершину в черный цвет.

3.3 Вывод

Были реализованы основные алгоритмы топологической сортировки в программной среде. Проведен анализ каждого из этапов разработки данных алгоритмов, также были приведены результаты.

ЗАКЛЮЧЕНИЕ

Топологическая сортировка — это сортировка элементов, для которых определён частичный порядок, то есть упорядочение задано не на всех, а только на некоторых парах элементов. Кроме того, она является одним из основных алгоритмов на графах, который применяется для решения более сложных задач.

В данной курсовой работе были рассмотрены общие принципы топологической сортировки, изучены основные методы топологической сортировки, а также их реализация в различных программных средах. Из проделанной работы можно сделать следующие выводы:

— Топологическая сортировка применима в разных отраслях:

— сети;

— создание карты сайта;

— календарное планирование и т. д.

— Алгоритмы топологической сортировки достаточно просты и понятны, также легко реализуемы в программной среде.

1. Кнут Д. Искусство программирования Т. 1. Основные алгоритмы. — М.: Вильямс, 2000, — 736с.

2. Вирт Н. Алгоритмы + структуры данных = программы. — М.: Мир, 1983,-406с.

3. Кофман А., Фор Р. Займемся исследованием операций. — М.: Мир, 1966, — 262с.

4. Кнут Д. Искусство программирования Т. 3. Сортировка и поиск. — М.: Вильямс, 2000.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.:Вильямс, 2000 — 384 с.

6. Окулов С. М. Программирование в алгоритмах. М.: Лаборатория базовых знаний, 2002.-341 с.

7. Седжвик Р. Фундаментальные алгоритмы на С++/Алгоритмы на графахК.:Диасофт, 2002. — 496 с.

8. Седжвик Р. Фундаментальные алгоритмы на С++/Анализ/Структуры данных/Сортировка/Поиск — К.:Диасофт, 2001. — 688с.

9. Бакнелл Дж. Фундаментальные алгоритмы и структуры данных в Delphi. — СПб.: Диасофт, 2003. — 560 с.

10. Белоусов А. И., Ткачев С. Б., Дискретная математика Москва, 2004 — 743с.

Приложение 1

#include «stdafx.h»

#include

using namespace std;

typedef struct Leader *Lref; //Тип: указатель на заголовочный узел.

typedef struct Trailer *Tref; //Тип: указатель на дуговой узел.

//Описание типа заголовочного узла.

typedef struct Leader

{

int Key; //Информационное поле.

int Count; //Количество предшественников.

Tref Trail;

Lref Next;

};

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

//Описание типа дугового узла.

typedef struct Trailer

{

Lref Id;

Tref Next;

};

class Spisok {

private:

Lref Head; //Указатель на список заголовочных узлов.

Lref Tail; //Указатель на фиктивный элемент

//в конце списка заголовочных узлов.

int z; //Количество узлов, не имеющих предшественников.

public:

Spisok () {//Инициализация списка заголовочных узлов.

Head = Tail = new (Leader); z = 0;};

Lref L (int);

void Poisk ();

void Vyvod ();

};

void Spisok: Poisk ()

{

Lref p, q; // Рабочие указатели.

p = Head; Head = NULL;

while (p≠Tail)

{

q = p; p = p->Next;

if (q->Count==0)

{ q->Next = Head; Head = q; }

}

}

Lref Spisok: L (int w)

//Функция возвращает указатель на ведущего с ключом w.

{

Lref h = Head;

Tail->Key = w;

while (h->Key≠w) h = h->Next;

if (h==Tail)

// В списке нет элемента с ключом w.

{

Tail = new (Leader); z++;

h->Count = 0; h->Trail = NULL; h->Next = Tail;

}

return h;

}

void Spisok: Vyvod ()

{

Lref p, q; // Рабочие указатели.

Tref t;

cout << endl;

cout << «Результат…n» ;

q = Head;

while (q≠NULL)

{

cout << q->Key << ««;

z—;

t = q->Trail; q = q->Next;

while (t≠NULL)

{

p = t->Id; p->Count—;

if (p->Count==0) // Включение (*p) в список ведущих.

{ p->Next = q; q = p; }

t = t->Next;

}

}

if (z≠0)

cout << «nМножество не является частично упорядоченным! n» ;

}

void main ()

{

{setlocale (LC_ALL, «Russian»);}

Spisok A;

Lref p, q; // Рабочие указатели.

Tref t;

int x, y; // Рабочие переменные.

// Фаза ввода.

cout << «Задайте отношение частичного порядка… n» ;

cout << «Элемент «;

cin >> x;

cout << «предшествует элементу «;

while (x≠0)

{

cin >> y;

p = A. L (x); q = A. L (y);

t = new (Trailer); t->Id = q; t->Next = p->Trail;

p->Trail = t; q->Count += 1;

cout << «Элемент «;

cin >> x;

cout << «предшествует элементу «;

}

// Поиск ведущих с нулевым количеством предшественников.

A.Poisk ();

// Фаза вывода.

A.Vyvod ();

}