Поиск в глубину на графе (RU)

  Представьте себе, что Вы находитесь у входа в лабиринт. Вам известно, что где-то находится выход, и его надо найти. Лабиринт представляет собой набор тоннелей, расположенных глубоко под землей. У Вас, увы, нет ни фонарика, ни факела, зато есть смекалка и отсутствие страха перед темнотой.  

   Описанных условий достаточно чтобы найти выход. Для этого достаточно воспользоваться правилом "правой руки": на входе в лабиринт следует взяться правой рукой за стену и постоянно двигаться таким образом, чтобы правая рука непрерывно скользила по стене. Действуя подобным образом, Вы обязательно найдете выход (если конечно к нему существует путь из точки входа; в противном случае Вы снова попадете на вход).

   Попробуем усложнить задачу. Пусть лабиринт представляет собой набор подземных комнат и тоннелей, их связывающих. Вход в лабиринт только один (он же является и выходом), а в каждой комнате находится слиток золота. Ваша задача состоит в том, чтобы собрать все (непременно все!) слитки и вернуться к тому же месту, из которого Вы вошли в лабиринт.

   Если не вводить дополнительных условий или Ваших умений (способностей), то задача в такой постановке не разрешима. Во всяком случае, детерминированного алгоритма, который бы на 100% гарантировал успех сбора всех золотых слитков, не существует.

   Предположим, что в последней версии задачи в каждой комнате есть одна лампочка, которую можно включить, только попав в эту же комнату. Золотоискатель (то есть Вы) уже вооружены факелом, а также мелом, которым можете делать любые пометки на стенах лабиринта. Попав в темную комнату, Вы без труда способны найти выключатель, при помощи которого можно зажечь в ней лампу. Будем считать, что любые две соседние комнаты соединяются прямым недлинным тоннелем. То есть находясь с одной стороны тоннеля и заглянув в него, можно однозначно определить, горит ли свет с другой стороны (любой тоннель всегда соединяет две комнаты).

   В такой постановке решение задачи существует. Его можно описать двумя правилами:

1. Если в текущей комнате существует тоннель, ведущий в еще не пройденную комнату (где еще не горит свет), то идем туда. При этом попадая в темную комнату, мы непременно включаем свет и отмечаем мелом тоннель, по которому сюда попали.
2. Если из текущей комнаты нельзя попасть в еще неизведанную комнату (условия пункта 1 не выполняются), то возвращаемся по тому тоннелю, по которому мы впервые попали сюда (этот тоннель отмечен у нас мелом).

   Описанный метод обхода лабиринта носит название "поиск в глубину".

   Поиском в глубину (DFS – depth first search) называется один из методов обхода графа G = (V, E), суть которого состоит в том, чтобы идти “вглубь” пока это возможно. В процессе поиска в глубину вершинам графа присваиваются номера, а ребра помечаются. Обход вершин графа происходит согласно принципу: если из текущей вершины есть ребра, ведущие в непройденные вершины, то идем туда, иначе возвращаемся назад.

   Поиск в глубину начинается с выбора начальной вершины v графа G, которая сразу же помечается как пройденная. Потом для каждой непомеченной вершины, смежной с v, рекурсивно вызывается поиск в глубину. Когда все вершины, достижимые из v, будут помечены, поиск заканчивается. Если на некотором (не начальном) шаге обхода поиск закончился, но некоторые вершины остаются непомеченными (такой случай возможен в случае ориентированного или несвязного графа), то выбирается произвольная из них и поиск повторяется. Процесс поиска продолжается до тех пор, пока все вершины графа G не будут помечены.

   Пример 1. Вывести последовательность вершин графа при поиске в глубину.

Вход. Первая строка содержит количество вершин n в неориентированном связном графе. Каждая из следующих строк содержит пару вершин, соединенных ребром графа. Вершины графа нумеруются с 1 до n.

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

   Пусть m – матрица смежности графа (m[i][j] = 1, если существует ребро между вершинами i и j, и m[i][j] = 0 иначе), used – булевый массив, в котором used[i] = 1, если вершина i помечена (пройдена) и used[i] = 0 иначе.

