Обход в глубину, цвета вершин

Обход в глубину (поиск в глубину, англ. Depth-First Search, DFS) — один из основных методов обхода графа, часто используемый для проверки связности, поиска цикла и компонент сильной связности и для топологической сортировки.

Алгоритм

Общая идея

Общая идея алгоритма состоит в следующем: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Пошаговое представление

1. Выбираем любую вершину из еще не пройденных, обозначим ее как [math]u[/math].
2. Запускаем процедуру [math]\mathrm{dfs(u)}[/math]
   • Помечаем вершину [math]u[/math] как пройденную
   • Для каждой не пройденной смежной с [math]u[/math] вершиной (назовем ее [math]v[/math]) запускаем [math]\mathrm{dfs(v)}[/math]
3. Повторяем шаги 1 и 2, пока все вершины не окажутся пройденными.

Реализация

В массиве [math]\mathrm{visited[]}[/math] хранится информация о пройденных и не пройденных вершинах.

function doDfs(G: Graph):// функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе 
   function dfs(u: int):   
      visited[u] = true
      for v: (u, v) in G        
         if not visited[v]               
            dfs(v)

   fill(visited, false)             
   for i = 1 to n             
      if not visited[i]                    
         dfs(i)    

Время работы

Оценим время работы обхода в глубину. Процедура [math]\mathrm{dfs}[/math] вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие ребра [math]\{e\ |\ begin(e) = u\}[/math]. Всего таких ребер для всех вершин в графе [math]O(E)[/math], следовательно, время работы алгоритма оценивается как [math]O(V+E)[/math].

Цвета вершин

Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.

Поэтому в процессе алгоритма вершинам задают некоторые цвета:

• если вершина белая, значит, мы в ней еще не были, вершина не пройдена;
• серая — вершина проходится в текущей процедуре [math]\mathrm{dfs}[/math];
• черная — вершина пройдена, все итерации [math]\mathrm{dfs}[/math] от нее завершены.

Такие "метки" в основном используются при поиске цикла.

Реализация

Отличие реализации с цветами от предыдущей лишь в массиве [math]\mathrm{visited[]}[/math], который мы назовем теперь [math]\mathrm{color[]}[/math]. В нем будет хранится информация о цветах вершин.

function doDfs(G: Graph):// функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе 
   function dfs(u: int):
      color[u] = gray           
      for v: (u, v) in G                   
         if color[v] == white
            dfs(v)
      color[u] = black   
                   	   
   fill(color, white)             
   for i = 1 to n             
      if color[i] == white                
         dfs(i)

Пример

Рассмотрим, как будут изменяться цвета вершин при обходе в глубину данного графа.

Описание шага	Состояние графа
В функции [math]\mathrm{doDfs}[/math] присваиваем всем вершинам в массиве [math]\mathrm{color[]}[/math] белый цвет. Затем проверяем, что первая вершина окрашена в белый цвет. Заходим в нее и раскрашиваем ее в серый цвет.
Пробуем пойти в вершину с номером 2. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет.
Пробуем пойти в вершину с номером 3. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет.
Проверяем, что из вершины с номером 3 не исходит ни одного ребра. Помечаем ее в черный цвет и возвращаемся в вершину с номером 2.
Пробуем пойти в вершину с номером 4. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет.
Пробуем пойти в вершину с номером 3. Видим, что она черного цвета, и остаемся на месте.
Пробуем пойти в вершину с номером 1. Видим, что она серого цвета, и остаемся на месте.
Из вершины с номером 4 больше нет исходящих ребер. Помечаем ее в черный цвет и возвращаемся в вершину с номером 2.
Из вершины с номером 2 больше нет исходящих ребер. Помечаем ее в черный цвет и возвращаемся в вершину с номером 1.
Из вершины с номером 1 больше нет исходящих ребер. Помечаем ее в черный цвет и выходим в программу [math]\mathrm{doDfs}[/math]. В ней проверяем, что все вершины окрашены в черный цвет. Выходим из функции [math]\mathrm{doDfs}[/math]. Алгоритм завершен.

Дерево обхода в глубину

Типы ребер, определяемые деревом обхода:
1) ребра дерева
2) обратные ребра
3) прямые ребра
4) перекрестные ребра

Рассмотрим подграф предшествования обхода в глубину [math]G_p = (V, E_p)[/math], где [math]E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}[/math], где в свою очередь [math]p[u][/math] — вершина, от которой был вызван [math]\mathrm{dfs(u)}\ [/math] (для вершин, от которых [math]\mathrm{dfs}[/math] был вызван нерекурсивно это значение соответственно равно [math]NIL[/math]). Подграф предшествования поиска в глубину образует лес обхода в глубину, который состоит из нескольких деревьев обхода в глубину. С помощью полученного леса можно классифицировать ребра графа [math]G[/math]:

• Ребрами дерева назовем те ребра из [math]G[/math], которые вошли в [math]G_p[/math].
• Ребра [math](u, v)[/math], соединяющие вершину [math]u[/math] с её предком [math]v[/math] в дереве обхода в глубину назовем обратными ребрами (для неориентированного графа предок должен быть не родителем, так как иначе ребро будет являться ребром дерева).
• Ребра [math](u, v)[/math], не являющиеся ребрами дерева и соединяющие вершину [math]u[/math] с её потомком [math]v[/math] в дереве обхода в глубину назовем прямыми ребрами (в неориентированном графе нет разницы между прямыми и обратными ребрами, поэтому все такие ребра считаются обратными).
• Все остальные ребра назовем перекрестными ребрами — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.

Алгоритм [math]\mathrm{dfs}[/math] можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро [math](u, v)[/math] можно классифицировать при помощи цвета вершины [math]v[/math] при первом его исследовании, а именно:

• Белый цвет вершины [math]v[/math] по определению [math]\mathrm{dfs}[/math] говорит о том, что это ребро дерева.
• Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев [math]\mathrm{dfs}[/math] и встреченная вершина [math]v[/math] лежит на нем выше вершины [math]u[/math], определяет обратное ребро (для неориентированного графа необходимо проверить условие [math]v \neq p[u][/math]).
• Черный цвет, соответственно, указывает на прямое или перекрестное ребро.

См. также

• Обход в ширину

Источники информации

• Википедия — Поиск в глубину
• Wikipedia — Depth-first search
• Обход в глубину. Реализации.
• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, второе издание. Пер. с англ. — Издательский дом "Вильямс", 2007. — 1296 с. — Глава 22. Элементарные алгоритмы для работы с графами.