Исследование алгоритмов топологической сортировки
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
кой сортировки
18 for v := 1 to n печать(list[v]);
По окончании работы алгоритма массив list будет содержать топологическую сортировку данного графа. Условие в строке 6 осуществляет проверку на наличие циклов (ориентированный граф не имеет циклов тогда и только тогда, когда поиск в глубину не находит в нем обратных ребер). При нахождении обратного ребра (строка 7) следует выдать соответствующее сообщение и завершить исполнение алгоритма. Последнее для рекурсивного алгоритма не совсем тривиально.
2.3 Вывод
В данной главе были исследованы основные способы топологической сортировки, а именно метод Демукрона и метод топологической сортировки с помощью обхода в глубину. Метод Демукрона реализован с использованием матрицы смежности. Алгоритм топологической сортировки с помощью обхода в глубину основан на рекурсии.
3. РЕАЛИЗАЦИЯ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ В ПРОГРАММНОЙ СРЕДЕ
3.1 Программа, реализующая топологическую сортировку методом Демукрона
Пример топологической сортировки заимствованный у Д.Кнута:
#include "stdafx.h"
#include
#include struct Leader *Lref;//1struct Trailer *Tref;//2
//3struct Leader
{
int key;//4
int count;//5
Tref Trail;
Lref next;
};
//6struct Trailer
{
Lref Id;
Tref next;
};
spisok {:
Lref head;//7
Lref tail;//8
int z;//9:
spisok(){//10
head = tail = new(Leader); z=0;};
Lref L (int);
void poisk ();
void vyvod ();
};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;}
}
}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;
}spisok ::vyvod()
{
Lref p,q;
Tref t;
cout << endl;
cout << "Результат...\n";
q=head;
while (q!=NULL)
{
cout 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 ();
}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();
}
Здесь операторы:
- Тип: указатель на заголовочный узел;
- Тип: указатель на дуговой узел;
- Описание типа заголовочного узла;
- Информационное поле;
- Количество предшественников;
- Описание типа дугового узла;
- Указатель на список заголовочных узлов;
- Указатель на фиктивный элемент в конце списка заголовочных узлов;
- Количество узлов, не имеющих предшественников;
- Инициализация списка заголовочных узлов;
- Рабочие указатели;
- Функция возвращает указатель на ведущего с ключом w;
- В списке нет элемента с ключом w;
- Включение (*p) в список ведущих;
- Рабочие переменные;
- Фаза ввода;
- Поиск ведущих с нулевым количеством предшественников;
- Фаза вывода.
Тестовые пpимеpы:
)Система отношений порядка имеет вид:
>2, 3>7, 7>5, 5>8, 8>6, 4>6, 1>3, 7>4, 9>5, 2>8.
Программа топологической сортировки выдаст следующий результат:
3 7 4 9 2 5 8 6
)Более содержательный пример использования программы топологической сортировки [4, с.261-262]:
Разнообразие вин, отражающих почтенную традицию и свидетельствующее об исключительном богатстве палитры французских виноделов, кажется, представляет бесконечные возможности для сервировки хорошего обеда. В действительности же имеются ограничения, выраженные следующими двумя общими правилами:
не принято подавать за обедом более четырех вин, не считая шампанского;
последовательность вин на столе подчиняется некоторым соотношениям порядка, признаваемым всеми знатоками.
Эти соотношения порядка таковы:
белое сухое < белое бархатистое,
белое бархатистое < белое сладкое,
красное легкое < красное крепкое,
белое (за исключением сладкого) < красное,
крепкое < белое сладкое.
При этом знак < указывает, что вино, стоящее слева от него, должно быть подано прежде вина, которое стоит справа. Мы хотим отметить то, что эти соотношения вносят в любой винный погреб частичное упорядочение с точки зрения математика.
Закодируем сорта вин следующим образом:
1 - белое сухое,
2 - белое бархатистое,
3 - белое сладкое,
4 - красное легкое,
5 - красное крепкое.
Тогда система отношений порядка примет вид:
<2, 2<3, 4<5, 1<4, 1<5, 2<4, 2<5, 4<3, 5<3,
а программа топологической сортировки выдаст следующий результат:
2 4 5 3
Hо так как не принято подавать за обедом более четырех вин, а шампанское в нашем перечне сортов вин отсутствует, то возможны лишь следующие варианты:
4 5 3 1 2 4 3
2 5 3 1 2 4 5
1 4 5 3
Цель топологической сортировки - преобразовать частичный порядок в
линейный. Графически это означает расположить вершины графа в ряд так, чтобы все стрелки были направлены вправо. Реализация в программной среде с++ алгоритма одного из возможных преобразований частичного порядка в линейный приведен в приложении 1.
3.2 Процедура топологической сортировки, реализующая метод обхода в глуби?/p>