#include< stdio.h >

#include< memory.h >

#define MAX 100

int m[MAX][MAX], used[MAX];

int i, n, a, b, ptr;

void dfs(int v)

{

  int i;

  // включаем в комнате (вершине v графа) лампочку

  used[v] = 1;

  printf("Vertex %d is visited\n",v);

  // ищем тоннель, через который можно попасть в еще непройденную комнату

  for (i = 1; i <= n; i++)

    if (m[v][i] && !used[i]) dfs(i);

}

void main(void)

{

  memset(m, 0, sizeof(m)); memset(used, 0, sizeof(used));

  // читаем входные данные

  scanf("%d", &n);

  while (scanf("%d %d", &a, &b) == 2)

    m[a][b] = m[b][a] = 1;

  // запускаем поиск в глубину с вершины 1

  dfs(1);

}

   При поиске в глубину можно использовать цвет вершины. Изначально цвета всех вершин белые. Когда вершина проходится первый раз, она становится серой. Вершина является обработанной, если полностью просмотрены все ее смежные вершины. Когда вершина  обработана, она становится черной.

   Каждой вершине можно приписать две метки времени:

   d[v] – время, когда вершина обнаружена и стала серой;

   f[v] – время, когда вершина обработана и стала черной.

   Эти метки используются во многих алгоритмах на графах и являются полезными для анализа свойств поиска в глубину.

   Метки времени d[v] и f[v] являются целыми числами от 1 до 2|V|. Для каждой вершины v имеет место неравенство: d[v] < f[v]. Вершина v будет белой до момента времени d[v], серой с d[v] до f[v] и черной после f[v].

   Поиск в глубину на связном неориентированном графе можно описать следующим образом:

   DFS(u)

1. Отмечаем вершину u пройденной и окрашиваем ее в серый цвет;
2. Для каждой вершины v, смежной с u, и окрашенной в белый цвет, вызываем dfs(v);
3. Окрашиваем вершину u в черный цвет;

   Пример 2. Расстановка меток вершин графа при поиске в глубину.

   Вход. Первая строка содержит количество вершин n в связном графе. Каждая из следующих строк содержит пару вершин, соединенных ребром графа. Вершины графа нумеруются с 1 до n.

   Выход. В i - ой строке вывести информацию об i - ой вершине в формате, приведенном в примере. Вместе с номером вершины i следует вывести значения d[i] и f[i].

   Цвет вершины храним в ячейках массива used: 0 – вершина белая, 1 – серая, 2 – черная.

#include< stdio.h >

#include< memory.h >

#define MAX 100

int m[MAX][MAX], d[MAX], f[MAX], used[MAX];

int i, n, a, b, time;

void dfs(int v)

{

  int i;

  used[v] = 1;

  d[v] = time++;

  for (i = 1; i <= n; i++)

    if (m[v][i] && !used[i]) dfs(i);

  used[v] = 2;

  f[v] = time++;

}

void main(void)

{

  memset(m, 0, sizeof(m)); memset(used, 0, sizeof(used));

  scanf("%d", &n);

  while (scanf("%d %d", &a, &b) == 2)

    m[a][b] = m[b][a] = 1;

  time = 1; dfs(1);

  for (i = 1; i <= n; i++)

    printf("Vertex: %d, Gray: %d, Black %d\n", i, d[i], f[i]);

}

   Реализуем процедуру поиска в глубину на случай несвязного или ориентированного графа. В этом случае вызов dfs(1) следует заменить на следующий код:

  for (i = 1; i <= n; i++)

     if (!used[i]) dfs(i);

   Пример 3. Рассмотрим ориентированный граф, изображенный на рисунке 1. На рисунке 2 показан обход графа в глубину с расстановкой меток, начиная с вершины 4. Около каждой вершины v запишем ее номер в последовательности обхода в глубину, а в фигурных скобках – метки времени d[v] и f[v].

