8.3. Поиск в глубину для ориентированных графов: топологическая сортировка и смежные вопросы

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

В общем, в этом разделе мы будем рассматривать ориентированные графы.

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

Ациклическим называется ориентированный граф, в котором нет (ориентированных, конечно) циклов.

Контрольный вопрос 8.11:

Понимаете ли вы, что этот класс намного шире, чем деревья? Т.е. что ациклический граф — это не только ориентированное дерево?

Самая основная задача, которая может быть поставлена на ациклических графах — это топологическая сортировка (сокращённо топсорт) такого графа. Несмотря на страшное название, на самом деле это просто. Задача состоит в том, чтобы пронумеровать вершины графа так, чтобы все ребра шли из вершин с меньшим номером в вершину с большим. Или, говоря по-другому, расположить вершины на прямой так, чтобы все ребра шли слева направо. Классическая легенда задачи гласит: есть \(N\) дел, которые надо сделать. При этом про каждое дело известно, какие дела надо сделать обязательно до него (и, соответственно, известно, какие надо сделать после). Требуется определить порядок, в котором нужно делать эти дела.

Очевидно, что, если в графе есть циклы, то задача решения не имеет. Оказывается, если циклов нет, то задача имеет решение; как вы уже, наверное, догадались, доказывать мы это будем предъявлением соответствующего алгоритма.

На самом деле есть два довольно существенно разных алгоритма решения этой задачи. Первый вообще не использует идеи поиска в глубину [1], довольно очевиден идейно, но не очень тривиален в реализации. Он приведён в «Искусстве программирования для ЭВМ» Кнута и потому я буду называть его методом Кнута (он используется редко, и я не знаю, есть ли у него стандартное название. Кстати, когда говорят «алгоритм топологической сортировки», обычно понимают не этот, а второй). Состоит этот алгоритм в следующем: в любом ациклическом графе точно есть «сток», т.е. вершина, из которой не выходит ни одного ребра (т.е. вершина, у которой исходящая степень равна нулю). Очевидно, её можно поставить последней. После этого как бы мы ни ставили остальные вершины, проблем с рёбрами, идущими в эту вершину, не возникнет: они в любом случае будут идти направо. Тогда эту вершину вместе со всеми входящими в неё рёбрами (а исходящих, мы помним, нет) можно выкинуть из графа. Получившийся граф также будет ациклическим, и в нем тоже обязательно будет сток. Поставим его на предпоследнее место в массиве и выкинем из графа. И так далее. Очевидно, что в итоге все получится: поскольку каждую вершину мы ставили только тогда, когда она становилась стоком, то проблем ни с какими рёбрами не получится.

(Собственно, примерно так, наверное, люди и поступают в реальной жизни. Если у вас есть \(N\) дел, которые надо сделать, и есть зависимости между делами, то вы выберете дело, которое можно сделать прямо сейчас, которое не зависит от других, и начнете с него, и т.д.)

Кстати, я надеюсь, очевидно, почему в любом ациклическом графе обязательно найдётся сток? Если его нет, то встанем в произвольную вершину. Из неё есть выходящее ребро — пойдём по нему. Дальше опять найдётся выходящее ребро — и т.д. Гулять по графу мы сможем до бесконечности, а это обозначает, что вершины обязательно повторятся — найдётся цикл. Противоречие.

Таким образом, алгоритм: находим какой-нибудь сток, ставим его на последнее место в выходном массиве, выкидываем его (а на самом деле просто помечаем в соответствующем массиве, что он выкинут, и в будущем при расчёте исходящей степени не учитываем его). Дальше находим новый сток и т.д., пока не расставим все вершины. Если на очередном шагу стока не найдётся, значит, граф не ациклический. Заметьте, что мы таким образом доказали, что любой ациклический граф можно оттопсортить.

В простейшей реализации этот алгоритм будет работать за \(O(V^3)\): действительно, каждый поиск стока занимает \(O(V^2)\): перебрать все вершины и для каждой посчитать исходящую степень — а таких поисков надо сделать \(V\). Но можно на самом деле все ускорить, и в итоге получить программу, работающую за \(O(E)\) (как всегда, при условии, что граф хранится списком смежных вершин).

