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

Представим себе n чиновников, каждый из которых выдает справки определенного вида. Мы хотим получить все эти справки, соблюдая установленные ограничения: у каждого чиновника есть список справок, которые нужно собрать перед обращением к нему. Дело безнадежно, если схема зависимостей имеет цикл (справку A нельзя получить без B , B без C ,..., Y без Z и Z без A ). Предполагая, что такого цикла нет, требуется составить план, указывающий один из возможных порядков получения справок.

Изображая чиновников точками, а зависимости -- стрелками, приходим к такой формулировке. Имеется n точек, пронумерованных от 1 до n . Из каждой точки ведет несколько (возможно, ) стрелок в другие точки. (Такая картинка называется ориентированным графом.) Циклов нет. Требуется расположить вершины графа (точки) в таком порядке, чтобы конец любой стрелки предшествовал ее началу. Эта задача называется топологической сортировкой.

$\scriptstyle{\blacktriangleright}$ 7.4.1. Доказать, что это всегда возможно.

Решение. Из условия отсутствия циклов вытекает, что есть вершина, из которой вообще не выходит стрелок (иначе можно двигаться по стрелкам, пока не зациклимся). Ее будем считать первой. Выкидывая все стрелки, в нее ведущие, мы сводим задачу к графу с меньшим числом вершин и продолжаем рассуждение по индукции.

$\scriptstyle{\blacktriangleright}$ 7.4.2. Предположим, что ориентированный граф без циклов хранится в такой форме: для каждого i от 1 до n в num[i] хранится число выходящих из i стрелок, в ${\hbox{\tt adr[i][1]}}$ , $\ldots$ , ${\hbox{\tt adr[i][num[i]]}}$ -- номера вершин, куда эти стрелки ведут. Составить (рекурсивный) алгоритм, который производит топологическую сортировку не более чем за $C\cdot({\hbox{\tt n}}+{\hbox{\tt m}})$ действий, где m -- число ребер графа (стрелок).

Замечание. Непосредственная реализация приведенного выше доказательства существования не дает требуемой оценки; ее приходится немного подправить.

Решение. Наша программа будет печатать номера вершин. В массиве

            printed: array[1..n] of boolean

мы будем хранить сведения о том, какие вершины напечатаны (и корректировать их одновременно с печатью вершины). Будем говорить, что напечатанная последовательность вершин корректна, если никакая вершина не напечатана дважды и для любого номера i, входящего в эту последовательность, все вершины, в которые ведут стрелки из i, напечатаны, и притом до i.

     procedure add (i: 1..n);
     | {дано: напечатанное корректно;}
     | {надо: напечатанное корректно и включает вершину i}
     begin
     | if printed [i] then begin {вершина i уже напечатана}
     | | {ничего делать не надо}
     | end else begin
     | | {напечатанное корректно}
     | | for j:=1 to num[i] do begin
     | | | add(adr[i][j]);
     | | end;
     | | {напечатанное корректно, все вершины, в которые из
     | |  i ведут стрелки, уже напечатаны - так что можно
     | |  печатать i, не нарушая корректности}
     | | if not printed[i] then begin
     | | | writeln(i); printed [i]:= TRUE;
     | | end;
     | end;
     end;

Основная программа:

     for i:=1 to n do begin
     | printed[i]:= FALSE;
     end;
     for i:=1 to n do begin
     | add(i)
     end;

К оценке времени работы мы вскоре вернемся.

$\scriptstyle{\blacktriangleright}$ 7.4.3. В приведенной программе можно выбросить проверку, заменив

          if not printed[i] then begin
          | writeln(i); printed [i]:= TRUE;
          end;

на

          writeln(i); printed [i]:= TRUE;

Почему? Как изменится спецификация процедуры?

Решение. Спецификацию можно выбрать такой:

       дано: напечатанное корректно
       надо: напечатанное корректно и включает вершину i;
             все вновь напечатанные вершины доступны из i.`

$\scriptstyle{\blacktriangleright}$ 7.4.4. Где использован тот факт, что граф не имеет циклов?

Решение. Мы опустили доказательство конечности глубины рекурсии. Для каждой вершины рассмотрим ее << глубину>> -- максимальную длину пути по стрелкам, из нее выходящего. Условие отсутствия циклов гарантирует, что эта величина конечна. Из вершины нулевой глубины стрелок не выходит. Глубина конца стрелки по крайней мере на 1 меньше, чем глубина начала. При работе процедуры add(i) все рекурсивные вызовы add(j) относятся к вершинам меньшей глубины. $\scriptstyle\blacktriangleleft$

Вернемся к оценке времени работы. Сколько вызовов add(i) возможно для какого-то фиксированного i? Прежде всего ясно, что первый из них закрасит i, остальные сведутся к проверке того, что i уже закрашено. Ясно также, что вызовы add(i) индуцируются << закрашивающими>> вызовами add(j) для тех j, из которых в i ведет ребро. Следовательно, число вызовов add(i) равно числу входящих в i ребер (стрелок). При этом все вызовы, кроме первого, требуют O(1) операций, а первый требует времени, пропорционального числу исходящих из i стрелок. (Не считая времени, уходящего на выполнение add(j) для концов j выходящих ребер.) Отсюда видно, что общее время пропорционально числу ребер (плюс число вершин). $\scriptstyle\blacktriangleleft$

pvv
1/8/1999