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

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

Поиск в глубину (англ. 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[править | править вики-текст]

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 );
  }
}

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

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

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

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