Задача 8.12:

Напишите эту программу в простейшем варианте. Попробуйте придумать, как можно заставить её работать быстрее. На самом деле это делается в два этапа: во-первых, заметим, что каждый раз пересчитывать исходящую степень не надо, а на втором этапе вам пригодится структура данных очередь или стек. Попробуйте придумать это сами. Если не придумаете, то смотрите подсказки, которые есть по этому заданию (впрочем, как и по некоторым другим). Обязательно потом прочитайте подсказки и ответ.

Кстати, замечу, что, очевидно, вместо стоков можно точно также использовать истоки — вершины, у которых входящая степень равна нулю, и вообще, задача топологической сортировки обладает соответствующей симметрией: если обратить все ребра, то искомый порядок вершин тоже просто обратится.

Вышеприведённый алгоритм на самом деле очень интересен, а две идеи его ускорения весьма красивы. Но перейдём ко второму алгоритму, который напрямую использует поиск в глубину. Давайте, как и в первом алгоритме, будем заполнять выходной массив справа налево, т.е. от больших номеров к меньшим. Подумаем, когда можно поставить некоторую вершину? Очевидно, лишь после того, как поставлены все вершины, в которые из нашей идут ребра. Получаем следующую процедуру, ставящую вершину \(i\) в выходной массив:

Перебрать все ребра, выходящие из вершины i,
и поставить в выходной массив вершины, в которые эти ребра идут.
После этого поставить нашу.

Но как мы будем ставить эти самые вершины, «в которые эти ребра идут»? Очевидно, рекурсивным вызовом! Только не забудем проверить, а вдруг эта вершина уже поставлена в выходной массив. А тогда это есть вылитый поиск в глубину:

procedure put(i:integer);
begin
if was[i]<>0 then exit;
was[i]:=1;
for j:=1 to n do
    if gr[i,j]<>0 then
       put(j);
записать вершину i в выходной массив;
end;

Итак, ещё раз. Процедура \(put\) ставит вершину \(i\) в выходной массив. Прежде чем туда её поставить, она пытается поставить туда все вершины, которые должны идти после \(i\)-ой (напомню, что массив мы заполняем с конца); естественно, это делается рекурсивным вызовом. После того, как это выполнено, можно непосредственно поместить \(i\) в выходной массив.

То же можно сказать немного по-другому: процедура убеждается, что \(i\)-я вершина уже стоит в выходном массиве. Если стоит, то ок, иначе процедура помещает её туда с соблюдением всех мер предосторожности. А именно, прежде чем поместить вершину в массив, она перебирает все вершины, которые должны идти после \(i\)-ой и убеждается (рекурсивным вызовом, конечно), что эти вершины там уже стоят. Таким образом, после вызова \(put(j)\) \(j\)-я вершина точно будет в выходном массиве. Массив \(was\) здесь фактически как раз обозначает, находится ли вершина уже в выходном массиве или нет.

(На всякий случай замечу довольно очевидную на мой взгляд вещь: здесь у нас, вообще говоря, есть две схемы нумерации вершин: одна — так, как они заданы во входном файле, вторая — искомая при топологической сортировке. Везде под номеров вершины я понимаю, конечно, номер её так, как она задана во входном файле.)

Как реализовать последнюю строчку в приведённой выше процедуре? Очевидно. Заведём глобальный массив \(out\), в котором будем формировать результат сортировки, и счётчик \(pos\), который будет указывать, какую позиция мы сейчас будем заполнять (т.е. первую свободную позицию при движении справа налево). Изначально \(pos=n\): заполнение массива начинаем справа. Тогда получаем следующий алгоритм топологической сортировки (для единообразия переименовал процедуру \(put\) в \(find\)):

procedure find(i:integer);
begin
if was[i]<>0 then exit;
was[i]:=1;
for j:=1 to n do
    if gr[i,j]<>0 then
       find(j);
