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

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

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все непройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.

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

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

  1. Из множества всех белых вершин выберем любую вершину, обозначим её v_1.
  2. Выполняем для неё процедуру DFS(v_1).
  3. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

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

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

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

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

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

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

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

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

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

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

Ребро, идущее в белую вершину,— ребро дерева. В серую — обратное. В чёрную — перекрёстное.

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

Примеры реализации[править | править исходный текст]

Java[править | править исходный текст]

public static void dfs(Node node, Node goal) { // Node - вершина графа
    if (node.equals(goal)) {
            System.out.println(node);
    } else {
 
        for (int i = 0; i < node.getNode().size(); i++) { // Вызываем этот же метод для каждой смежной вершины
 
            if (stack.add(node.getNode().get(i))) { // Проверяем, вызывали ли мы этот метод для вершины node.getNode().get(i)
 
                dfs(node.getNode().get(i), goal);
            }
        }
    }   
}

С++[править | править исходный текст]

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[править | править исходный текст]

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

См. также[править | править исходный текст]

Литература[править | править исходный текст]

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

Ссылки[править | править исходный текст]