Рисунок 1. Ориентированный граф                                  Рисунок 2. Поиск в глубину

   В результате обхода графа в глубину получаем подграф предшествования, который представляет собой лес поиска в глубину (состоит из деревьев поиска в глубину). На рисунке 3 представлен соответствующий граф предшествования.

Рисунок 3. Подграф предшествования

   КЛАССИФИКАЦИЯ РЕБЕР

   Поиск в глубину используется для классификации ребер графа. Имеются 4 типа ребер:

1. Дугами дерева являются ребра, ведущие к вершинам, которые раньше не посещались. Они формируют для заданного графа глубинныйостовный лес.
2. Обратныминазываются дуги, идущие в остовном лесу от потомков к предкам. Дуга, идущая из вершины в саму себя, считается обратной.
3. Прямыми называются дуги, идущие от предков к собственным потомкам, но которые не являются дугами дерева.
4. Поперечными дугами являются ребра, соединяющие вершины, не являющиеся ни предками, ни потомками.

Рисунок 4. Глубинный остовный лес

   На рисунке 4 изображены:

• дуги дерева – красным цветом;
• обратные дуги – зеленым цветом;
• прямые дуги – розовым цветом;
• поперечные дуги – коричневым цветом;

   СВОЙСТВА ПОИСКА В ГЛУБИНУ

   Время начала и окончания обработки вершины при поиске в глубину образуют правильную скобочную структуру, если появление вершины u обозначать через “(u”, а окончание обработки вершины u обозначать через “u)”. Поиск в глубину на графе, изображенном на рисунке 2, образует следующую скобочную структуру:

(4 (1 (2 (3 (6 6) 3) 2) (5 5) 1) 4)

   Теорема о скобочной структуре. При поиске в глубину для произвольных двух вершин u и v выполняется одно и только одно из следующих свойств:

1. Отрезки (d[u], f[u]) и (d[v], f[v]) не пересекаются;
2. Отрезок (d[u], f[u]) полностью содержится в отрезке (d[v], f[v]). При этом u является потомком v при поиске в глубину.
3. Отрезок (d[v], f[v]) полностью содержится в отрезке (d[u], f[u]). При этом v является потомком u при поиске в глубину.

   Следствие. Вложение интервалов для потомков.

   Вершина v является потомком вершины u при поиске в глубину тогда и только тогда, когда d[u] < d[v] < f[v] < f[u].

   Теорема про белый путь. Вершина v является потомком вершины u в лесу поиска в глубину тогда и только тогда, когда в момент d[u] обнаружения вершины u существует путь из u в v, состоящий только из белых вершин.

   Теорема про свойства ребер. Ребро (u, v) является

а) ребром дерева или прямым ребром тогда и только тогда, когда

d[u] < d[v] < f[v] < f[u]

б) обратным ребром тогда и только тогда, когда

d[v] < d[u] < f[u] < f[v]

в) поперечным ребром тогда и только тогда, когда

