На этом шаге мы начнем рассматривать примеры использования топологической сортировки.
Пример 1 [2, с.211-219].
#include <iostream.h> 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() { 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(); }
Тестовые пpимеpы:
1) данный тестовый пример заимствован у Д.Кнута [1, с.324-325].
Система отношений порядка имеет вид:
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) Приведем более содержательный пример использования программы топологической сортировки [3, с.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 4 5 3
1 2 5 3
1 2 4 3
1 2 4 5
3) Этот тестовый пример базируется на идее об использовании топологической сортировки, упомянутой в монографиях [2, с.212; 4, с.311].
В учебных программах для высших учебных заведений одни предметы опираются на материал других, поэтому некоторые курсы студенты должны прослушать раньше других. Если курс v содержит материал для курса w, мы пишем v<<w. Топологическая сортировка курсов означает чтение курсов в таком порядке, чтобы ни один курс не читался раньше того, на материале которого он основан.
Поставим задачу: топологически упорядочить курсы по
- математике,
- дискретной математике и
- информатике.
| Номер курса | Название курса | Последующие курсы |
|---|---|---|
| C1 | Дискретная математика | C2,C3,С4,C5,C6 |
| C2 | Теория кодирования | C10 |
| C3 | Теория автоматов | C5,C11 |
| C4 | Машинная арифметика | C10 |
| C5 | Формальные языки и грамматики | C11 |
| C6 | Теория графов | C8 |
| C7 | Введение в программирование | C8,C18 |
| C8 | Структуры данных | C9,С11,C12,С14,C15,C16,C25 |
| C9 | Анализ алгоритмов | C16,C27 |
| C10 | Устройство ЭВМ | C12 |
| C11 | Теория компиляторов | C12,C14 |
| C12 | Операционные системы | Нет |
| C13 | Базы данных | Нет |
| C14 | Парадигмы программирования | С15,C23 |
| C15 | Искусственный интеллект | Нет |
| C16 | Информационный поиск | C13,C15 |
| C17 | Реляционная алгебра и реляционное исчисление | C13 |
| C18 | Доказательство правильности программ | C14 |
| C19 | Математическая логика | C15,С18,C24 |
| C20 | Теория взаимодействующих последовательных процессов | C12,C14 |
| C21 | Алгебра | C8,C17,C20,C23 |
| C22 | Математический анализ | C9,C23 |
| C23 | Вычислительная математика | Нет |
| C24 | Теория алгоритмов | C2,C7,C9,C14 |
| C25 | Машинная графика | C27 |
| C26 | Геометрия | C25 |
| C27 | Вычислительная геометрия | Нет |
Применив программу топологической сортировки, получим последовательность целых чисел:
26 22 21 17 20 19 24 7 18 1 2 3 5 4 10 6 8 9 16 13 11 12 14 23 15 25 27
Заметим, что в приведенной последовательности допустима перестановка чисел 15 и 23. С учетом этого, получим расположение курсов достаточно крупными блоками:
- Классическая математика (алгебра, геометрия, математический анализ, математическая логика и теория алгоритмов): 26 22 21 17 20 19 24.
- Введение в программирование: 17 18.
- Дискретная математика: 1 2 3 5 4.
- Архитектура вычислительных систем: 10.
- Структуры данных и анализ алгоритмов: 6 8 9.
- Программное обеспечение вычислительных систем: 16 13 11 12 14 15.
- Вычислительная математика: 23.
- Алгоритмы машинной графики: 25 27.
Замечание [1, с.332]. Метод топологической сортировки был впервые опубликован Каном (A.B.Kahn, 1962). Сам факт возможности топологической сортировки был доказан в статье Шпильрайна (E.Szpilrajn, 1930).
(1) Кнут Д. Искусство программирования для ЭВМ. Т.1: Основные алгоритмы. - M.: Мир, 1976. - 736 с.
(2) Вирт H. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. - 406 с.
(3) Кофман А., Фор Р. Займемся исследованием операций. - М.: Мир, 1966, с.261-262.
(4) Tucker, Allen B. Computer Science: A Second Course Using Modula-2. McGraw-Hill, Inc. - 401 pp.
На следующем шаге мы продолжим рассматривать примеры использования топологической сортировки.
