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

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

Поиск в глубину (англ. 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).

Недостатки

  • Во-первых, отыскивается не самый короткий путь;
  • Во-вторых, если в дереве есть бесконечные ветви и если такая бесконечная ветвь встретится, поиск никогда не закончится, даже если есть конечный путь в целевую вершину.

Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Причина этого состоит в том, что, обрабатывая цели, пролог-система сама просматривает альтернативы именно в глубину.

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

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 (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.

Ссылки



Wikimedia Foundation. 2010.

Смотреть что такое "Поиск в глубину" в других словарях:

  • поиск в глубину — В ИИ алгоритм поиска в пространстве решений. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN depth first search …   Справочник технического переводчика

  • Поиск в ширину — Порядок обхода дерева в ширину Поиск в ширину (BFS, Breadth first search)  метод обхода и разметки вершин графа. Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам  метка 1.… …   Википедия

  • Поиск по первому наилучшему совпадению — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… …   Википедия

  • Поиск с возвратом — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете …   Википедия

  • поиск преимущественно в глубину — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN depth first search …   Справочник технического переводчика

  • ПОИСК ЗАТОНУВШИХ СУДОВ — Комплекс мероприятий по установлению и обозначению точного места затонувшего судна. П.З.С., как правило, очень сложен и длителен, особенно на больших глубинах и в удаленных районах Мирового океана. Производится с помощью судов различного типа,… …   Морской энциклопедический справочник

  • Двунаправленный поиск — Для улучшения этой статьи по информационным технологиям желательно?: Добавить иллюстрации. Проставив сноски, внести более точные указания на источники …   Википедия

  • Алгоритм Косарайю — Алгоритм Косарайю  алгоритм поиска компонент сильной связности в орграфе. Чтобы найти компоненты сильной связности, сначала выполняется поиск в глубину (DFS) на обращении исходного графа (ребра инвертированы), вычисляя вектор обратного… …   Википедия

  • Алгоритм поиска A* — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… …   Википедия

  • А* — Алгоритмы поиска на графах A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению Поиск A* (произносится «А звездочка») в информатике и математике, алгоритм …   Википедия

Книги

Другие книги по запросу «Поиск в глубину» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.