Алгоритм поиска в глубину — это способ обхода графа, который заключается в движении вглубь графа по мере возможности.
Введение
Алгоритм обхода (или поиска) в глубину даёт возможность выстроить обход ориентированного или неориентированного графа таким образом, что будут посещены все вершины, которые доступны из исходной вершины. Поиск в глубину отличается от поиска в ширину тем, что (для случая неориентированного графа) в результате работы поискового алгоритма в глубину будет найден определённый маршрут движения, идя по которому возможно пройти поочерёдно все вершины графа, которые доступны из исходной вершины. Это является принципиальным отличием от поиска в ширину, при котором ведётся одновременная обработка большого числа вершин. При поиске же в глубину в любой текущий момент работы алгоритма ведётся обработка только по одной вершине. Однако при этом, при поиске в глубину нет возможности найти кратчайшие пути. Но если нет полных данных о графе, а алгоритм выполняет какое-то автоматизированное устройство, то поиск в глубину является практически оптимальным решением. При работе с ориентированным графом, поиск в глубину может построить дерево путей из исходной вершины во все вершины, к которым есть доступ
Поиск в глубину
Алгоритм действий при обходе в глубину возможно описать следующим образом. Предположим, что исследователь расположен в определённом графе (лабиринте) и ему нужно пройти весь лабиринт, при этом посетив все вершины графа, которые доступны из исходной вершины. Исследователь расположен в заданной вершине и может видеть рёбра, которые исходят из этой вершины. Предполагаемая очерёдность его действий будет следующая:
- Двигаться до какой-либо смежной вершины.
- Пройти поочерёдно ко всем вершинам, которые доступны из данной вершины.
- Выполнить возврат на исходную вершину.
- Выполнить повторно алгоритм для оставшихся вершин, которые являются смежными с исходной.
Очевидно, что такой алгоритм по сути рекурсивный, то есть, чтобы обойти весь граф, необходимо перейти на соседнюю вершину, а затем повторно выполнить для этой вершины данный алгоритм обхода. Правда при этом может появиться проблема зацикливания. Поскольку, если из точки (вершины) А возможно пройти в точку (вершину) В, то справедливо и обратное утверждение, и рекурсия может стать бесконечной. Чтобы решить проблему бесконечной рекурсии, достаточно использовать простейшую мысль, а именно исследователь не надо проходить на вершину, где он был ранее. То есть, которая уже фактически ему не интересна (предполагается, что интересны исследователю лишь те вершины, на которых он ещё не бывал). Таким образом, скорректированный алгоритм будет иметь вид:
- Посетить любую смежную вершину, где исследователь не был ранее.
- Выполнить из этой вершины алгоритм обхода в глубину.
- Выполнить возврат на исходную вершину.
- Выполнить повтор пунктов один – три для всех смежных вершин, где исследователь не был ранее.
Чтобы выполнить данный алгоритм необходимо отмечать, какие вершины уже посещал исследователь, а какие ещё нет. Это можно сделать при помощи списка visitеd, где visitеd[i] == Truе для вершин, где уже был исследователь и visited[i] == false для тех, где он ещё не был. Отметка ставится только при посещении данной вершины. Так как в качестве основной цели обхода в глубину может быть формирование дерева обхода в глубину, то необходимо так же сохранять предшественника для всех вершин. Алгоритм по обходу в глубину можно оформить как рекурсивную функцию dfs, где stаrt — номер вершины, из которой начинается обход.
Пример алгоритма на языке C++
const vector g)
{
visited[start] = true;
for (auto u : g[start])
if (!visited[u]) {
prev[u] = start;
dfs(u, visited, prev, g);
}
}
int main()
{
…
vector visited(n + 1);
vector prev(n + 1, -1);
dfs(start, visited, prev, g);
Пример алгоритма на языке PYTHON
prev = [None] * (n + 1)
def dfs(start, visited, prev, g):
visited[start] = True
for u in g[start]:
if not visited[u]:
prev[u] = start
dfs(u)
dfs(start, visited, prev, g)
Здесь символом n обозначено число вершин в графе, вершины пронумерованы числами от 1 до n, а v[u] сохраняет множество вершин, которые являются смежными с u. Для того, чтобы запустить алгоритм, например, для вершины, пронумерованной как start, требуется вызов dfs. После чего все вершины, которые доступны из start, будут отмечаться в списках visited, а используя список prev возможно выстроить пути из вершины start ко всем доступным вершинам. Если нет необходимости выстраивать дерево обхода в глубину, то возможно не выполнять формирование списка stаrt, что сильно упрощает алгоритм dfs.
Выделение компонент связности
Алгоритм обхода в глубину даёт возможность для решения самых разнообразных задач. К примеру, можно реализовать, используя алгоритм обхода в глубину, вычисление количества компонент связности в неориентированном графе. Чтобы это сделать, нужно при обходе всех вершин графа, проверять, посещалась ли текущая вершина ранее. Если не посещалась, то это означает, что обнаружена новая компонента связности. Чтобы выделить всю компоненту связности требуется запуск DFS от данной вершины.
Пример алгоритма на языке C++
{
visited[start] = true;
for (auto u : g[start])
if (!visited[u])
dfs(u, visited, g);
}
int main()
{
…
vector visited(n + 1);
int ncomp = 0;
for (i = 1; i Пример реализации на языке PYTHON
def DFS(start):
Visited[start] = True
for v in V[start]:
if not Visited[v]:
DFS(v)
ncomp = 0
for i in range(1, n + 1):
if not Visited(i):
ncomp += 1
DFS(i)
Выполнение проверки графа на двудольность
Граф может называться двудольным, когда его вершины могут быть разбиты на два подмножества таким образом, что окончания любого ребра входят в различные множества. Другими словами, имеется возможность раскрасить вершины графа в два цвета таким образом, что окончания любого из рёбер окрашены в различные цвета.
