WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.

Пример

Для графа

Бесконтурный ориентированный граф

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

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

Алгоритм Кана (1962)

Один из первых алгоритмов, и наиболее приспособленный к исполнению вручную.

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

пока 

  выбрать любую вершину 
 такую, что 
 и 

  

  удалить 
 из всех 

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

Пример работы алгоритма

Пусть задан граф . В таком случае алгоритм выполнится следующим образом:

шаг
0
1
2
3
4
5

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

Алгоритм Тарьяна (1976)

На компьютере топологическую сортировку можно выполнить за O(n) времени и памяти, если обойти все вершины, используя поиск в глубину, и выводить вершины в момент выхода из неё.

Другими словами алгоритм состоит в следующем:

  • Изначально все вершины белые.
  • Для каждой вершины делаем шаг алгоритма.

Шаг алгоритма:

  • Если вершина чёрная, ничего делать не надо.
  • Если вершина серая — найден цикл, топологическая сортировка невозможна.
  • Если вершина белая
    • Красим её в серый
    • Применяем шаг алгоритма для всех вершин, в которые можно попасть из текущей
    • Красим вершину в чёрный и помещаем в окончательный список.

Пример

Пример будет на том же графе, однако порядок, в котором выбираем вершины для обхода — c, d, e, a, b.

Шаг Текущая Белые Стек (серые) Выход (чёрные)
0 a, b, c, d, e
1 c a, b, d, e c
2 d a, b, e c, d
3 e a, b c, d, e
4 d a, b c, d e
5 c a, b c d, e
6 a, b c, d, e
7 d a, b c, d, e
8 e a, b c, d, e
9 a b a c, d, e
10 b a, b c, d, e
11 a a b, c, d, e
12 a, b, c, d, e
13 b a, b, c, d, e

Применение

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

Можно построить список отображения объектов в изометрической проекции зная парные порядковые отношения между объектами (какой из двух объектов должен быть прорисован раньше).

См. также

Ссылки

Литература

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии