ВУЗ:
Составители:
21
Рис. 4. Исходное частично упорядоченное множество
Здесь, например, работа 1 должна быть выполнена раньше работы 3,
работа 3 – раньше работы 7, работа 7 – раньше работ 4, 5 и т.д. (рис. 4).
Требуется расположить элементы множества в линейную последо-
вательность так, чтобы все дуги были ориентированы слева направо
(рис. 5):
Рис. 5. Частично упорядоченное множество
после топологической сортировки
Существует простой способ топологической сортировки вручную.
Вначале берётся элемент, которому не предшествует никакой другой
элемент. Он помещается первым в выходную последовательность и уда-
ляется из исходного частично упорядоченного множества вместе с инци-
дентными ему дугами. Затем в графе выбирается ещё один элемент без
предшественников, помещается вторым в выходную последовательность
и исключается из него. Описанный процесс продолжается до тех пор,
пока исходный граф не сократится до пустого графа. Заметим, что ли-
нейное размещение всех элементов невозможно, если в графе имеется
хотя бы один контур.
Рассмотрим далее реализацию топологической сортировки на ма-
шине. При этом будем полагать, что сортируемые элементы пронумеро-
ваны числами от 1 до n в любом порядке. Информация вводится парами
чисел вида ( j, k) или j < k. Это означает, что j-й элемент множества
предшествует k-му элементу.
Входной информацией применительно к нашему примеру могут
быть такие пары:
9 < 2, 3 < 7, 7 < 5, 5 < 8,
8 < 6, 4 < 6, 1 < 3, (22)
7 < 4, 9 < 5, 2 < 8.
1
2
3
4
5
6 7
8
9
1 3 7 4 9 2 5 8 6
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