out[pos]:=i;
dec(pos);
end;

...
fillchar(was,sizeof(was),0);
pos:=n;
for i:=1 to n do
    find(i);

Обратите внимание, что вызывать поиск в глубину приходится циклом: ясно, что, запустившись из случайной вершины, мы не обязательно обойдём весь граф, даже если он связен (а тем более если он несвязен). Можно это же сказать и по-другому: чтобы оттопсортить граф, нам надо убедиться, что все его вершины стоят в выходном массиве. Поэтому надо запустить процедуру \(find\) из всех вершин.

Задача 8.13:

(простое) Так ли ясно? Приведите пример связного ориентированного графа, на котором однократно запущенный поиск в глубину не обойдёт все вершины. Не забудьте, что связный ориентированный граф — это такой, который будет связным, если забыть про ориентацию его рёбер. Вспомните доказательство того, что поиск в глубину в неориентированном графе обходит всю компоненту связности, и поймите, почему это доказательство не работает в случае ориентированного графа.

Обратите внимание, как просто. Десяток строк — и решена такая нетривиальная задача. И думать почти ничего не надо, т.к. это просто поиск в глубину. Но идеи очень глубокие, они ещё активно всплывут в динамическом программировании, например. (Приведённый выше «алгоритм Кнута» тоже, наверное, можно реализовать так коротко, только там думать надо…)

Сложность, как и всегда у поиска в глубину, у приведённого выше алгоритма \(O(V^2)\), а, если граф хранить списком соседних вершин, то \(O(E)\).

8.3.2. Проверка графа на ацикличность

Как проверить граф на ацикличность? На самом деле все очень просто. Кажется, точно также, как проверять неориентированный граф на то, является ли он лесом, только, может быть, ещё проще. Встанем в произвольную вершину и пойдём поиском в глубину. Если хоть раз вернёмся туда, где уже были, значит, граф точно не ациклический. Хотя… Нет! Ничего подобного!

Задача 8.14:

Приведите пример ациклического графа, в котором мы при поиске в глубину попадём в вершину, в которой уже были раньше.

Что же делать? Пожалуй, я могу предложить два варианта. Первый: на самом деле, если подумать, цикл найдётся, если мы вернёмся в ту вершину, которую ещё не закончили обрабатывать. Т.е. теперь введём три состояния вершин: в которой мы ещё не были, которую мы начали обрабатывать, но ещё не закончили, и которую мы уже обработали (их часто называют, соответственно, белыми, серыми и чёрными). Т.е. теперь массив \(was\) кроме значений 0 и 1 будет принимать ещё значение 2: вершины, которую мы обработали до конца; это значение мы будем устанавливать на выходе из процедуры \(find\). Если немного подумать, то мы нашли цикл тогда и только тогда, когда вернулись в серую вершину:

procedure find(i:integer);
begin
if was[i]=1 then
   граф не ациклический
if was[i]<>0 then
   exit;
was[i]:=1;
for j:=1 to n do
    if gr[i,j]<>0 then
       find(j);
was[i]:=2;
end;

Действительно, в каждый момент «серые» вершины (у которых \(was=1\)) образуют путь в графе, в точности соответствующий стеку вызовов процедуры \(find\). Если мы вернулись в одну из них, то мы точно нашли цикл. Если немного подумать, то верно обратное: что, если граф не ациклический, то мы хотя бы один цикл найдём. Можете над этим подумать, это может быть с ходу не очевидно.

Есть второй, совершенно тупой, алгоритм проверки графа на ацикличность: запустим вышеприведённый алгоритм для топологической сортировки (использующий поиск в глубину, а не «алгоритм Кнута»). Он в любом случае выдаст какую-то последовательность вершин. Если граф ацикличный, то это будет решение задачи о топсорте. Если граф не ацикличный, то это точно не будет решением задачи о топсорте, т.к. в неацикличных графах она решения не имеет. Значит, можно просто проверить, верно ли, что все ребра идут слева направо в полученном графе, и, если да, то граф ациклический, иначе нет.

