1033
правки
Поиск в глубину: различия между версиями
Перейти к навигации
Перейти к поиску
м
Откат правок KVN (обсуждение) к версии GDS
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) м (Откат правок KVN (обсуждение) к версии GDS) Метка: откат |
||
| (не показаны 3 промежуточные версии 3 участников) | |||
| Строка 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>-нумерацией''. В случае несвязного графа поиск в | ||
глубину, завершившийся обходом очередной компоненты связности графа, продолжается с любой еще непросмотренной вершины. | глубину, завершившийся обходом очередной [[компонента связности|компоненты связности]] графа, продолжается с любой еще непросмотренной вершины. | ||
Поиск в глубину в [[орграф|орграфе]] отличается тем, что при движении вперед [[дуга|дуги]] проходятся в соответствии с их ориентацией. При этом после завершения пройденные дуги оказываются разбитыми на | Поиск в глубину в [[орграф|орграфе]] отличается тем, что при движении вперед [[дуга|дуги]] проходятся в соответствии с их ориентацией. При этом после завершения пройденные дуги оказываются разбитыми на | ||
четыре класса: ''древесные'', ''прямые'', замыкающие какой-либо [[путь]] из [[древесная дуга|древесных дуг]], ''обратные'', замыкающие [[контур]], и ''поперечные'', ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. [[Частичный граф|Частичный орграф]], порожденный древесными дугами, является либо корневым растущим [[ордерево|ордеревом]] (''дерево поиска в глубину''), либо [[лес|лесом]], каждая компонента которого есть [[корневое дерево|корневое растущее дерево]]. | четыре класса: ''древесные'', ''прямые'', замыкающие какой-либо [[путь]] из [[древесная дуга|древесных дуг]], ''обратные'', замыкающие [[контур]], и ''поперечные'', ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. [[Частичный граф|Частичный орграф]], порожденный древесными дугами, является либо корневым растущим [[ордерево|ордеревом]] (''[[дерево поиска в глубину]]''), либо [[лес|лесом]], каждая компонента которого есть [[корневое дерево|корневое растущее дерево]]. | ||
Поиск в глубину является основой многих алгоритмов исследования структуры графа. | Поиск в глубину является основой многих алгоритмов исследования структуры графа. | ||
Другие названия | Другие названия — ''[[Возвратный ход]], [[Бектрекинг]], [[Обход графа в глубину]]''. | ||
==Пример визуализации== | |||
[[Файл:Dfs_tree.gif]] | |||
==См. также== | ==См. также== | ||
''[[Базисная нумерация]], [[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. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||