Обход в глубину, цвета вершин — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Время работы)
(Реализация)
(не показано 29 промежуточных версий 7 участников)
Строка 1: Строка 1:
'''Обход в глубину''' (поиск в глубину, англ. Depth-First Search, DFS) - один из основных методов обхода графа, часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].
+
'''Обход в глубину''' (поиск в глубину, англ. ''Depth-First Search'', ''DFS'') один из основных методов обхода [[Основные определения теории графов|графа]], часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].
  
 
== Алгоритм ==
 
== Алгоритм ==
  
 
=== Общая идея ===
 
=== Общая идея ===
Общая идея алгоритма состоит в следующем:  для каждой ''не пройденной'' вершины необходимо найти все ''не пройденные'' смежные вершины и повторить поиск для них.
+
Общая идея алгоритма состоит в следующем:  для каждой ''не пройденной'' [[Основные определения теории графов|вершины]] необходимо найти все ''не пройденные'' [[Основные определения теории графов|смежные вершины]] и повторить поиск для них.
  
 
=== Пошаговое представление ===
 
=== Пошаговое представление ===
#Выбираем  любую вершину из еще ''не пройденных'', обозначим ее как u.
+
#Выбираем  любую вершину из еще ''не пройденных'', обозначим ее как <tex>u</tex>.
#Запускаем процедуру DFS(u)
+
#Запускаем процедуру <tex>\mathrm{dfs(u)}</tex>
#*Помечаем вершину u как ''пройденную''
+
#*Помечаем вершину <tex>u</tex> как ''пройденную''
#*Для каждой ''не пройденной'' смежной с u вершиной (назовем ее v) запускаем DFS(v)
+
#*Для каждой ''не пройденной'' смежной с <tex>u</tex> вершиной (назовем ее <tex>v</tex>) запускаем <tex>\mathrm{dfs(v)}</tex>
#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.
+
#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.
  
 
=== Реализация ===
 
=== Реализация ===
vector<bool> visited;                      //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
+
В массиве <tex>\mathrm{visited[]}</tex> хранится информация о ''пройденных'' и ''не пройденных'' вершинах.
 +
 
 +
'''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
 +
    visited = array[n, ''false''] <font color=darkgreen> // создаём массив посещённых вершины длины n, заполненный ''false'' изначально</font>
 +
         
 +
    '''function''' dfs(u: '''int'''): 
 +
      visited[u] = ''true''
 +
      '''for''' v: (u, v) '''in''' G       
 +
          '''if''' '''not''' visited[v]             
 +
            dfs(v)
 
   
 
   
void dfs(int u)             
+
    '''for''' i = 1 '''to''' n             
{
+
      '''if''' '''not''' visited[i]                     
    visited[u] = true;                      //помечаем вершину как пройденную
+
          dfs(i)
    for (v таких, что (u, v) - ребро в G)  //проходим по смежным с u вершинам
 
        if (!visited[v])                    //проверяем, не находились ли мы ранее в выбранной вершине
 
            dfs(v);
 
}
 
 
int main()
 
{
 
    ...                                    //задание графа G с количеством вершин n.
 
    visited.assign(n, false);              //в начале все вершины в графе ''не пройденные''
 
    for (int i = 0; i < n; ++i)             //проходим по всем вершинам графа...
 
        if (!visited[i])                   //...не забыв проверить, были мы уже в очередной вершине или нет
 
            dfs(i);
 
    return 0;
 
}
 
  
 
=== Время работы ===
 
=== Время работы ===
Оценим время работы обхода в глубину. Процедура <tex>dfs</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все ребра <tex>{e\ |\ begin(e) = u}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.
+
Оценим время работы обхода в глубину. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(e)} = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.
  
 
== Цвета вершин ==
 
== Цвета вершин ==
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.<br />
+
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.
Поэтому в процессе алгоритма вершинам задают некоторые цвета:<br />
+
 
:если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';<br />
+
Поэтому в процессе алгоритма вершинам задают некоторые цвета:
:''серая'' - вершина ''проходится'' в текущей процедуре DFS;<br />
+
 
:''черная'' - вершина ''пройдена'', все итерации DFS от нее завершены.<br />
+
*если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';
 +
*''серая'' вершина ''проходится'' в текущей процедуре <tex>\mathrm{dfs}</tex>;
 +
*''черная'' вершина ''пройдена'', все итерации <tex>\mathrm{dfs}</tex> от нее завершены.
  
 
Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].
 
Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].
  
 
=== Реализация ===
 
=== Реализация ===
Отличие реализации с цветами от предыдущей лишь в массиве visited, который мы назовем теперь color, и дополнительной ''черной'' "метки". При этом цвета вершин будут заданы следующим образом: ''белый'' - 0, ''серый'' - 1, ''черный'' - 2.
+
Отличие реализации с цветами от предыдущей лишь в массиве <tex>\mathrm{visited[]}</tex>, который мы назовем теперь <tex>\mathrm{color[]}</tex>. В нем будет хранится информация о цветах вершин.
 +
 
 +
'''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
 +
    color = 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)
 +
 
 +