Задача 8.15:

Попробуйте понять, почему в вышеприведённой идее нельзя в лоб заменить алгоритм топсорта с помощью поиска в глубину на «алгоритм Кнута». Но «алгоритм Кнута», конечно, также несложно приспособить для проверки графа на ацикличность; придумайте, как.

Все эти алгоритмы тоже, конечно, работают за \(O(V^2)\) или \(O(E)\) в зависимости от способа хранения графа.

8.3.3. Компоненты сильной связности

Говорят, что две вершины \(u\) и \(v\) находятся в одной компоненте сильной связности ориентированного графа, если существует (ориентированный, конечно) путь как из \(u\) в \(v\), так и назад. Несложно видеть, что, если \(u\) и \(v\) находятся в одной компоненте сильной связности и \(v\) и \(w\) тоже, то и \(u\) и \(w\) тоже находятся в одной компоненте сильной связности (это свойство называется транзитивностью). Поэтому можно разбить все вершины на компоненты сильной связности так, что каждая вершина будет ровно в одной компоненте; на рисунке справа приведён пример ориентированного графа и разбиения его на компоненты сильной связности (здесь их три).

../_images/graph.12.png ../_images/graph.21.png

Задача 8.16:

Зачем требовать транзитивность? Давайте я попробую определить компоненты слабой связности следующим образом: две вершины \(u\) и \(v\) находятся в одной компоненте слабой связности, если хотя бы в одну сторону есть путь, т.е. или есть путь из \(u\) в \(v\), или назад, или и туда и туда. Имеет ли смысл такое определение? Т.е. сумеете ли вы в любом графе разбить все вершины на компоненты слабой связности?

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

Итак, поставим задачу нахождения сильносвязных компонент графа. Есть известный алгоритм их поиска. Я не знаю, как до него можно додуматься самим, и его не так просто доказать (в Кормене есть двухстраничное доказательство его, которое я с большим трудом осознал; я также читал и более простые доказательства, но не видел ни одного, которое можно было бы запомнить и потом легко воспроизвести), поэтому я его доказывать не буду.

Итак, алгоритм следующий. Сначала запустим алгоритм топологической сортировки поиском в глубину — он выдаст нам некоторую последовательность вершин (конечно, в случае неациклического графа она не будет решением задачи о топсорте, но какая-то последовательность вершин получится). После этого сделаем следующее: запустим поиск в глубину ещё раз, но будем двигаться по инвертированным рёбрам, а во внешнем цикле поиска будем просматривать вершины в том порядке, в котором нам их выдал топсорт. Т.е. обратим направление каждого ребра графа и запустим поиск в глубину, перебирая во внешнем цикле вершины в этом особом порядке. Утверждается, что те «компоненты связности», которые вы найдёте при втором поиске, как раз и будут сильносвязными компонентами исходного графа.

procedure find(i:integer);
var j:integer;
begin
if was[i]<>0 then
   exit;
was[i]:=1;
for j:=1 to n do
    if gr[i,j]<>0 then
       find(j);
ts[pos]:=i;
dec(pos);
end;

procedure find2(i:integer);
var j:integer;
begin
if was[i]<>0 then
   exit;
was[i]:=nc;
for j:=1 to n do
    if gr[j,i]<>0 then
       find2(j);
end;

...
fillchar(was,sizeof(was),0);
pos:=n;
for i:=1 to n do
    find(i);
fillchar(was,sizeof(was),0);
nc:=0;
for i:=1 to n do
    if was[ts[i]]=0 then begin
       inc(nc);
       find2(ts[i]);
    end;

Ещё раз обратите внимание, как алгоритм состоит из двух частей: первые четыре строки в основном алгоритме — топсорт, остальное в точности повторяет поиск обычных компонент связности в неориентированно графе. Обратите внимание, что для них используются разные процедуры find, поскольку, хотя обе процедуры реализуют поиск в глубину, но они делают разные вещи в дополнение к собственно поиску.

