Поиск в глубину: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Поиск в глубину''' (''[[Depth first search]]'') -
'''Поиск в глубину''' (''[[Depth first search]]'')
метод систематического прохождения (посещения) [[вершина|вершин]] [[граф|графа]],
метод систематического прохождения (посещения) [[вершина|вершин]] [[граф|графа]],
когда за счет продвижений от текущей вершины по [[ребро|ребру]] вперед (к еще непросмотренной вершине)
когда за счет продвижений от текущей вершины по [[ребро|ребру]] вперед (к еще непросмотренной вершине)
всегда, когда это возможно, и возвратов от текущей вершины по пройденному ребру назад
всегда, когда это возможно, и возвратов от текущей вершины по пройденному ребру назад
(к ранее пройденной вершине), если движение вперед от текущей вершины невозможно,
(к ранее пройденной вершине), если движение вперед от текущей вершины невозможно,
осуществляется движение по всем вершинам графа, [[достижимая вершина|достижимым]] из заданной вершины <math>s</math>, с которой начинается поиск. Поиск в глубину всегда завершается через конечное число шагов
осуществляется движение по всем вершинам графа, [[достижимая вершина|достижимым]] из заданной вершины <math>\,s</math>, с которой начинается поиск. Поиск в глубину всегда завершается через конечное число шагов
в вершине <math>s</math> --- начале просмотра; после его завершения все ребра [[связный граф|связного графа]] оказываются разбитыми на два класса: ''древесные'', по которым осуществлялись переходы из посещенных вершин в непосещенные, и ''ребра касания'', замыкающие циклы. Частичный граф,
в вершине <math>\,s</math> начале просмотра; после его завершения все ребра [[связный граф|связного графа]] оказываются разбитыми на два класса: ''древесные'', по которым осуществлялись переходы из посещенных вершин в непосещенные, и ''ребра касания'', замыкающие циклы. Частичный граф,
порожденный древесными ребрами, называется ''деревом поиска в глубину''; он является ''каркасом графа''. ''Нумерация вершин'' графа в порядке их первого посещения в процессе поиска в глубину
порожденный древесными ребрами, называется ''деревом поиска в глубину''; он является ''каркасом графа''. ''Нумерация вершин'' графа в порядке их первого посещения в процессе поиска в глубину
называется ''<math>M</math>-нумерацией''. В случае несвязного графа поиск в
называется ''<math>\,M</math>-нумерацией''. В случае несвязного графа поиск в
глубину, завершившийся обходом очередной компоненты связности графа, продолжается с любой еще непросмотренной вершины.
глубину, завершившийся обходом очередной [[компонента связности|компоненты связности]] графа, продолжается с любой еще непросмотренной вершины.


Поиск в глубину в [[орграф|орграфе]] отличается тем, что при движении вперед [[дуга|дуги]] проходятся в соответствии с их ориентацией. При этом после завершения пройденные дуги оказываются разбитыми на
Поиск в глубину в [[орграф|орграфе]] отличается тем, что при движении вперед [[дуга|дуги]] проходятся в соответствии с их ориентацией. При этом после завершения пройденные дуги оказываются разбитыми на
четыре класса: ''древесные'', ''прямые'', замыкающие какой-либо [[путь]] из [[древесная дуга|древесных дуг]], ''обратные'', замыкающие [[контур]], и ''поперечные'', ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. [[Частичный граф|Частичный орграф]], порожденный древесными дугами, является либо корневым растущим [[ордерево|ордеревом]] (''дерево поиска в глубину''), либо [[лес|лесом]], каждая компонента которого есть [[корневое дерево|корневое растущее дерево]].
четыре класса: ''древесные'', ''прямые'', замыкающие какой-либо [[путь]] из [[древесная дуга|древесных дуг]], ''обратные'', замыкающие [[контур]], и ''поперечные'', ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. [[Частичный граф|Частичный орграф]], порожденный древесными дугами, является либо корневым растущим [[ордерево|ордеревом]] (''[[дерево поиска в глубину]]''), либо [[лес|лесом]], каждая компонента которого есть [[корневое дерево|корневое растущее дерево]].


Поиск в глубину является основой многих алгоритмов исследования структуры графа.
Поиск в глубину является основой многих алгоритмов исследования структуры графа.


Другие названия ---''[[Возвратный ход]], [[Бектрекинг]], [[Обход графа в глубину]]''.
Другие названия ''[[Возвратный ход]], [[Бектрекинг]], [[Обход графа в глубину]]''.


==См. также==  
==См. также==  
''[[Базисная нумерация]], [[K-Нумерация|K-нумерация]], [[L-Нумерация|L-нумерация]], [[M-Нумерация|M-нумерация]], [[T-Нумерация|T-нумерация]], [[Обход графа]], [[Поиск в ширину]], [[Правильная нумерация]], [[Разумная нумерация]], [[Топологическая сортировка]], [[Укладка уграфа]]''.
* ''[[Базисная нумерация]],''
* ''[[K-Нумерация|<math>\,K</math>-нумерация]],''
* ''[[L-Нумерация|<math>\,L</math>-нумерация]],''
* ''[[M-Нумерация|<math>\,M</math>-нумерация]],''
* ''[[T-Нумерация|<math>\,T</math>-нумерация]],''
* ''[[Обход графа]],''
* ''[[Поиск в ширину]],''
* ''[[Правильная нумерация]],''
* ''[[Разумная нумерация]],''
* ''[[Топологическая сортировка]],''
* ''[[Укладка уграфа]].''  
==Литература==
==Литература==
[Ахо-Хопкрофт-Ульман],
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —  М.: Мир, 1979.


[Касьянов/88],  
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Евстигнеев-Касьянов/94]
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

Версия от 13:03, 8 июня 2011

Поиск в глубину (Depth first search) — метод систематического прохождения (посещения) вершин графа, когда за счет продвижений от текущей вершины по ребру вперед (к еще непросмотренной вершине) всегда, когда это возможно, и возвратов от текущей вершины по пройденному ребру назад (к ранее пройденной вершине), если движение вперед от текущей вершины невозможно, осуществляется движение по всем вершинам графа, достижимым из заданной вершины [math]\displaystyle{ \,s }[/math], с которой начинается поиск. Поиск в глубину всегда завершается через конечное число шагов в вершине [math]\displaystyle{ \,s }[/math] — начале просмотра; после его завершения все ребра связного графа оказываются разбитыми на два класса: древесные, по которым осуществлялись переходы из посещенных вершин в непосещенные, и ребра касания, замыкающие циклы. Частичный граф, порожденный древесными ребрами, называется деревом поиска в глубину; он является каркасом графа. Нумерация вершин графа в порядке их первого посещения в процессе поиска в глубину называется [math]\displaystyle{ \,M }[/math]-нумерацией. В случае несвязного графа поиск в глубину, завершившийся обходом очередной компоненты связности графа, продолжается с любой еще непросмотренной вершины.

Поиск в глубину в орграфе отличается тем, что при движении вперед дуги проходятся в соответствии с их ориентацией. При этом после завершения пройденные дуги оказываются разбитыми на четыре класса: древесные, прямые, замыкающие какой-либо путь из древесных дуг, обратные, замыкающие контур, и поперечные, ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. Частичный орграф, порожденный древесными дугами, является либо корневым растущим ордеревом (дерево поиска в глубину), либо лесом, каждая компонента которого есть корневое растущее дерево.

Поиск в глубину является основой многих алгоритмов исследования структуры графа.

Другие названия — Возвратный ход, Бектрекинг, Обход графа в глубину.

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.