=== Пример ===
 +
Рассмотрим, как будут изменяться цвета вершин при обходе в глубину данного графа.
 +
 
 +
{| style="background-color:#CCC;margin:0.5px;width:600px"
 +
!style="background-color:#EEE"| Описание шага
 +
!style="background-color:#EEE"| Состояние графа
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| В функции <tex>\mathrm{doDfs}</tex> присваиваем всем вершинам в массиве <tex>\mathrm{color[]}</tex> белый цвет. Затем проверяем, что первая вершина окрашена в белый цвет. Заходим в нее и раскрашиваем ее в серый цвет.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs1.png‎|150px|]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 2. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs2.png‎|150px|]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 3. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs3.png‎|150px|]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Проверяем, что из вершины с номером 3 не исходит ни одного ребра. Помечаем ее в черный цвет и возвращаемся в вершину с номером 2.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs4.png‎|150px|]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 4. Проверяем, что она белая, и переходим в нее. Окрашиваем ее в серый цвет.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs5_6_7.png‎|150px|]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 3. Видим, что она черного цвета, и остаемся на месте.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs5_6_7.png‎|150px|]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Пробуем пойти в вершину с номером 1. Видим, что она серого цвета, и остаемся на месте.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs5_6_7.png‎|150px|]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Из вершины с номером 4 больше нет исходящих ребер. Помечаем ее в черный цвет и возвращаемся в вершину с номером 2.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs8.png‎|150px|]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Из вершины с номером 2 больше нет исходящих ребер. Помечаем ее в черный цвет и возвращаемся в вершину с номером 1.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs9.png‎|150px|]]
 +
|-
 +
|style="background-color:#FFF;padding:2px 10px"| Из вершины с номером 1 больше нет исходящих ребер. Помечаем ее в черный цвет и выходим в программу <tex>\mathrm{doDfs}</tex>. В ней проверяем, что все вершины окрашены в черный цвет. Выходим из функции <tex>\mathrm{doDfs}</tex>. Алгоритм завершен.
 +
|style="background-color:#FFF;padding:2px 10px"| [[Файл:dfs10.png‎|150px|]]
 +
|}
 +
 
 +
== Дерево обхода в глубину ==
 +
[[Image: Colors.png|thumb|240px|Типы ребер, определяемые деревом обхода:<br>
 +
1) ребра дерева<br>
 +
2) <font color=#3771c8>обратные</font> ребра<br>
 +
3) <font color=#71c837>прямые</font> ребра<br>
 +
4) <font color=#ff2a2a>перекрестные</font> ребра]]
 +
 
 +
Рассмотрим подграф предшествования обхода в глубину <tex>G_p = (V, E_p)</tex>, где <tex>E_p = \{(p[u], u) : u \in V,\ p[u] \neq NIL\}</tex>, где в свою очередь <tex>p[u]</tex> — вершина, от которой был вызван <tex>\mathrm{dfs(u)}\ </tex> (для вершин, от которых <tex>\mathrm{dfs}</tex> был вызван нерекурсивно это значение соответственно равно <tex>NIL</tex>). Подграф предшествования поиска в глубину образует ''лес обхода в глубину'', который состоит из нескольких ''деревьев обхода в глубину''. С помощью полученного леса можно классифицировать ребра графа <tex>G</tex>:
 +
* ''Ребрами дерева'' назовем те ребра из <tex>G</tex>, которые вошли в <tex>G_p</tex>.
 +
* Ребра <tex>(u, v)</tex>, соединяющие вершину <tex>u</tex> с её предком <tex>v</tex> в дереве обхода в глубину назовем ''обратными ребрами'' (для неориентированного графа предок должен быть ''не родителем'', так как иначе ребро будет являться ребром дерева).
 +
* Ребра <tex>(u, v)</tex>, не являющиеся ребрами дерева и соединяющие вершину <tex>u</tex> с её потомком <tex>v</tex> в дереве обхода в глубину назовем ''прямыми ребрами'' (в неориентированном графе нет разницы между прямыми и обратными ребрами, поэтому все такие ребра считаются обратными).
 +
