|
|
| Строка 1: |
Строка 1: |
| − | '''Обход в глубину''' (поиск в глубину, англ. ''Depth-First Search'', ''DFS'') — один из основных методов обхода [[Основные определения теории графов|графа]], часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].
| |
| | | | |
| − | == Алгоритм ==
| |
| − |
| |
| − | === Общая идея ===
| |
| − | Общая идея алгоритма состоит в следующем: для каждой ''не пройденной'' [[Основные определения теории графов|вершины]] необходимо найти все ''не пройденные'' [[Основные определения теории графов|смежные вершины]] и повторить поиск для них.
| |
| − |
| |
| − | === Пошаговое представление ===
| |
| − | #Выбираем любую вершину из еще ''не пройденных'', обозначим ее как <tex>u</tex>.
| |
| − | #Запускаем процедуру <tex>\mathrm{dfs(u)}</tex>
| |
| − | #*Помечаем вершину <tex>u</tex> как ''пройденную''
| |
| − | #*Для каждой ''не пройденной'' смежной с <tex>u</tex> вершиной (назовем ее <tex>v</tex>) запускаем <tex>\mathrm{dfs(v)}</tex>
| |
| − | #Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.
| |
| − |
| |
| − | === Реализация ===
| |
| − | В массиве <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)
| |
| − |
| |
| − | '''for''' i = 1 '''to''' n
| |
| − | '''if''' '''not''' visited[i]
| |
| − | dfs(i)
| |
| − |
| |
| − | === Время работы ===
| |
| − | Оценим время работы обхода в глубину. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(e)} = u\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>.
| |
| − |
| |
| − | == Цвета вершин ==
| |
| − | Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей.
| |
| − |
| |
| − | Поэтому в процессе алгоритма вершинам задают некоторые цвета:
| |
| − |
| |
| − | *если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена'';
| |
| − | *''серая'' — вершина ''проходится'' в текущей процедуре <tex>\mathrm{dfs}</tex>;
| |
| − | *''черная'' — вершина ''пройдена'', все итерации <tex>\mathrm{dfs}</tex> от нее завершены.
| |
| − |
| |
| − | Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].
| |
| − |
| |
| − | === Реализация ===
| |
| − | Отличие реализации с цветами от предыдущей лишь в массиве <tex>\mathrm{visited[]}</tex>, который мы назовем теперь <tex>\mathrm{color[]}</tex>. В нем будет хранится информация о цветах вершин.
| |
| − |
| |
| − | '''function''' doDfs(G[n]: '''Graph'''):<font color=darkgreen> // функция принимает граф G с количеством вершин n и выполняет обход в глубину во всем графе </font>
| |
| − | 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)
| |
| − |
| |
| − | === Пример ===
| |
| − | Рассмотрим, как будут изменяться цвета вершин при обходе в глубину данного графа.
| |
| − |
| |
| − | {| 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>).
| |
| − | * Черный цвет, соответственно, указывает на ''прямое'' или ''перекрестное ребро''.
| |
| − |
| |
| − | == См. также ==
| |
| − | * [[Обход в ширину]]
| |
| − |
| |
| − | == Источники информации ==
| |
| − | *[http://ru.wikipedia.org/wiki/Поиск_в_глубину Википедия {{---}} Поиск в глубину]
| |
| − | *[http://en.wikipedia.org/wiki/Depth-first_search Wikipedia {{---}} Depth-first search]
| |
| − | *[http://www.e-maxx.ru/algo/dfs Обход в глубину. Реализации.]
| |
| − | * Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, второе издание. Пер. с англ. — Издательский дом "Вильямс", 2007. — 1296 с. — Глава 22. Элементарные алгоритмы для работы с графами.
| |
| − |
| |
| − |
| |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | [[Категория: Обход в глубину]]
| |
