Введение
Порядок узлов для направленных ациклических графов
В информатике топологическая сортировка или топологический порядок направленного графа — это линейный порядок его вершин, такой что для каждого направленного ребра (u, v) от вершины u к вершине v, вершина u предшествует вершине v в этом порядке. Например, вершины графа могут представлять задачи, которые необходимо выполнить, а ребра — ограничения, указывающие, что одна задача должна быть выполнена перед другой; в этом случае топологический порядок представляет собой допустимую последовательность выполнения задач. Точнее, топологическая сортировка — это обход графа, в котором каждый узел v посещается только после посещения всех его зависимостей. Топологический порядок возможен тогда и только тогда, когда граф не содержит направленных циклов, то есть является направленным ациклическим графом (DAG). Любой DAG имеет как минимум один топологический порядок, и существуют алгоритмы для построения топологического порядка любого DAG за линейное время. Топологическая сортировка имеет множество применений, особенно в задачах ранжирования, таких как поиск множества обратных дуг. Топологическая сортировка возможна даже в случае, если DAG имеет несвязные компоненты.
Примеры
Каноническое применение топологической сортировки заключается в планировании последовательности заданий или задач на основе их зависимостей. Задания представляются вершинами, и существует ребро от x к y, если задание x должно быть выполнено перед началом задания y (например, при стирке одежды стиральная машина должна закончить работу, прежде чем мы поместим одежду в сушилку). Тогда топологическая сортировка предоставляет порядок выполнения заданий. Тесно связанное применение алгоритмов топологической сортировки было впервые изучено в начале 1960-х годов в контексте метода PERT для планирования в управлении проектами. В этом применении вершины графа представляют собой вехи проекта, а ребра – задачи, которые необходимо выполнить между двумя вехами. Топологическая сортировка является основой для алгоритмов с линейной временной сложностью, предназначенных для поиска критического пути проекта – последовательности вех и задач, определяющей общую продолжительность проекта. В информатике подобные применения возникают при планировании инструкций, упорядочивании вычисления ячеек формул при пересчете значений в электронных таблицах, логическом синтезе, определении порядка выполнения задач компиляции в makefile, сериализации данных и разрешении зависимостей символов в компоновщиках. Она также используется для определения порядка загрузки таблиц с внешними ключами в базах данных.
Уникальность
Если топологическая сортировка обладает свойством, что все пары последовательных вершин в отсортированном порядке соединены ребрами, то эти ребра образуют ориентированный гамильтонов путь в DAG. Если гамильтонов путь существует, порядок топологической сортировки уникален; ни один другой порядок не соответствует ребрам этого пути. И наоборот, если топологическая сортировка не образует гамильтонов путь, то в DAG будет два или более допустимых топологических упорядочений, поскольку в этом случае всегда можно сформировать второе допустимое упорядочение, поменяв местами две последовательные вершины, не соединенные ребром. Таким образом, можно проверить за линейное время, существует ли уникальное упорядочение и существует ли гамильтонов путь, несмотря на NP-трудность задачи о гамильтоновом пути для более общих ориентированных графов (т.е. циклических ориентированных графов).
Отношение к частичным заказам
Топологические упорядочения также тесно связаны с концепцией линейного расширения частичного порядка в математике. Частично упорядоченное множество — это просто множество объектов вместе с определением отношения неравенства «≤», удовлетворяющего аксиомам рефлексивности (x ≤ x), антисимметрии (если x ≤ y и y ≤ x, то x = y) и транзитивности (если x ≤ y и y ≤ z, то x ≤ z). Полный порядок — это частичный порядок, в котором для любых двух объектов x и y в множестве либо x ≤ y, либо y ≤ x. Полные порядки хорошо известны в информатике как операторы сравнения, необходимые для выполнения алгоритмов сортировки сравнением. Для конечных множеств полные порядки могут быть отождествлены с линейными последовательностями объектов, где отношение «≤» истинно всякий раз, когда первый объект предшествует второму в последовательности; алгоритм сортировки сравнением может быть использован для преобразования полного порядка в последовательность таким образом. Линейное расширение частичного порядка — это полный порядок, совместимый с ним в том смысле, что если x ≤ y в частичном порядке, то x ≤ y и в полном порядке. Можно определить частичный порядок по любому DAG, приняв множество объектов за вершины DAG и определив, что x ≤ y истинно для любых двух вершин x и y, если существует направленный путь из x в y; то есть, если y достижим из x. При этих определениях топологический порядок DAG является тем же самым, что и линейное расширение этого частичного порядка. И наоборот, любой частичный порядок можно определить как отношение достижимости в DAG. Один из способов сделать это — определить DAG, который имеет вершину для каждого объекта в частично упорядоченном множестве и ребро xy для каждой пары объектов, для которых x ≤ y. Альтернативный способ — использовать транзитивное сокращение частичного упорядочения; как правило, это приводит к DAG с меньшим количеством ребер, но отношение достижимости в этих DAG по-прежнему соответствует тому же частичному порядку. Используя эти построения, можно применять алгоритмы топологической сортировки для поиска линейных расширений частичных порядков.
Отношение к оптимизации расписания
По определению, решение задачи планирования, включающее граф предшествования, является допустимым решением топологической сортировки (независимо от количества машин), однако сама по себе топологическая сортировка недостаточна для оптимального решения задачи оптимизации планирования. Алгоритм Ху — популярный метод, используемый для решения задач планирования, требующих графа предшествования и учитывающих время обработки (где целью является минимизация максимального времени завершения всех задач). Как и топологическая сортировка, алгоритм Ху не является единственным и может быть реализован с использованием поиска в глубину (DFS) путем нахождения максимальной длины пути и последующего назначения задач.