Давайте обсудим, как работать с достижимостью, связностью и поиском в Python. Давайте для начала зададим граф: мы загружаем библиотеку, заводим граф, добавляем вершины и ребра, давайте это запустим. Хорошо. Давайте нарисуем граф так, что при этом это было похоже на то, как мы рисуем граф в слайдах, этот кусок мы уже поговаривали, давайте просто запустим его, получился вот такой граф у нас. Дальше — достижимость. Для этого есть просто команда в нашей библиотеке "has_path", и мы даем нашей команде на вход сам граф и пару вершин, для которых мы хотим проверить достижимость, например, для вершин E и A мы можем проверить достижимость, на картинке видно, что они достижимы. Давайте запустим, тем не менее, команду, и это оказалось действительно так, а вот если я, например, вместо E напишу F, то вершины уже недостижимы друг из друга, и тогда у меня будет "False". Хорошо, достижимость проверяется следующим образом. Мы также можем проверить и связность графа. Для этого просто есть отдельная команда "is_connected", то есть мы подаем ее на вход в граф, и она проверяет связность этого графа. Давайте запустим, граф получился не связный. Действительно, видно, что у нас граф не связный, и вершина F отдельно, из нее никуда не дойдешь. Давайте немножко поправим граф, добавим ребро между E и F, давайте его перерисуем и снова запустим, проверим на связность. Запускаем, граф перерисовался, появилось ребро между E и F, видно, что вот здесь его не было, а теперь оно появилось, и связность стала истинной, то есть действительно теперь граф связен. Хорошо. Давайте теперь обсудим, как реализуется поиск в глубину на Python. Давайте проговорим снова все это. Мы хотим в этом графе, я думаю, что мы хотим, на самом деле, граф, который у нас был до этого, без добавления ребра, давайте мы его зададим. И теперь; вот у нас поиск в глубину, давайте его просто запустим. Он посчитает нам, у нас будет пред- и постобработка, у нас будет счетчик времени, то есть мы заводим счетчик времени, заводим словари для предобработки, для постобработки, заводим команду предобработки и команду постобработки, она просто состоит в том, что мы увеличиваем счетчик и зафиксируем время предобработки и постобработки вершины. Здесь есть небольшая тонкость, что у нас счетчик — это глобальная переменная, и это число, поэтому нам придется ее передавать в эти функции как глобальную, и тут ничего не поделаешь. Можно ее сделать локальной, но давайте для простоты пока не передавать ее между функциями, давайте для простоты пока реализуем это таким образом. Хорошо. Дальше мы заводим опять же словарь для посещенных вершин, где мы будем хранить посещенные вершины, и мы фиксируем, что все вершины у нас непосещенные, то есть мы для всех вершин фиксируем, что они не посещены пока. Дальше мы описываем нашу процедуру исследования вершины, процедуру "Explore". Она делает следующее, она помечает вершину как посещенную и делает предобработку, запускает ту же процедуру рекурсивно на всех соседях, которые еще не были посещены, и дальше делает постобработку вершины. Дальше мы запускаем поиск в глубину для всех вершин графа, если мы еще не посетили — запускаем исследование этой вершины. И действительно, мы получим ровно те результаты, которые мы получали до этого. Давайте, на самом деле, вот в этом месте перерисуем наш граф, чтобы нам было удобно это смотреть, просто здесь в конце добавим перерисовывание графа, вот он появился. Действительно, мы начинаем из вершины A, время предобработки у нее ноль, переходим в B, время предобработки один, дальше в C, предобработки время два, из C мы никуда уже не переходим, возвращаемся в B, время постобработки C — это три, дальше переходим в D — предобработка четыре, в E —предобработка пять, заканчиваем с E — тут шесть, заканчиваем с D — здесь семь, заканчиваем с B — здесь восемь, заканчиваем с A — здесь девять. Дальше мы возвращаемся, вот в этот момент мы вернулись обратно в нашу функцию "dfs", и мы проверяем, есть ли еще непосещенные вершины, такая вершина есть — это вершина F, и, собственно, мы ее посещаем, у нее предобработка 10, постобработка 11. Так что вот так это отработает. Давайте, на самом деле, вот здесь мы меняли немножко граф, давайте это сделаем. У нас добавилось ребро из E в F, давайте посмотрим, что изменится в нашем запуске. Нарисовался этот измененный граф, вот время предобработки и постобработки. Изменилось вот что, во-первых, мы обойдем весь граф за один раз, запустив из вершины A мы пройдем по всем вершинам и закончим в той же вершине A, время постобработки у A будет максимальное, будет 11. Как это все происходит? В начале так же, мы из A идем в B, потом в C, возвращаемся в B, идем в D, идем в E и дальше идем в F, появилось ребро из E в F, и F еще непосещенное, и из вершины E мы переходим в вершину F, у нее будет время предобработки на единицу больше, чем предобработка у E, дальше мы с F заканчиваем, тут уже у нее будет семь постобработка, дальше возвращаемся в E, а дальше просто, как и раньше, возвращаемся в вершину A.
