19
2. Поиск в графе
Многие алгоритмы на графах основ аны на систематическом перебо-
ре всех вершин графа, при котором каждая вершина просматривается
в точности один раз. В этой главе мы рассмотрим два стандартных и
широко используемых метода такого перебора: поиск в глубину и по-
иск в ширину. Оба метода изучаются применительно к обыкновенным
графам, поскольку на произвольные графы они могут быть распростра-
нены очевидным образом. В разд. 2.3 поиск в глубину применяется для
отыскания компонент сильной связности в орграфе.
2.1. Поиск в глубину
Идея этого метода состоит в следующем. Поиск в обыкновенном гра-
фе G начинается с некоторой начально й вершины v (с этого момента v
считается просмотренной). Пусть u – последняя просмотренная верши-
на (этой вершиной может быть и v). Тогда возможны два случая.
1) Среди вершин, смежных с u, существует еще непросмотренная
вершина w. Тогда w объявляется просмотренной, и поиск продолжается
из вершины w. Будем говорим, что вершина u является отцом вершины
w (u = father[w]). Ребро uw в этом случае будет называться древесным.
2) Все вершины, смежные с u, просмотрены. Тогда u объявляется
использованной вершиной. Обозначим через x ту вершину, из которой
мы попали в u, т. е. x = father[u]; поиск в глубину продолжается из
вершины x.
Что произойдет, когда все просмотренные вершины будут использо-
ваны? Если в графе G не осталось непросмотренных вершин, то поиск
заканчивается. Если же осталась непросмотренная вершина y, то поиск
продолжается из этой вершины.
Поиск в глубину просматривает вершины графа G в определенном
порядке. Для того, чтобы зафиксировать этот порядок, будет использо-
ваться массив num. При этом естественно считать, что num[v] = 1, если
v начальная вершина, и num[w] = num[u] + 1, если w просматривается
сразу после того, как просмот рена вершина u.
Пусть в обыкновенном графе G проведен поиск в глубину. Обозначим
через T множество всех древесных ребер. Все остальные ребра графа
будем называть обратными ребрами. Множество всех обратных ребер
будем обозначать через B.
Результат применения поиска в глубину к связному графу G (рис. 7 a)