Ещё замечу, что тут стандартная ошибка — в рекурсивном вызове во второй процедуре вызвать первую, а не вторую, т.е. написать

procedure find2(i:integer);
...
    if gr[j,i]<>0 then
       find(j);

Всегда, когда у вас в программе есть две процедуры с похожими именами, следите, чтобы их не перепутать. Особенно если эти процедуры рекурсивны — не перепутайте, где какую функцию в рекурсивном вызове вызывать. Даже более общее утверждение: если есть два похожих куска кода, особенно внимательно просмотрите, не сглючили ли вы где-нибудь. Например, если у вас два поиска в глубину по двум разным графам, не перепутайте графы внутри процедур, не перепутайте рекурсивные вызовы и т.д. Особенно это важно, если один блок вы получаете копирование из другого.

Ещё обратите внимание, что во втором поиске используется \(gr[j,i]<>0\): поиск идёт в инвертированном графе.

В общем, как я уже сказал, я не знаю, как до этого алгоритма можно дойти, и не знаю, как его легко доказать. Поэтому имхо этот алгоритм нужно примерно запомнить. Собственно, запоминать тут нечего: два поиска в глубину, причём второй — в инвертированном графе. Единственное, что не очевидно, как запомнить, — это то, в каком порядке стоит перебирать вершины при втором поиске в глубину. Но это легко восстанавливается: представьте себе ациклический граф. В нем, очевидно, каждая компонента сильной связности — это отдельная вершина. Очевидно, что такие компоненты мы получим, только если будем второй поиск запускать в порядке, который мы получим из топсорта (не забудьте, что второй поиск — в инвертированном графе!). Конечно, это не очевидно, а надо представить себе ациклический оттопсорченный граф в уме и просто прикинуть, какие последствия будут у разных порядков выбора вершин. Если все ещё не понятно, то нарисуйте оттопсорченный ациклический граф и попробуйте в нем позапускать поиск в глубину в инвертированном графе, перебирая вершины слева направо, справа налево и т.п.

В общем, по-моему, этот алгоритм довольно легко можно запомнить.

Задача 8.17:

(нетривиальное) Не очевидно, что не работает такой алгоритм: оттопсортим граф и пойдём поиском в глубину в неинвертированном графе справа налево, т.е. от последних вершин к первым. Придумайте контрпример к этому алгоритму (конечно, придумать контрпример проще, чем доказать корректность :) ).

8.3.4. Конденсация графа

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

../_images/graph.21.png ../_images/graph.3.png

Выше приведён пример ориентированного графа с выделенными компонентами сильной связности (то же, что и выше, в теме про компоненты сильной связности), и его конденсации. Поскольку компонент сильной связности три, то и вершин в конденсированном графе три, соответствующие этим самым компонентам.

Задача 8.18:

Докажите, что конденсация произвольного графа является ациклическим графом.

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

В чем смысл конденсации? Ну например вот в чем. Пусть у нас есть набор объектов, про которые известно, что их можно в каком-то смысле упорядочить, и пусть про некоторые пары объектов дано утверждение вида «первый объект меньше или равен второго» (а про остальные пары ничего не известно). Ясно, что этому соответствует ориентированный граф. Несложно понять, что компоненты сильной связности такого графа — это множества объектов такие, которые точно должны быть равны: ведь каждый из них получается меньше или равен сам себя. Тогда логично эти объекты объединить в одну вершину, ведь они все равны между собой. Осталось определить отношения между такими «классами», т.е. про некоторые классы сказать, что «объекты одного класса меньше или равны объектов другого класса». Если пользоваться только теми отношениями, которые нам даны с самого начала, и не пытаться получить дополнительных следствий из них, то то что нам надо — это как раз и есть конденсация начального графа.

Замечу, что если бы с самого начала были даны условия вида «один объект строго меньше второго», то граф был бы обязан быть ациклическим. Ясно, что в этом случае задача конденсации большого смысле не имеет (конденсация ациклического графа есть сам этот граф, т.к. каждая компонента сильной связности тут состоит из одной вершины), но может иметь смысл задача поиска какого-нибудь порядка объектов, не противоречащего этим условиям — а это делает топсорт.

