Давайте обсудим обходы ориентированных графов. У нас были обходы для неориентированного случая, и там у нас были поиск в глубину и поиск в ширину. И оказывается, что буквально те же алгоритмы работают и для ориентированных графов, то есть просто можно взять те же самые процедуры, и они буквально переносятся на ориентированные графы. Давайте посмотрим на это на примере поиска в глубину. Вот наша процедура исследования вершины. Запустим поиск в глубину. Мы берем любую необработанную вершину и давайте, как обычно, считать, что мы перебираем вершины в алфавитном порядке и начинаем с вершины A. Запускаем процедуру исследования вершины A. Дальше мы должны пройти по соседям вершины A, и здесь важно, что мы проходим по соседям, в которые ведут ребра из вершины A, то есть мы перебираем те вершины, в которые ведут ребра из вершины А. Такая вершина одна — это вершина B и, соответственно, мы запускаем процедуру для вершины B. Дальше мы должны перебрать соседей вершины B. Их несколько, и мы берем первую из них — C, и запускаем процедуру обхода для вершины C. У вершины C есть исходящие ребра, но они ведут в вершины, которые уже обрабатываются, поэтому мы из вершины C ничего не обходим и заканчиваем обработку вершины C, возвращаемся в вершину B. Сейчас мы находимся в процедуре исследования вершины B. Перебираем ребра дальше и следующее ребро D. Переходим в вершину D, запускаем для нее процедуру исследования. Из вершины D тоже есть исходящее ребро в еще необработанную вершину — вершину E, переходим туда. А вот из вершины E уже никаких ребер нету, и процедура для нее заканчивается сразу, возвращаемся в процедуру для вершины D. Больше не осталось исходящих ребер из вершины D, которые ведут в необработанные вершины, поэтому мы для D тоже заканчиваем процедуру. Точно так же заканчиваем процедуру и для B, и для A. Дальше мы делаем полный поиск в глубину, и поэтому мы должны посмотреть на еще необработанные вершины. Такая вершина одна, запускаем процедуру для нее. Она сразу заканчивается, потому что есть одно ребро из вершины F, и оно ведет в уже обработанную вершину, поэтому процедура обработки для F уже заканчивается, и на этом обход нашего графа закончился. Напомним, что в качестве предобработки и постобработки вершины, например, просто можно считать время, когда мы эту обработку совершили. То есть в качестве предобработки вершины мы фиксируем время предобработки и увеличиваем счетчик, и то же самое для постобработки. И для любой вершины у нас получается два числа: время предобработки и время постобработки. Давайте вспомним, как они были устроены, и на примере ориентированного графа все это разберем. У нас изначальный счетчик, мы положим его равным нулю, и зафиксируем время предобработки и постобработки всех вершин. Давайте пройдем еще раз по этому графу. Мы начинаем с вершины A, ее время предобработки фиксируем равным нулю, и счетчик увеличивается. Дальше мы переходим в вершину B, счетчик у нас увеличивается (он увеличивается после каждого действия на единицу), и время обработки B у нас единица. Дальше, следующим шагом, мы заходим в вершину C, фиксируем это во времени предобработки вершины C. Дальше мы возвращаемся в вершину B, потому что из вершины C не было исходящих ребер в новые вершины, и время постобработки C становится равным трем. Переходим в вершину D, ее время предобработки четыре. Дальше время предобработки вершины E — это пять. Заканчиваем с E, ее время постобработки шесть. Для D у нас будет время постобработки семь. Возвращаемся в B — постобработка восемь, постобработка A — это девять. И дальше переходим в вершину F, ее время предобработки 10, а время постобработки 11. Итак, мы посчитали эти параметры для всех вершин. Дальше давайте посмотрим на ребра графа и заметим, что у нас есть четыре типа ребер. Во-первых, есть древесные ребра — это ребра, по которым мы проходили в обходе нашего графа (они выделены синим цветом на картинке). Давайте посмотрим на эти параметры для древесных ребер и, на самом деле, будем смотреть на две вещи. Во-первых, будем смотреть на отрезки от pre до post (от времени предобработки до времени постобработки вершины), а также мы будем смотреть на величину постобработки вершин. Заметим, что для древесных ребер в конечной вершине отрезок будет вложен в отрезок для начальной вершины, а post, соответственно, будет меньше. Например, давайте посмотрим на ребро из B в C: мы вершину C обработали во время обработки вершины B, то есть мы запустили обработку после начала обработки вершины B, закончили эту обработку, и только потом вернулись в вершину B и закончили обработку вершины B. Так что отрезок для C будет вложен в отрезок для B, и, соответственно, время постобработки будет меньше. Дальше, у нас есть прямые ребра в графе — это ребра, по которым мы не проходили, но они ведут из вершины на нашем дереве в ее последователя, не в непосредственно потомка, но в последователя — вершину, которая находится ниже в дереве. Например, вот на этой картинке такое ребро одно: из вершины B в вершину E. Давайте посмотрим на параметры для нее. Опять же, можно заметить, что отрезок от предобработки до постобработки для более поздней вершины (для конца ребра) вложен в отрезок для начальной вершины. Действительно, мы вершину E обработали позже вершины B: из вершины B мы запустили обработку вершины D, потом запустили обработку вершины E и закончили ее до того, как закончили обработку вершины B. То есть мы начали обработку вершины E после начала вершины обработки B, а закончили обработку вершины E до того, как закончили обработку вершины B. Соответственно, отрезок для E (от пяти до шести) будет вложен в отрезок для B (от одного до восьми), так что эти отрезки тоже вложены, и время постобработки вершины E будет меньше, чем время постобработки вершины B. Дальше. Также есть обратные ребра, они ведут из вершин в этих деревьях в их предшественника. Например, на этой картинке таких ребра два: из C в A и из D в A. То есть из какой-то вершины дерева ребро ведет в вершину, которая находится в этом дереве выше. Давайте посмотрим на отрезки: здесь они вложены в обратную сторону, то есть у нас отрезок для конца ребра больше, чем отрезок для начала ребра. Просто отрезок для вершины C вложен в отрезок для вершины A, причины здесь те же самые: мы, запустив обработку вершины A, прошли вершину B, потом прошли вершину C, закончили с вершиной C и только после этого, через какое-то время, закончили с обработкой вершины A. Тут разница, по сравнению с прямыми ребрами, только в том, что ребро ведет в обратную сторону, поэтому отрезки вложены тоже в обратную сторону: отрезок в конце ребра больше, чем отрезок в начале. И поэтому вот здесь все наоборот: время постобработки в конце ребра больше, чем время постобработки в начале. В двух предыдущих случаях было наоборот: время постобработки в конце было меньше. Хорошо. Есть четвертый тип ребер, когда мы сравниваем несравнимые вершины в этих деревьях — перекрестные ребра, то есть у нас на этой картинке таких ребер два: D и C и ребро из F в E. Это могут быть ребра, которые соединяют вершины в одном и том же дереве. В дереве, с которого начиналась вершина A, у нас есть ребро из D в C, и эти ребра соединяют несравнимые вершины, то есть те, для которых ни одна из вершин не находится выше другой, они просто в разных ветках дерева (вот такое ребро у нас из D в C). А также есть случаи, когда эти ребра просто из разных деревьев. Например, у нас есть отдельное дерево для вершины F (мы вершину F обрабатывали отдельно), и у нас из нее есть ребро в какую-то вершину первого дерева, и тоже это называется перекрестным ребром. Давайте посмотрим, что происходит с ними: для них отрезки от предобработки до постобработки просто не пересекаются. Действительно, мы начали обрабатывать вершину C в какой-то момент, закончили ее обрабатывать, и только после этого начали обрабатывать вершину D. Так что отрезки для C и D не пересекаются: мы сначала закончили с вершиной C, а потом перешли к вершине D. И аналогично для E и F: мы сначала закончили с вершиной E, а потом обработали вершину F отдельно, отрезки получились непересекающимися. Тут давайте тоже заметим, что время постобработки в конце ребра будет меньше. Почему? Раз мы по этому ребру не прошли в нашем обходе, значит, вершина в конце была обработана раньше, чем вершина в начале ребра. Когда мы обрабатываем вершину D, вершина C уже должна быть обработана, то есть мы уже ее начали обрабатывать, поэтому мы ее не посещаем из вершины D (мы посетили ее уже раньше). Но поскольку отрезки не пересекаются, то мы вершину C так же и закончили обрабатывать до того, как обработали вершину D. Поэтому отрезок для C идет просто раньше, чем отрезок для D. В частности, время постобработки для C меньше, чем время постобработки для D. Таким образом, мы из этого анализа видим, что время постобработки по всем ребрам в конце меньше, чем в начале, кроме одного случая — кроме обратных ребер. И теперь с помощью этого алгоритма мы можем проверять, есть ли в графе обратные ребра. Как мы это делаем? Мы просто перебираем все ребра и проверяем, бывает ли такое, что вдоль ребра увеличивается время постобработки, то есть время постобработки в конце ребра больше, чем в начале? Мы убедились, что это бывает только для обратных ребер. Почему это важно? Оказывается, что это позволяет проверять граф на ацикличность. Утверждается, что в графе есть цикл только тогда, когда в нем есть обратные ребра. Давайте это проверим. Действительно, если есть обратное ребро, то есть цикл. Обратное ребро ведет из более поздней вершины в более раннюю вершину в дереве, то есть мы можем тогда, если оно есть, пройти сначала из более ранней вершины в более позднюю по ребрам дерева (по древесным ребрам), и потом вернуться по обратному ребру — получить цикл. Так что, если есть обратные ребра, то цикл точно есть. Но верно и обратное: если в графе есть цикл, то тогда обязательно в нашем обходе встретится обратное ребро. Посмотрим на первую вершину, которая попала в обход (первую вершину этого цикла): если мы запустим процедуру исследования этой вершины, то мы также обойдем все вершины, которые достижимы из этой вершины. В частности, мы обойдем все вершины цикла, то есть среди последователей нашей вершины в дереве будут все вершины нашего цикла. А в частности, значит, будет и обратное ребро, то есть из последней вершины этого цикла будет ребро в нашу вершину, которую мы начали рассматривать первой в этом цикле, — это и будет обратное ребро.
