В этом видео мы обсудим поиск в глубину в ориентированных графах, а также поиск компонент сильной связности. Давайте зададим граф, подгрузим нашу библиотеку, заведем ориентированный граф, зададим у него вершины, зададим ребра. Вот так соединим: A соединим с B, B соединим с C, с D и с E и так далее. И давайте запустим это. Давайте граф нарисуем. Вот у нас получилась такая картинка, и мы задали координаты вершин, задали параметры, которые мы рисуем, тут все точно также. Задали это как функцию, чтобы потом мы могли перерисовать граф, если потребуется. И давайте перейдем к поиску в глубину. Вот он здесь записан, и, на самом деле, здесь ничего по существу не отличается от неориентированного случая — буквально все то же самое. Мы заводим счетчик и будем считать время предобработки и постобработки, заводим соответствующие словари. Команды предобработки и постобработки просто такие же, как и раньше. Заводим словарь для посещенных вершин, говорим про все вершины, что они непосещенные в начале. Дальше заводим функцию исследования вершин, она такая же. Опять же, мы фиксируем, говорим, что вершина посещенная, делаем предобработку по всем непосещенным соседям вершины. И мы запускаем обработку этой вершины, обработку соседа, и делаем постобработку вершины. Хорошо, давайте. Да, и в конце мы запускаем поиск в глубину, берем вершину v из графа, и если она не посещалась, то запускаем в ней ее исследование, и запускаем, собственно, вот эту функцию. Давайте запустим даже. И, собственно, да, вот мы посчитали время пред- и постобработки — они, в общем, тут, естественные. Мы начинаем из A, переходим в B, потом в C, возвращаемся в B, переходим в D, у D есть сосед E, переходим в E, здесь соседи кончились, возвращаемся сюда — в B и в A. И осталась непройденной вершина F, мы проходим ее отдельно, и вот ее время предобработки и постобработки будь самое позднее. У A это ноль и девять, а все остальные вершины между ними, как мы это описали. Хорошо. Но скоро нам потребуется искать компоненты сильной связности, и там нужно будет поиск в глубину запускать для разных графов, и поэтому пришло уже время сделать наш поиск в глубину в виде функции, в которую вершины передаются без глобальных переменных. Давайте перепишем поиск в глубину так, чтобы он работал хорошо и можно было запускать его на любом графе. То есть вот в этом блоке мы сейчас это все сделаем, и поиск в глубину мы в конце запустим, подав ему на вход граф, массив предобработки, словарь предобработки, словарь постобработки и список посещенных вершин. Инициализируем мы их так же, то есть предобработка и постобработка инициализируются как обычно, список посещенных вершин тоже. Счетчик мы можем инициализировать внутри поиска в глубину, то есть в начале поиска в глубину мы можем спокойно инициализировать счетчик, и после этого уже все вершины обрабатывать. Как устроен наш поиск в глубину? Мы по всем вершинам из графа, если они еще не посещались, запускаем процедуру "Explore" и передаем ей все, то есть передаем просто ей все параметры, включая счетчик. Хорошо, дальше эта функция со всеми параметрами делает следующее: она, как и раньше, помечает вершину как посещенную, запускает предобработку, запускает постобработку. Предобработка и постобработка, если мы в них пройдем, мы теперь сделали так, чтобы они возвращали нам счетчик. То есть после того, как они поработали со счетчиком, они его возвращают. И, собственно, вот здесь мы фиксируем этот счетчик, что он изменился внутри пред- и постобработки. А самой пред- и постобработке достаточно передать следующие параметры: нужно передать вершину, в которой мы сейчас находимся, массив предобработки и счетчик, потому что счетчик эта процедура меняет. И она меняет массив предобработки в вершине v, поэтому эти параметры нужны, остальные не нужны, поэтому тут можно остальное не передавать. И дальше мы по всем соседям вершины, если они еще не были посещены, запускаем процедуру исследования этих вершин, и процедура исследования тоже возвращает счетчик после ее работы — тоже мы его возвращаем и фиксируем здесь, чему он равен после запуска этой процедуры. Давайте это запустим, и мы получаем тот же результат, тут ничего по существу не меняется. Просто мы записали это в таком виде, что мы теперь этот поиск можем запускать на любом графе, и мы сейчас этим воспользуемся. Хорошо, компоненты сильной связности — как их искать? Во-первых, надо сразу сказать, что есть встроенная функция. То есть мы можем это сделать встроенной функцией, в библиотеке "NetworkX" есть функция, которая просто выдает нам компоненты сильной связности, давайте ее запустим. И вот, пожалуйста, в нашем графе, давайте поднимемся, она нашла такие компоненты — вершина E. Действительно, очевидно, это отдельная компонента, из нее не выходит ребер. И вершина F будет отдельной компонентой, потому что когда мы вершину E уберем, то в нее нельзя попасть, в вершину F нельзя попасть, поэтому, очевидно, это отдельная компонента. И также еще компонента A, B, C и D — действительно, ведь из любой из этих вершин можно дойти в любую другую, потому что на A, B и C у нас есть цикл, а также есть цикл на A, B и D, поэтому из любой из этих вершин можно дойти в любую другую, поэтому они образуют отдельную компоненту, что нам и выдала эта команда. Вот так можно искать компоненты сильной связности. Давайте, тем не менее, разберемся, как это работает, и давайте реализуем алгоритм поиска компонент сильной связности, который у нас был в лекциях. Как этот алгоритм работал? Для начала мы должны рассмотреть развернутый граф — граф, в котором мы развернули все ребра. И для этого есть специальная команда. Мы применяем команду "reverse", фиксируем, что это будет новая копия графа, и сохраняем ее в "graph_r". Хорошо, давайте для начала нарисуем эти графы — и один, и другой. Давайте, собственно, запустим уже этот блок, чтобы мы увидели, как это все выглядит, потом продолжим с его разбором. Вот изначальный граф нарисован, тут то же самое, что было нарисовано раньше. А вот граф с развернутыми ребрами: действительно, просто все ребра здесь развернулись. Хорошо, как работает наш алгоритм дальше? Мы запускаем поиск в глубину для развернутого графа. Мы заводим для этого графа словари предобработки и постобработки, словарь посещенных вершин, фиксируем все вершины как непосещенные. И дальше запускаем функцию, которую мы сделали чуть раньше, для развернутого графа, для этих массивов и для этого словаря посещенных вершин. И этот алгоритм работает и выдает нам список всех вершин, которые мы посетили, время предобработки и постобработки для всех вершин. Мы здесь упорядочиваем их по вершинам, то есть мы хотим, чтобы это выглядело так, что у нас вершины одна за другой идут, в правильном порядке — от A до F, чтобы просто удобнее был на это смотреть. Вот время пред- и постобработки, давайте посмотрим, как это работает. Мы начинаем с вершины A, у нее время предобработки ноль, и исходящее ребро — здесь их два, в C и D, но первой рассматривается C, мы переходим сюда. После этого из C мы переходим в B. И тут исходящее ребро только в A, поэтому на этом все заканчивается, мы с B заканчиваем, возвращаемся в C, из C еще в D можно сходить. И в D мы тоже сразу заканчиваем, и возвращаемся в C, время постобработки здесь шесть. После этого мы возвращаемся в A, с вершиной A мы закончили. Мы обошли вершины A, B, C и D. После этого остались еще вершины, и мы переходим к вершине E, она следующая по алфавиту, и мы рассматриваем ее, переходим в F. С F заканчиваем, возвращаемся в E — и на этом все заканчивается. Действительно, вот все отработало на развернутом графе, как мы и ожидали. Что мы делаем после этого? Мы после этого запускаем обход компонент связности в нашем изначальном графе. Для этого заводим массив посещенных вершин для этого изначального графа, и дальше делаем следующее. В каком порядке мы это делаем? Мы берем вершины в порядке максимума их времени постобработки в развернутом графе — такой у нас был алгоритм. Как мы будем это реализовывать? Мы возьмем словарь для постобработки, и просто обработанные вершины будем оттуда удалять. Пока этот словарь не пуст, мы делаем следующее: мы напишем, что очередная компонента состоит из следующих вершин, разделять их будем пробелом, и заводим массив пред- и постобработки для этого запуска, заводим текущую вершину, и она будет просто с максимальным временем постобработки в словаре постобработки для развернутого графа. Запускаем в этой вершине процедуру исследования этой вершины. И для всех вершин, которые мы уже обработали в конце этой процедуры, то есть после запуска этой процедуры, мы будем проверять — лежат ли они в массиве постобработки развернутого графа, и если лежат, а мы их обработали, то мы можем их удалить из этого массива, чтобы потом снова выбрать максимум, перейти к следующей компоненте. Вот, собственно, так мы действуем. Давайте мы запустим эту процедуру. Вот она все это обработает. Как она будет работать? Давайте посмотрим. С чего надо начать? Начинаем мы с вершины, у которой максимальное время постобработки в развернутом графе. Оно здесь написано. И, действительно, вот у вершины E оно максимальное. То есть мы начнем с того, что запустим. То есть вот эта вот вершина v, текущая вершина v, в начале будет просто вершиной E, и мы запустим процедуру исследования вершины E в изначальном графе, то есть в этом графе, который на первой картинке нарисован. Из вершины E мы никуда попасть не можем, и мы обработаем только эту вершину. Она станет обработанной, и мы удалим ее из этого словаря постобработки. То есть после первой итерации мы уделяем вот эту вершину E. И дальше смотрим на оставшиеся вершины, у какой вершины будет максимальное время постобработки — у вершины F. И тогда мы для вершины F запустим процедуру исследования. Мы обойдем эту вершину, и вершину E мы уже не обойдем, потому что мы ее уже посещали. То есть когда мы запустим процедуру исследования вершины F, мы в E не пойдем, потому что E мы уже посещали. И после этого мы из массива постобработки развернутого графа удалим только вершину F. То есть во второй компоненте, во втором проходе, во второй итерации мы пройдем вершину F только, и удалим ее из того же словаря. Останутся у нас вершины A, B, C и D. Максимальное время постобработки — у вершины A. И, соответственно, последний, на самом деле это будет последний запуск процедуры "Explore", мы запустим в вершине A. И в вершине A мы обойдем вершину B, C, вернемся в B, попадем в D, и в E уже не пойдем, потому что она будет уже обработана, и это будет последняя вершина, в которой мы запускаем процедуру. Действительно, мы просто выпишем все эти вершины, и на этом все закончится, потому что в конце мы удалим эти вершины из нашего словаря постобработки, и он станет пустой. И как только он станет пустой, то "while" следующий раз уже не запустится, и на этом все закончится.