d[v] < f[v] < d[u] < f[u]

    Теорема. О классификации ребер в неориентированном графе. При поиске в глубину в неориентированном графе произвольное ребро является или ребром дерева, или обратным. Прямых и перекрестных ребер не существует.

   ЗАДАЧИ

   В качестве приложения поиска в глубину рассмотрим три эквивалентных между собой задачи на неориентированном связном графе:

   1. Можно ли покрасить вершины графа в два цвета так, чтобы любое его ребро соединяло вершины разных цветов.

   2. Проверить, является ли граф двудольным. Напомним, что граф G(V, E) является двудольным, если множество его вершин можно разбить на два подмножества  так, что любое ребро графа соединяет вершины из разных подмножеств.

   3. Проверить, существует ли в графе цикл нечетной длины. То есть цикл, состоящий из нечетного количества вершин.

   Эквивалентность задач 1 и 2. Пусть вершины графа можно покрасить двумя цветами. Тогда все вершины с одним цветом отнесем к одной доле, а вершины с другим цветом – к другой. Если ребро соединяет две вершины разного цвета, то это же ребро соединяет вершины из разных долей. Двудольный граф построен.

   Эквивалентность задач 2 и 3. Если граф двудольный, то любой его цикл содержит четное количество вершин. Если граф не двудольный, то он обязательно содержит цикл нечетной длины.

   Рассмотрим первую задачу более детально, приведя полностью ее условие, описание ввода-вывода и детальное решение на языке Си. Эта задача взята с WEB страницы http://uva.onlinejudge.org университета Вальядолид, посвященной олимпиадному программированию, ее номер 10004 в списке задач.

   Пример 4. Раскраска вершин графа двумя цветами [Вальядолид, 10004]. Имеется связный неориентированный граф. Определить, можно ли покрасить его вершины двумя цветами так, чтобы никакие две соседние вершины не были покрашены одним цветом.

   Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество вершин n (1 < n < 200) и количество ребер l в графе. Каждая из следующих l строк содержит два числа – номера вершин графа, соединенные ребром. Вершины графа нумеруются числами от 0 до n – 1. Последняя строка содержит n = l = 0 и не обрабатывается.

   Выход.Для каждого теста вывести строку “BICOLORABLE.”, если вершины графа можно раскрасить требуемым образом, и “NOT BICOLORABLE.” иначе.

   Решение. Для решения задачи воспользуемся поиском в глубину. Изначально вершины не просмотрены, пометим их все цветом 0. По мере прохождения по вершинам будем красить их в два цвета: 1 и 2. Если текущая вершина имеет цвет i (i = 1, 2), то следующую вершину, в которую мы попадаем при поиске в глубину, красим в цвет 3 – i. При этом проверяем, чтобы две соседние вершины не были покрашены в одинаковый цвет.

   Реализация. Матрицу смежности графа храним в массиве g размера MAX = 200. Массив mark содержит информацию о цвете вершины. Глобальная переменная Error отвечает за правильность раскраски: как только найдутся две соседние вершины, покрашенные одинаково, переменная примет значение 1.

#define MAX 200

int g[MAX][MAX], mark[MAX], Error;

   Процедура dfs выполняет поиск в глубину. Ей передаются два параметра: текущая вершина v и ее цвет color. Если уже встретился случай невозможности требуемой раскраски (Error = 1), то выйти из процедуры. Помечаем вершину v цветом color. Ищем непросмотренную вершину i, в которую можно пойти продолжив поиск в глубину. При этом если соседняя вершина i уже была просмотрена, проверяем условие окрашенности вершин v и i в разные цвета. Если указанные вершины покрашены в одинаковый цвет, устанавливаем Error = 1.

void dfs(int v, int color)

{

  int i;

  if (Error) return;

  mark[v] = color;

  for (i = 0; i < n; i++)

    if (g[v][i])

      if (!mark[i]) dfs(i,3-color); else

      if (mark[v] == mark[i]) Error = 1;

}

   Основной цикл программы. Читаем число вершин графа n и количество ребер l. Обнуляем матрицу смежности и массив mark.

while (scanf("%d %d", &n, &l), n)

{

   memset(g, 0, sizeof(g));

   memset(mark, 0, sizeof(mark));

   Читаем данные графа.

   for (i = 0; i < l; i++)

   {

     scanf("%d %d", &a, &b);

     g[a][b] = g[b][a] = 1;

   }

   Обнуляем значение переменной Error, запускаем процедуру поиска в глубину с нулевой вершины, которую красим цветом 1.

   Error = 0; dfs(0,1);

   В зависимости от значения переменной Error выводим результат.

   if (Error) printf("NOT BICOLORABLE.\n");

         else printf("BICOLORABLE.\n");

}

СПИСОК ЛИТЕРАТУРЫ

1. "Алгоритмы построение и анализ", Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., – Москва, Санкт-Петербург, Киев, 2005 – 1292 с. 

2. "Практика и теория программирования", Книга 2. Винокуров Н.А., Ворожцов А.В., – М: Физматкнига, 2008 - 288 с.