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

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

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

Алгоритм поиска в глубину

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

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

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

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

Примеры реализации

Java

public static void search(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)
            {
                search(node.getNode().get(i), goal);
            }
        }
    }   
}

С++

vector < vector<int> > graph;
 
vector<bool> used;
 
void dfs(int node_index) 
{
    used[node_index] = true;
    for (vector<int>::iterator i = graph[node_index].begin(); i != graph[node_index].end(); ++i)
    {
        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;

Литература

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

• Кормен Т., Лейзерсон Ч., Ривест Р. Глава 22. Элементарные алгоритмы для работы с графами // Алгоритмы: построение и анализ(второе издание). — М.: «Вильямс», 2005. — С. 622-632.

Ссылки

• ВКИ НГУ: Методы программирования. Обходы графа.
• СпбГУ ИТМО, Факультет информационных технологий и программирования: Дискретная математика. Алгоритмы. Обход графа в глубину.
• Реализация поиска в глубину и различные задачи, решаемые с его помощью (сайт e-maxx.ru)
• Поиск в глубину