Топологическая сортировка — упорядочивание вершин ациклического ориентированного графа согласно частичному порядку, заданному рёбрами орграфа на множестве его вершин.
Например, для графа:
существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, в частности:
В последовательности могут быть переставлены любые две стоящие рядом вершины, которые не входят в отношение частичного порядка .
Топологическая сортировка широко применяется в различных отраслях например, с её помощью можно построить последовательность прохождения учебных курсов студентами, последовательность установки программ при помощи пакетного менеджера, последовательность сборки исходных текстов программ по данным сборочных файлов, можно построить список отображения объектов в изометрической проекции зная парные порядковые отношения между объектами (какой из двух объектов должен быть прорисован раньше).
Алгоритм Кана Один из первых алгоритмов, и наиболее приспособленный к исполнению вручную разработан Артуром Каном в 1962 году.
Пусть дан ациклический ориентированный простой граф . Через обозначим множество таких вершин , что . То есть — множество всех вершин, из которых есть дуга в вершину . Пусть — искомая последовательность вершин.
пока выбрать любую вершину такую, что и
удалить из всех
Наличие хотя бы одного цикла в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину .
Например, если задан граф: , алгоритм выполнится следующим образом:
шаг 0 1 2 3 4 5
На втором шаге вместо может быть выбрана вершина , поскольку порядок между и не задан.
Алгоритм Тарьяна
С использованием вычислительной техники топологическую сортировку можно выполнить за времени и памяти, если обойти все вершины, используя поиск в глубину, и выводить вершины в момент выхода из неё — алгоритм разработан Робертом Тарьяном в 1976 году.
Изначально все вершины помечаются как белые, для каждой вершины осуществляется шаг алгоритма: если вершина чёрная, ничего делать не надо, если вершина серая — найден цикл, топологическая сортировка невозможна, если вершина белая, то: красится в серый, применяется шаг алгоритма для всех вершин, в которые можно попасть из текущей, вершина красится в чёрный и помещается в начало окончательного списка.
Например, на графе:
с порядком обхода алгоритм отрабатывает следующим образом:
Шаг Текущая Белые Стек (серые) Выход (чёрные) 0 —
— — 1
— 2
— 3
— 4
5
6 —
—
7
—
8
—
9
10
—
11
—
12 — — —
13
— —
См. также Алгоритм Демукрона
Литература
Ссылки Топологическая сортировка при помощи поиска в глубину — реализация на C++ Топологическая сортировка на Pascal за O(n + m) от Никлауса Вирта
Категория:Алгоритмы на графах Категория:Алгоритмы сортировки