§9. Поиск в глубину

Основой для выделения связных компонент графа в методе A1 из §2 служит алгоритм обхода всех вершин неориентированного связного графа $G$, именуемый поиском в глубину (сокращённо ПГ). В учебниках по алгоритмам на графах описаны и другие полезные алгоритмы поиска — скажем, поиск в ширину или метод Дейкстры нахождения кратчайшего пути между двумя заданными вершинами графа.

Алгоритм

В процессе поиска в глубину вершинам графа $G$ присваиваются номера (ПГ-номера), а рёбра помечаются. В начале рёбра не помечены, вершины не имеют ПГ-номеров.

Начинаем с произвольной вершины $v$. Присваиваем ей ПГ-номер $\text{ПГ}(v) = 1$ и выбираем произвольное ребро $vw$. Ребро $vw$ помечается как «прямое», а вершина $w$ получает (из $v$) ПГ-номер $\text{ПГ}(w) = 2$. После этого переходим в вершину $w$.

Пусть в результате выполнения нескольких шагов этого процесса пришли в вершину $x$, при этом $k$ — последний присвоенный ПГ-номер. Далее действуем в зависимости от ситуации следующим образом.

1. Имеется непомеченное ребро $xy$.
   • Если у вершины $y$ уже есть ПГ-номер, то ребро $xy$ помечаем как «обратное» и продолжаем поиск непомеченного ребра, выходящего из вершины $x$.
   • Если же вершина $y$ не имеет ПГ-номера, то полагаем $\text{ПГ}(y) = k + 1$, ребро $xy$ помечаем как «прямое» и переходим в вершину $y$. Вершина $y$ считается получившей свой ПГ-номер из вершины $x$.
2. Все рёбра, выходящие из $x$, помечены. Тогда возвращаемся в вершину, из которой $x$ получила свой ПГ-номер.

Процесс закончится, когда все рёбра будут помечены и произойдёт возвращение в вершину $v$.

Для того чтобы в пункте 2 узнать, из какой вершины получила свой ПГ-номер вершина $x$, надо запоминать список $Q$. Каждая вершина включается в $Q$ в момент получения ПГ-номера и исключается, как только произойдёт возвращение из этой вершины. Включение и исключение вершин производятся всегда с конца списка. Программисты называют такой список стеком.

Пусть граф $G$ задан списками смежности, то есть для каждой вершины $x$ приведён $N_x$ — список всех вершин, соединённых с ней рёбрами.

Пример

Граф рис. 21 у Лагутина задан списками смежности:

Применим поиск в глубину из вершины $v = 1$:

1. из 1 по первому ребру списка идём в 3 (номер 2);
2. из 3 ребро в 1 уже помечено, идём в 5 (номер 3);
3. из 5 идём в 2 (номер 4), из 2 — в 4 (номер 5);
4. из 4 ребро 4–5 ведёт в вершину с номером — оно «обратное»; возвращаемся в 2;
5. из 2 ребро в 1 «обратное», возвращаемся в 5;
6. из 5 ребро в 1 «обратное», идём в 6 (номер 6);
7. возвращаемся до 1 — конец.

Итог: ПГ-номера $1(1)$, $2(4)$, $3(2)$, $4(5)$, $5(3)$, $6(6)$.

Отметим, что по построению «прямые» рёбра образуют незамкнутый путь (дерево), соединяющий все вершины связного графа $G$. Однако этот путь, вообще говоря, не является кратчайшим (см. A2 из §2): как замечает Лагутин, на рис. 21, если считать длины рёбер по расстояниям на рисунке, выгоднее соединить вершины 4 и 6, а не 5 и 6.

Можно показать, что трудоёмкость и объём памяти для поиска в глубину составляют $O(n + m)$, где $n$ — число вершин графа, $m$ — число рёбер. Каждое ребро помечается ровно один раз, каждая вершина один раз попадает в стек и один раз из него выходит.

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

Связные компоненты

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

• если просматриваемая вершина $i$ ($i = 1, \dots, n$) имеет ПГ-номер, то перейти к следующей;
• иначе положить $v = i$, $\text{ПГ}(v) = k + 1$, где $k$ — последний присвоенный ПГ-номер, и применить поиск в глубину;
• после его окончания, то есть выделения компоненты, содержащей $i$, продолжить просмотр списка вершин с $i + 1$.

Различать вершины разных компонент можно по их ПГ-номерам, если для каждой компоненты запомнить последний ПГ-номер. Именно так работает виджет метода A1 в §2.

Замечание 8. После удаления $k - 1$ самых длинных рёбер КНП (алгоритм A2 из §2) автоматическое разбиение на классы можно произвести путём выделения связных компонент оставшегося графа.

Нить Ариадны

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

Смысл по-пацански: нить Ариадны — это и есть стек $Q$ плюс пометки на рёбрах. Наткнулся на свою же нить — значит, тут уже был, разворачивайся.

Проверь себя