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