Топологическая сортировка (с переименованием)

Пусть задан произвольный DAG (вверху), топологическая сортиров­ка позволяет нам переименовать его вершины так, что каждое ребро ведет из вершины с меньшим номером в вершину с большим номером (внизу). В этом примере мы переименовываем вершины 4, 5, 7 и 8, соответственно, в 7, 8, 5 и 4, как показано в массиве tsI Существует большое число переименований, позволяющих получить требуемые результаты.

Часть 5. Алгоритмы на графах

РИСУНОК 19.22. ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА (С ПЕРЕГРУППИРОВКОЙ)

Эта диаграмма может служить другой точкой зрения на топологическую сортировку, представлен­ную на рис. 19.21; в ней мы определяем способ перегруппировки вершин, а не их переименования. Когда мы группируем вершины в порядке, указанном в массиве is, слева направо, то все ориентированные ребра направлены слева направо. Инверсия перестановки ts есть перестановка tsl, которая определя­ет переименование, описанное на рис. 19.21.

for (i = 0; i < V; i++) tsI[ts[i]] = i;

определяет переименование в векторе tsl, индексированном именами вершин. И наобо­рот, мы можем получить перегруппировку из переименования с помощью цикла

for (i = 0; i < V; i++) ts[tsI[i]] = i;

который помещает первой в список вершину, получающую метку 0, второй вершину, получающую метку 1, и т.д. Чаще всего мы используем термин топологическая сортиров­ка (topological sort) в отношении версии задачи, связанной с перегруппировкой. Обратите внимание на то обстоятельство, что ts не есть вектор, индексированный именами вершин. В общем случае, порядок вершин, установленный топологической сортировкой, не уникален. Например,

суть логические сортировки примера DAG, представленного на рис. 19.6 (существует мно­жество других примеров). В приложении составления расписаний подобная ситуация воз­никает всякий раз, когда одна из задач прямо или косвенно не находится в прямой или непрямой зависимости от другой задачи, и в силу этого обстоятельства она может выпол­няться перед либо после другой задачи (и даже одновременно). Число возможных рас­писаний возрастает экспоненциально с увеличением количества таких пар задач.

Как уже отмечалось, иногда бывает полезно рассматривать ребра орграфа в другом аспекте: когда мы говорим, что ребро направлено из s в t, это означает, что вершина s " зависит" от вершины tНапример, вершины могут представлять термины, определения которых даются в некоторой книге, при этом ребро направлено из s в t, если определе­ние s использует tВ этом случае полезно установить порядок, по условиям которого оп­ределение каждого термина дается перед тем, как оно будет использоваться в другом оп­ределении. Использование подобной упорядоченности соответствует такому построению вершин в линию, что все ребра направлены справа налево — получаем обратную тополо­гическую сортировку (reverse topological sort). Рисунок 19, 23 может служить иллюстрацией обратной топологической сортировки на рассматриваемом нами демонстрационном при­мере DAG.

Глава 19. Орграфы и ориентированные ациклические графы

РИСУНОК 19.23. ОБРАТНАЯ ТОПОЛОГИЧЕСКАЯ СОРТИРОВКА

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

Теперь выясняется, что мы уже рассматривали алгоритм обратной топологической сортировки, таковым является наш старый знакомый — стан­дартный рекурсивный поиск в глубину! Если на вход подать DAG, то нумерация вершин во время об­хода в обратном порядке размещает вершины в по­рядке обратной топологии. Иначе говоря, мы вы­полняем нумерацию каждой вершины как завершающее действие рекурсивной функции DFS аналогично вектору post в программе 19.2, которая представляет собой реализацию поиска в глубину (DFS). Как видно из рис. 19.24, использование та­кой нумерации эквивалентно нумерации узлов в лесе DFS при обходе в обратном порядке и экви­валентно топологической сортировке: вектор post, индексированный по именам вершин, позволяет получить переименование и его инверсию, пока­занные на рис. 19.23, — получается обратная топо­логическая сортировка графа DAG.