* Все остальные ребра назовем ''перекрестными ребрами'' — такие ребра могут соединять вершины одного и того же дерева обхода в глубину, когда ни одна из вершин не является предком другой, или соединять вершины в разных деревьях.
 +
Алгоритм <tex>\mathrm{dfs}</tex> можно модифицировать так, что он будет классифицировать встречающиеся при работе ребра. Ключевая идея состоит в том, что каждое ребро <tex>(u, v)</tex> можно классифицировать при помощи цвета вершины <tex>v</tex> при первом его исследовании, а именно:
 +
* Белый цвет вершины <tex>v</tex> по определению <tex>\mathrm{dfs}</tex> говорит о том, что это ''ребро дерева''.
 +
* Серый цвет в силу того, что серые вершины всегда образуют нисходящий путь в каком-либо из деревьев <tex>\mathrm{dfs}</tex> и встреченная вершина <tex>v</tex> лежит на нем выше вершины <tex>u</tex>, определяет ''обратное ребро'' (для неориентированного графа необходимо проверить условие <tex>v \neq p[u]</tex>).
 +
* Черный цвет, соответственно, указывает на ''прямое'' или ''перекрестное ребро''.
  
vector<int> color;                          //вектор для хранения информации о цвете вершин
+
== См. также ==
+
* [[Обход в ширину]]
void dfs(int u)             
 
{
 
    color[u] = 1;                          //раскрашиваем вершину в ''серый'' цвет
 
    for (v таких, что (u, v) - ребро в G)  //проходим по смежным с u вершинам
 
        if (!color[v])                      //проверяем, не находились ли мы ранее в выбранной вершине, условие не требует изменений,
 
            dfs(v);                        //поскольку мы считаем вершину "не пройденной" только тогда, когда она ''белого'' цвета, т.е. когда color[v] = 0
 
    color[u] = 2;                          //раскрашиваем вершину в ''черный'' цвет
 
}
 
 
int main()
 
{
 
    ...                                    //задание графа G с количеством вершин n.
 
    color.assign(n, 0);                    //в начале все вершины в графе ''не пройденные'', т.е. ''белые''.
 
    for (int i = 0; i < n; ++i)            //проходим по всем вершинам графа...
 
        if (!color[i])                    //...не забыв проверить, были мы уже в очередной вершине или нет
 
            dfs(i);
 
    return 0;
 
}
 
  
== Источники ==
+
== Источники информации ==
*[http://ru.wikipedia.org/wiki/Поиск_в_глубину Обход в глубину на ru.wikipedia.org]
+
*[http://ru.wikipedia.org/wiki/Поиск_в_глубину Википедия {{---}} Поиск в глубину]
 +
*[http://en.wikipedia.org/wiki/Depth-first_search Wikipedia {{---}} Depth-first search]
 
*[http://www.e-maxx.ru/algo/dfs Обход в глубину. Реализации.]
 
*[http://www.e-maxx.ru/algo/dfs Обход в глубину. Реализации.]
 +
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, второе издание. Пер. с англ. — Издательский дом "Вильямс", 2007. — 1296 с. — Глава 22. Элементарные алгоритмы для работы с графами.
 +
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обход в глубину]]
 
[[Категория: Обход в глубину]]

Версия 21:45, 19 июня 2018

Обход в глубину (поиск в глубину, англ. 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[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)

Время работы

Оценим время работы обхода в глубину. Процедура [math]\mathrm{dfs}[/math] вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие ребра [math]\{e\ |\ \mathrm{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[n]: Graph): // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе 
   color = 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)

Пример

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

Описание шага Состояние графа
В функции [math]\mathrm{doDfs}[/math] присваиваем всем вершинам в массиве [math]\mathrm{color[]}[/math] белый цвет. Затем проверяем, что первая вершина окрашена в белый цвет. Заходим в нее и раскрашиваем ее в серый цвет. 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 больше нет исходящих ребер. Помечаем ее в черный цвет и выходим в программу [math]\mathrm{doDfs}[/math]. В ней проверяем, что все вершины окрашены в черный цвет. Выходим из функции [math]\mathrm{doDfs}[/math]. Алгоритм завершен. Dfs10.png

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

Типы ребер, определяемые деревом обхода:
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]).
  • Черный цвет, соответственно, указывает на прямое или перекрестное ребро.

См. также

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