Обход в глубину

Алгоритмы   20 Март 2015  Автор статьи: admin 

Обход в глубину (англ. Depth-First Search, DFS) — один из основных рекурсивных методов обхода вершин графа. Общая идея алгоритма состоит в следующем: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Таким образом, стратегия обхода в глубину следующая: идти «вглубь», пока это возможно, когда есть непройденные исходящие ребра, и возвращаться, чтобы искать другой путь, когда таких ребер нет. Впервые обнаружив вершину v графа, отмечаем это событие, проставляя в массиве used пройденных вершин значение true, used[v] \gets true. В результате обхода в глубину находится лексикографически первые пути в графе из вызванной вершины во все достижимые из нее.
Исходный граф может быть как неориентированным, так и ориентированным, сути метода это не меняет.

 

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

G(V, E) – исходный граф, в котором V – это множество вершин, а E – это множество ребер.
used – массив для хранения информации о пройденных и не пройденных вершинах графа G.

1
2
{\bf for} (для) всех вершин v \in V[G] //помечаем каждую вершину как не посещенную
    used[v] \gets {\bf false}

 
DFS(v)

1
2
3
4
5
{\bf if} used[v] = {\bf true}
    {\bf return}
used[v] \gets {\bf true} //помечаем вершину как посещенную
{\bf for} (для) всех вершин w \in E[v] //обрабатываем ребро (v, w)
    DFS(w) //вызываем процедуру рекурсивно от каждой вершины w, смежной с вершиной v

 

Классификация ребер при обходе в глубину

Дуги ориентированного графа делятся на категории в зависимости от их роли в обходе в глубину. Это классификация применяется при решении различных задач, базирующихся на методе обхода. Например, доказано, что ориентированный граф не имеет циклов тогда и только тогда, когда обход в глубину не находит в нем «обратных» дуг.
После работы обхода в глубину на ориентированном графе G построен лес G_\pi. Дуги в этом лесу классифицируются на следующие:
1. Дуги дерева – это непосредственно дуги, из которых состоит лес G_\pi, построенный в результате обхода.
2. Обратные дуги – это все дуги (u, v), соединяющие вершину u с ее предком v в одном из деревьев леса G_\pi обхода в глубину. (Встречные дуги, образующие цикл длины 2, возможные в ориентированных графах, считаются обратными дугами также).
3. Прямые дуги – это дуги, соединяющие вершину с ее потомком, но не входящие в лес G_\pi обхода в глубину.
4. Перекрестные дуги – это все остальные дуги ориентированного графа, не попавшие не в одну из вышеперечисленных категорий. Такие дуги, например, могут соединять две вершины одного дерева обхода, если ни одна из этих вершин не является предком другой.
Неориентированные графы требует особого рассмотрения, так как одно и то же ребро (u, v) = (v, u) обрабатывается дважды, с двух концов, и может попасть в разные категории. Будем относить его к той категории, которая представлена раньше в вышеприведенной классификации. При таком соглашении прямых и перекрестных ребер в неориентированном графе не будет.

 

Асимптотическая сложность

Процесс инициализации массива used и пометки каждой вершины v \in V графа как непосещенной осуществляется за O(|V|).
Процедура DFS вызывается ровно по одному разу для каждой вершины v \in V графа, так как она вызывается только для не посещенных вершин, и первое, что она делает, это помечает переданную в качестве параметра вершину процедуры как посещенную, строка 3. В процессе выполнения процедуры DFS цикл в строках 4, 5 выполняется ровно |adj[v]| раз. Так как \sum_{v \in V} |adj [v]|=O(|E|), то общая стоимость выполнения строк 4-5 процедуры DFS равна O(|E|).
Таким образом, асимптотическая сложность обхода в глубину равна O(|V|+|E|).

 

Применения метода обхода в глубину

1. Поиск лексикографически наименьшего пути в графе из заданной вершины
2. Проверка, является ли одна вершина дерева предком другой
3. Топологическая сортировка графа
4. Задача LCA (нахождение наименьшего общего предка)
5. Проверка орграфа на ацикличность и нахождение некоторого цикла в графе
6. Поиск компонент сильной связности в орграфе
7. Поиск мостов и точек сочленения в неориентированном графе

Реализации метода обхода в глубину

Научиться программировать

  • на Delphi

  • на Java

  • на C++