Поиск в глубину

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Порядок обхода дерева в глубину

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин[1].

Применение[править | править вики-текст]

  • В качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент.
  • В топологической сортировке.
  • В различных расчётах на графах. Например, как часть алгоритма Диница поиска максимального потока.
  • В поиске по древовидным структурам.

Алгоритм поиска в глубину[править | править вики-текст]

Пусть задан граф G = (V, E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

  1. Пройдём по всем вершинам v \in V.
    • Если вершина v белая, выполним для неё DFS(v).

Процедура DFS (параметр — вершина u \in V)

  1. Перекрашиваем вершину u в серый цвет.
  2. Для всякой вершины w, смежной с вершиной u и окрашенной в белый цвет, рекурсивно выполняем процедуру DFS(w)[2].
  3. Перекрашиваем вершину u в чёрный цвет.

Часто используют двухцветные метки — без серого, на 1-м шаге красят сразу в чёрный цвет.

Нерекурсивные варианты[править | править вики-текст]

На больших графах поиск в глубину серьёзно нагружает стек вызовов. Если есть риск переполнения стека, используют нерекурсивные варианты поиска.

Первый вариант: можно сэмулировать стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер u и номер текущей смежной вершины w.

Процедура DFS (параметр — вершина u \in V)

  1. Кладём на стек пару (u, \varnothing). Перекрашиваем вершину u в серый цвет.
  2. Пока стек не пуст…
    1. Берём верхнюю пару (v, w), не извлекая её из стека.
    2. Находим вершину w', смежную с v и следующую за w.
      1. Если таковой нет, извлекаем (v, w) из стека, перекрашиваем вершину v в чёрный цвет.
      2. В противном случае присваиваем w := w'.
        • Если к тому же вершина w' белая, кладём на стек пару (w', \varnothing), перекрашиваем w' в серый цвет.

Второй вариант: можно в каждой из «серых» вершин держать текущее w и указатель на предыдущую (ту, из которой пришли).

Третий вариант работает, если хватает двухцветных меток.

Процедура DFS (параметр — вершина u \in V)

  1. Кладём на стек вершину u.
  2. Пока стек не пуст…
    1. Берём верхнюю вершину v.
    2. Если она белая…
      1. Перекрашиваем её в чёрный цвет.
      2. Кладём в стек все смежные с v белые вершины.

Поиск в глубину с метками времени. Классификация рёбер[править | править вики-текст]

Поиск в глубину с метками времени. Порядок выбора рёбер — слева направо.

Для каждой из вершин установим два числа — «время» входа entry[u] и «время» выхода leave[u].

Модифицируем процедуру DFS так.

  1. Увеличиваем «текущее время» на 1. entry[u] = t.
  2. Перекрашиваем вершину u в серый цвет.
  3. Для всякой вершины w, смежной с вершиной u и окрашенной в белый цвет, выполняем процедуру DFS(w).
  4. Перекрашиваем вершину u в чёрный цвет.
  5. Увеличиваем «текущее время» на 1. leave[u] = t.

Считаем, что граф ориентированный. Очевидно, для любой вершины entry[u] < leave[u]. Просматриваемые на шаге 3 дуги uv могут быть:

  • entry[u] \leqslant t < entry[v] < leave[v] < leave[u]. В момент выполнения шага 3 (обозначенный как t) вершина v белая. В таком случае мы для вершины v исполняем DFS, а дуга называется дугой дерева поиска.
  • entry[u] < entry[v] < leave[v] \leqslant t < leave[u]. В момент t вершина v чёрная, сравнение entry говорит, что в v попали из u. Такая дуга называется прямой.
  • entry[v] < leave[v] < entry[u] \leqslant t < leave[u]. В момент t вершина v также чёрная, но сравнение entry говорит, что в v попали в обход u. Такая дуга называется перекрёстной.
  • entry[v] < entry[u] \leqslant t < leave[u] < leave[v]. В момент t вершина v серая. Имеем дело с обратной дугой.

Рёбра неориентированного графа могут быть рёбрами дерева и обратными, но не прямыми и перекрёстными.[3] Чтобы различать рёбра неориентированного графа, достаточно указанных выше трёх- или двухцветных отметок. Ребро, идущее в белую вершину,— ребро дерева. В серую (чёрную в двухцветном варианте) — обратное. В чёрную — такого не бывает.[4]

Алгоритм Косарайю требует сортировки вершин в обратном порядке по времени выхода. Метка входа и типы рёбер нужны в алгоритмах поиска точек сочленения и мостов.

Примеры реализации[править | править вики-текст]

Java[править | править вики-текст]

List<Integer>[] graph = readGraph();
boolean[] used = new boolean[graph.length];
 
public static void dfs(int pos) {
    used[pos] = true;
    System.out.println(pos);
    for (int next : graph[pos])
        if (!used[next])
            dfs(next);
}

С++[править | править вики-текст]

vector < vector<int> > graph;
 
vector<bool> used;
 
void dfs(int node_index)
{
    used[node_index] = true;
    for (auto i : graph[node_index])
    {
        if (!used[i])
            dfs(i);
    }
}

Pascal[править | править вики-текст]

const
  MAX_N = 10;
var
  graph:   array [1..MAX_N, 1..MAX_N] of boolean;  // массив для определения графа
  visited: array [1..MAX_N] of boolean;
 
procedure dfs(v: integer);
var
  i: integer;
begin
  visited[v] := true;
 
  for i := 1 to MAX_N do
    if graph[v, i] and not visited[i] then 
      dfs(i);
end;

Python[править | править вики-текст]

g = [[0,1,0],  # матрица связности
     [1,1,0],
     [0,0,1]]
 
ex = set()       # множество посещенных вершин
def dfs(node):   # start - начальная вершина
    ex.add(node)
    for i in range(len(g)):
        if g[node][i] == 1 and i not in ex:
            print(i)
            dfs(i)

PHP[править | править вики-текст]

$graph = array( 'A' => array('B','C','D','Z'),
		'B' => array('A','E'),
		'C' => array('A','F','G'),
		'D' => array('A','I'),
		'E' => array('B','H'),
		'F' => array('C','J'),
		'G' => array('C'),
		'H' => array('E','Z'),
		'I' => array('D'),
		'J' => array('J'),
		'Z' => array('A','H'));
 
function dfs( $graph , $startNode = 'A' )
{
  global $visited;
  $visited[] = $startNode;	
 
  foreach($graph[$startNode] as $index => $vertex)
  {
    if( !in_array( $vertex , $visited ) )
      dfs( $graph , $vertex );
  }
}

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

Примечания[править | править вики-текст]

  1. Cormen, p. 622
  2. Обход в глубину, цвета вершин — Викиконспекты
  3. Если в сторону u→v оно прямое, то ранее его прошли в сторону v→u как обратное. Если в сторону u→v оно перекрёстное, его должны были пройти v→u как ребро дерева.
  4. Cormen, с. 628-629

Литература[править | править вики-текст]

  • Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Поиск в глубину // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 212-215. — ISBN 0-201-74395-7.
  • Кормен Т., Лейзерсон Ч., Ривест Р. Глава 22. Элементарные алгоритмы для работы с графами // Алгоритмы: построение и анализ(второе издание). — М.: «Вильямс», 2005. — С. 622-632.

Ссылки[править | править вики-текст]