Свойство 19.11. Нумерация при обходе в обрат­ном порядке при поиске в глубину представляет со­бой обратную топологическую сортировку для лю­бого графа DAG.

Доказательство: Предположим, что s и t — две вершины, такие, что s появляется раньше t при нумерации в обратном порядке, даже если в

РИСУНОК 19.24. ЛЕС DFS ДЛЯ ГРАФА DAG

Лес DFS заданного орграфа не имеет обратных ребер (ребер, ведущих в узлы с большими номерами в обратном порядке обхода вершин графа) тогда и только тогда, когда этот орграф есть DAG. Ребра, не принадлежащие деревьям в этом DFS лесе для графа DAG, пред­ставленного на рис. 19.21, — это либо прямые ребра (заштрихованные квадра­тики), либо поперечные ребра (незашт­рихованные квадратики). Последова­тельность, в которой посещаются вершины при обходе леса в обратном порядке, показанная в нижней части диаграммы, представляет собой обратную топологическую сортировку (см. рис. 19.23).

Часть 5. Алгоритмы на графах

Глава 19. Орграфы и ориентированные ациклические графы

Доказательство того, что эти вычисления позволяют получить правильное топологи­ческое упорядочение, оставляем вам на самостоятельную проработку (см. упражнение 19.97).

Чтобы реализовать первый из вариантов, перечисленных в предыдущем параграфе в контексте разреженных графов (представленных в виде списков смежных вершин), нам может потребоваться программа 19.1 для вычисления обратного графа. Решение этой за­дачи требует увеличения используемого пространства памяти в два раза, что становится обременительным в случае крупных графов. Что касается насыщенных графов (представ­ленных в виде матриц смежности), то как было отмечено в разделе 19.1, мы можем вы­полнить поиск в глубину на обратном графе, не прибегая к использованию дополнитель­ного пространства памяти или без выполнения дополнительных работ, а только путем простой замены строк на столбцы при обращении к матрице смежности, как показыва­ет программа 19.7.

Далее мы рассмотрим альтернативный классический метод топологической сортиров­ки, которые имеет определенное сходство с BFS (breadth-first search — поиск в шири­ну) (см. раздел 18.7.). Он основан на следующем свойстве графа DAG.

Свойство 19.12. У каждого графа DAG имеется, по меньшей мере, один исток и, по мень­шей мере, один сток.

Доказательство: Предположим, что задан DAG, у которого нет стоков. Тогда, отправ­ляясь из любой вершины, мы можем построить ориентированный путь произвольной длины, следуя из этой вершины вдоль любого ребра в любую другую вершину (суще­ствует, по меньшей мере, одно такое ребро, поскольку у графа DAG нет стоков), с последующим следованием из этой вершины вдоль другого ребра и т.д. Но как толь­ко мы посетим V+ 1 вершину, мы должны попасть в ориентированный цикл в соот­ветствии с принципом картотечного ящика (см. свойство 19.6), что противоречит пред­положению о том, что имеется DAG. Таким образом, что в графе DAG существует, по меньшей мере, один сток. Отсюда также следует, что в каждом графе DAG присутству­ет, по меньшей мере, один исток, ибо исток представляет собой обращение стока. ■

Из этого факта мы можем вывести алгоритм топологической сортировки: пометим любой исток наименьшей неиспользованной меткой, затем удалим его и пометим осталь­ную часть графа DAG, применив тем же алгоритм. На рис. 19.25 показана трассировка этого алгоритма, примененного к рассматриваемому нами примеру графа DAG.

Программа 19.7. Топологическая сортировка___________________________________________

Если использовать данную реализацию функции tsR из программы 19.6, конструктор вычисляет топологическую сортировку, но не ее обращение (для любого DAG это реализация, которая поддерживает функцию edge), поскольку она замещает вызов функции edge(v, w) при поиске в глубину на вызов edge(w, v), тем самым выполняя обработку обратного графа (см. текст).