Ещё замечу, что можно поставить задачу так: базируясь на данных нам условиях об объектах, перечислить наибольшее возможное количество пар объектов, про которые мы можем сделать аналогичное утверждение. Здесь придётся пользоваться транзитивностью отношения «меньше» (или «меньше или равно», в зависимости от того, какие условия нам даны): т.е. тем, что, если \(a<b\), а \(b<c\), то \(a<c\). Т.е., если нам даны условия

\[a<b,\quad b<c,\quad b<d,\]

то мы должны сказать, что \(a<b\), \(a<c\), \(a<d\), \(b<c\), \(b<d\), но про \(c\) и \(d\) ничего сказать не можем. Такая задача называется транзитивным замыканием графа, она не решается ни одним из рассмотренных выше алгоритмов, она решается алгоритмом Флойда — к поиску в глубину он имеет мало отношения.

8.3.5. Времена входа и выхода

Очень часто при обсуждении поиска в глубину вводят такие понятия, как времена входа и выхода. А именно, заведём глобальный счётчик «времени» \(t\) и каждый раз, когда мы первый раз начинаем обработку очередной вершины (входим в неё), и каждый раз, когда заканчиваем обработку вершины (выходим из неё) будем увеличивать \(t\) на единицу, а полученное значение записывать как «время входа» или «время выхода» в/из этой вершины, соответственно. Т.е. получим следующий алгоритм:

procedure find(i:integer);
begin
if was[i]<>0 then
   exit;
was[i]:=1;
inc(t);
s[i]:=t;
for i:=1 to n do
    if gr[i,j]=1 then
       find(j);
inc(t);
f[i]:=t;
end;


...
fillchar(was,sizeof(was),0);
t:=0;
for i:=1 to n do
    find(i);

Здесь \(s\) — массив времён входа (т.е. \(s[i]\) — время входа в \(i\)-ю вершину), а \(f\) — аналогичный массив времён выхода. Перед запуском поиска в глубину занулим переменную \(t\).

Обратите ещё раз внимание, что при работе этого алгоритма каждый элемент массива \(s\) будет установлен ровно один раз (т.е. каждый элемент будет установлен: не будет вершин, у которых время входа останется неопределённым — и никакой элемент не будет переписываться: не будет такого, что мы сначала в \(s[i]\) запишем одно значение, а потом туда же другое), поскольку каждую вершину мы обрабатываем ровно один раз. Аналогично с массивом \(f\).

Ещё обратите внимание, что массив \(was\) теперь не нужен, вместо него можно использовать массив \(s\) (но не \(f\)!), только, конечно, тогда \(s\) нужно будет предварительно занулить. Или, что то же самое, времена входа можно хранить в массиве \(was\), а не в \(s\) (как раньше мы номер компоненты связности хранили в \(was\)). Здесь я использую \(s\) только для наглядности.

Но в реальных задачах времена входа и выхода, как правило, не бывают нужны. Они часто помогают в теоретических рассуждениях, иногда бывают нужны в очень продвинутых алгоритмах, но в простых случаях их вычислять обычно не нужно; более того, как мне кажется, нередко понять алгоритм проще, если не обращаться к понятию времён входа/входа. Например, часто при описании алгоритмов употребляется фраза «отсортируем вершины по временам выхода» (реже по временах входа), но это не значит, что нужно вычислять эти времена, а потом писать sort или что-нибудь подобное. Все делается намного проще.

Задача 8.19:

Как надо правильно и проще всего сортировать вершины по временам выхода? Аналогично по временам входа.

Обязательно прочитайте ответ к этой задаче! (Конечно, только после того, как порешаете сами).

[1]Ну, конечно, можно, наверное, найти какие-нибудь идейные сходства у этих двух алгоритмов, и даже, может быть, можно, сильно помучившись, попытаться объявить, что в каком-то смысле они одинаковы…Но, может быть, это вообще верно для любых двух решений одной и той же задачи? :)