Cybern8.com » Топологическая сортировка

Топологическая сортировка

2 августа 2015 Автор статьи: admin

Статья
Комментарии (0)

Пусть дан орграф $G(V, E)$ без петель и кратных дуг. Требуется найти топологическую сортировку (topological sort) вершин этого орграфа, то есть указать такой линейный порядок на его вершинах, что любая дуга ведет от меньшей вершины к большей в смысле этого порядка. В случае, если орграф не является ациклическим и такого порядка не существует, то вывести сообщение об этом. Топологическую сортировку на диаграмме орграфа можно рассматривать как такое упорядочивание его вершин вдоль горизонтальной линии, что все его дуги направлены слева направо. Таким образом, топологическая сортировка существенно отличается от других видов сортировок.

Данная задача решается на основе метода обхода в глубину. Каждая вершина $v \in V$ вначале белая. Будучи обнаруженной в процессе обхода, ее цвет становится серым. Цвет вершины станет черным, когда она будет полностью обработана, то есть когда список смежных с ней вершин будет просмотрен. Каждая вершина $v$ попадает ровно в одно дерева обхода в глубину, так что эти деревья не пересекаются.

Несложно понять, что орграф не имеет циклов тогда и только тогда, когда обход в глубину не находит в нем обратных дуг. Действительно, обратная дуга соединяет потомка с предком и замыкает цикл, образованный дугами дерева. Обратная дуга будет обнаружена, если обход в процессе своей работы придет в вершину серого цвета. Из этого факта следует, что вершины орграфа $G(V, E)$ могут быть топологически отсортированы тогда и только тогда, когда поиск глубину в нем не находит обратных дуг.

Пошаговое представление

$G(V, E)$ – исходный граф, в котором $V$ – это множество вершин, а $E$ – это множество ребер.
$colov$ – массив для хранения цветов вершин графа $G$ .
$cyclic$ — булевская переменная, служащая индикатором того, является орграф ациклическим или нет. Переменная $cyclic$ принимает значение ${\bf false}$ , если орграф $G$ является ациклическим, и значение ${\bf true}$ , если орграф содержит хотя бы один цикл.
$topSort$ — топологическая упорядоченная перестановка вершин орграфа

1
2
3

${\bf for}$ (для) всех вершин $v \in V[G]$
$color[v] \gets {\bf 0}$ //изначально цвет каждой вершины является белым
$cyclic \gets {\bf false}$ //изначально считаем орграф ациклическим

TOPOLOGICAL_SORT(v)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

${\bf if} color[v] = {\bf 2}$
${\bf return}$ //если вершина является черной, то не производим из нее вызов процедуры
${\bf if} cyclic = {\bf true}$
${\bf return}$ //выходим из процедуры, если уже нашли один из циклов
${\bf if} color[v] = {\bf 1}$ //если вершина является серой, то орграф содержит цикл
${\bf cyclic \gets true}$ //помечаем орграф, как содержащий цикл
${\bf return}$
$color[v] \gets {\bf 1}$ //вершина обнаружена, помечаем ее цвет серым
${\bf for}$ (для) всех вершин $w \in E[v]$ //обрабатываем ребро $(v, w)$
$TOPOLOGICAL\_SORT(w)$ //вызываем процедуру рекурсивно от каждой вершины $w$ , смежной с вершиной $v$
${\bf if} cyclic = {\bf true}$ //выходим из процедуры, если уже нашли один из циклов
${\bf return}$
$color[v] \gets {\bf 2}$ //вершина обработана, устанавливаем ее цвет черным
$topSort.push\_front(v)$ //добавляем вершина в начало списка топологически отсортированных вершин

По завершению процедуры топологически упорядоченная перестановка вершин орграфа будет находится в списке $topSort$ , в случае, если исходный орграф $G(V, E)$ не является ациклическим. Если в исходном орграфе есть цикл, то его можно восстановить проходом по массиву предков. Процедуру восстановления цикла смотрите в статье, посвященной алгоритму проверки орграфа на ацикличность.

Примеры и применение

Рассмотрим ситуацию, в которой возникает задача о поиске топологической сортировке вершин орграфа. Пусть в некотором ВУЗе на определенной специальности преподают следующие предметы:

1. математический анализ (матан)
2. теория функций комплексного переменного (ТФКП)
3. функциональный анализ (функан)
4. языки программирования (ЯП)
5. алгебра
6. теория графов
7. криптография (crypto).

При этом, для того чтобы студентам понять содержание некоторых дисциплин, надо ранее обязательно прослушать другие предметы. Например, чтобы усвоить содержание лекций функционального анализа, необходимо прослушать курс по математическому анализу и теории функций комплексного переменного. Для того, чтобы запрограммировать лабораторные работы по теории графов необходимо сдать практику по языкам программирования. На рисунке ниже требуемые соотношения показаны в виде ориентированного графа: дуга $(u, v)$ означает, что предмет $u$ должен быть понят для проведения занятий по предмету $v$ .

предметы в ВУЗе

Топологическая сортировка, тем самым, показывает один из порядков преподавания предметов на данной специальности. Один из таких порядков показан на рисунке ниже, где изучать предметы в показанном порядке. Все дуги идут слева направо.

порядок изучения предметов

Заметим, что данная топологическая сортировка не является единственной и для одного и того же орграфа $G$ может существовать несколько топологически упорядоченных перестановок его вершин. В примере с дисциплинами возможно сначала изучить языки программирования, а потом алгебру. Пример с предметами в ВУЗе является не единственным применением топологической сортировки. В общем случае при помощи выше описанного алгоритма можно построить корректную последовательность выполнения действий, всякое из которых зависит от другого: последовательность установки программ при помощи пакетного менеджера или сборки исходных текстов программ при помощи Makefile’ов.

Асимптотическая сложность

Процесс инициализации массива $color$ осуществляется за $O(|V|)$ .
Процедура TOPOLOGICAL_SORT вызывается ровно по одному разу для каждой вершины $v \in V$ орграфа, так как она вызывается только для белых вершин, то есть еще не обработанных. Первое, что она делает, это помечает переданную в качестве параметра вершину $v$ процедуры как серую, строка $7$ . В процессе выполнения процедуры TOPOLOGICAL_SORT цикл в строках $9 - 13$ выполняется ровно $|adj[v]|$ раз. Так как $\sum_{v \in V} |adj [v]|=O(|E|)$ , то общая стоимость выполнения строк $9 - 13$ процедуры TOPOLOGICAL_SORT равна $O(|E|)$ . В строке $14$ вершина $v$ помечается как черная за $O(1)$ , так как становится обработанной. Добавление черной вершины $v$ в начало списка $topsort$ также можно реализовать за $O(1)$ .
Таким образом, асимптотическая сложность алгоритма поиска топологической сортировки вершин орграфа равна $O(|V|+|E|)$ , то есть такая же, как и асимптотическая сложность алгоритма обхода в глубину.