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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Содержание

[править] Алгоритм

[править] Общая идея

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

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

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

[править] Реализация

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

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

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

[править] Время работы

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

[править] Цвета вершин

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

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

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

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

[править] Реализация

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

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

[править] Пример

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

Описание шага Состояние графа
В функции \mathrm{doDfs} присваиваем всем вершинам в массиве \mathrm{color[]} белый цвет. Затем проверяем, что первая вершина окрашена в белый цвет. Заходим в нее и раскрашиваем ее в серый цвет. Dfs1.png
Пробуем пойти в вершину с номером 2. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет. Dfs2.png
Пробуем пойти в вершину с номером 3. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет. Dfs3.png
Проверяем, что из вершины с номером 3 не исходит ни одного ребра. Помечаем ее в черный цвет и возвращаемся в вершину с номером 2. Dfs4.png
Пробуем пойти в вершину с номером 4. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет. Dfs5 6 7.png
Пробуем пойти в вершину с номером 3. Видим, что она черного цвета, и остаемся на месте. Dfs5 6 7.png
Пробуем пойти в вершину с номером 1. Видим, что она серого цвета, и остаемся на месте. Dfs5 6 7.png
Из вершины с номером 4 больше нет исходящих ребер. Помечаем ее в черный цвет и возвращаемся в вершину с номером 2. Dfs8.png
Из вершины с номером 2 больше нет исходящих ребер. Помечаем ее в черный цвет и возвращаемся в вершину с номером 1. Dfs9.png
Из вершины с номером 1 больше нет исходящих ребер. Помечаем ее в черный цвет и выходим в программу \mathrm{doDfs}. В ней проверяем, что все вершины окрашены в черный цвет. Выходим из функции \mathrm{doDfs}. Алгоритм завершен. Dfs10.png

[править] Дерево обхода в глубину

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

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

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

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

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

[править] См. также

[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты