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

Материал из Поле цифровой дидактики
Версия от 08:09, 26 июля 2022; ru_wikipedia>InternetArchiveBot (Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Файл:Depth-first-tree.svg
Порядок обхода дерева в глубину

Поиск в глубину (Шаблон:Lang-en) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин{{#if: | }}<ref name="{{#if: | | _7b9873a2d90ce124 }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}.

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

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

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

Процедура DFS (параметр — вершина [math]\displaystyle{ u \in V }[/math])

  1. Перекрашиваем вершину [math]\displaystyle{ u }[/math] в серый цвет.
  2. Для всякой вершины [math]\displaystyle{ w }[/math], смежной с вершиной [math]\displaystyle{ u }[/math] и окрашенной в белый цвет, рекурсивно выполняем процедуру DFS(w)<ref>Шаблон:Cite web</ref>.
  3. Перекрашиваем вершину [math]\displaystyle{ u }[/math] в чёрный цвет.

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

Нерекурсивные варианты

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

Первый вариант, простейший, но дающий немалый объём стека — до |E|.

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

Если хватает двухцветных меток…

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

Второй вариант: можно симулировать стек вызова программно: для каждой из серых вершин в стеке будет храниться её номер [math]\displaystyle{ u }[/math] и номер текущей смежной вершины [math]\displaystyle{ w }[/math].

Процедура DFS (параметр — вершина [math]\displaystyle{ u \in V }[/math])

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

Третий вариант: можно в каждой из «серых» вершин держать текущее [math]\displaystyle{ w }[/math] и указатель на предыдущую (ту, из которой пришли).

Поиск в глубину с метками времени. Классификация рёбер

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

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

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

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

Считаем, что граф ориентированный. Очевидно, для любой вершины, из которой мы не вышли в момент t, [math]\displaystyle{ entry[u] \leqslant t \lt leave[u] }[/math]. Также невозможно скрёстное неравенство: [math]\displaystyle{ entry[u] \lt entry[v] \lt leave[u] \lt leave[v] }[/math]. Просматриваемые на шаге 3 дуги u→v могут быть:

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

Рёбра неориентированного графа могут быть рёбрами дерева и обратными, но не прямыми и перекрёстными.<ref>Если в сторону u→v оно прямое, то ранее его прошли в сторону v→u как обратное. Если в сторону u→v оно перекрёстное, его должны были пройти v→u как ребро дерева.</ref> Чтобы различать рёбра неориентированного графа, достаточно указанных выше трёх- или двухцветных отметок. Ребро, идущее в белую вершину,— ребро дерева. В серую (чёрную в двухцветном варианте) — обратное. В чёрную — такого не бывает.{{#if: | }}<ref name="{{#if: | | _2258f5c206c46225 }}" group="{{#if: | }}">Шаблон:Sfn-текст.</ref>{{#if: | }}

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

Применение

Поиск в глубину ограниченно применяется как собственно поиск, чаще всего на древовидных структурах: когда расстояние между точками малó, поиск в глубину может «плутать» где-то далеко.

Зато поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например:

Поиск в глубину — естественный выбор, когда агент (человек или робот) лично ходит по лабиринту и видит то, что непосредственно рядом с ним. «Правило левой руки» (идти, ведя левой рукой по стенке) будет поиском в глубину, если лабиринт древовидный (нет кружных путей).

См. также

Примечания

1 }} 
       | {{#switch: {{{1}}}
         | узкие = columns reflist-narrow
         | широкие = columns reflist-wide
         | #default = columns
         }}
       | {{#switch: {{{1}}}
         | 1 = 
         | 2 | 3 = columns
         | #default = columns reflist-narrow
         }}
       }}
     | columns
     }}
   }}" style="{{#if: 
   | column-width:{{{colwidth}}};
   | {{#if: 
     | {{#iferror: {{#ifexpr: {{{1}}} > 1 }}
       | {{#switch: {{{1}}}
         | узкие | широкие = 
         | #default = column-width:{{{1}}};
         }}
       }}
     }}
   }} list-style-type: {{#switch: 
   | upper-alpha
   | upper-roman
   | lower-alpha
   | lower-greek
   | lower-roman = {{{group}}}
   | #default = decimal
   }};">

<references group="" responsive="{{#if: 

 | 0
 | {{#if: 
   | {{#iferror: {{#expr: {{{1}}} > 1 }}
     | {{#switch: {{{1}}}
       | узкие | широкие = 1
       | #default = 0
       }}
     | {{#switch: {{{1}}}
       | 1 = 0
       | #default = 1
       }}
     }}
   | 1
   }}
}}"></references>

Ошибка скрипта: Модуля «Check for unknown parameters» не существует.

Литература

  • Шаблон:Source
  • {{#if:Кормен Т., Лейзерсон Ч., Ривест Р.|Кормен Т., Лейзерсон Ч., Ривест Р. }}{{#if: Глава 22. Элементарные алгоритмы для работы с графами|{{#if: |[{{{ссылка часть}}} Глава 22. Элементарные алгоритмы для работы с графами]| Глава 22. Элементарные алгоритмы для работы с графами}} // }}{{#if:|[[:s:{{{викитека}}}|Алгоритмы: построение и анализ(второе издание)]]|{{#if:|[ Алгоритмы: построение и анализ(второе издание)]|Алгоритмы: построение и анализ(второе издание)}}}}{{#if:| = {{{оригинал}}} }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Алгоритмы: построение и анализ(второе издание)|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — {{{издание}}}.}}{{#switch:{{#if:М.|м}}{{#if:«Вильямс»|и}}{{#if:2005|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: «Вильямс», 2005.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: «Вильямс».
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}, 2005.
 |иг= — «Вильямс», 2005.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М..}} }}
 |и= — «Вильямс».
 |г= — 2005.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:622—632| — С. 622—632.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN {{{isbn}}}}}

Ссылки

Шаблон:Wikibooks

Шаблон:Rq Шаблон:Алгоритмы поиска на графах

Источник — http://digida.mgpu.ru/index.php?title=Поиск_в_глубину&oldid=4648