Поиск в глубину: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Поиск в глубину''' (''Depth first search'') - метод систематического прохождения (пос...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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-нумерация, L-нумерация, M-нумерация, T-нумерация, Обход графа, Поиск в ширину, Правильная нумерация, Разумная нумерация, Топологическая сортировка, Укладка уграфа''. | ==См. также== | ||
''[[Базисная нумерация]], [[K-Нумерация|K-нумерация]], [[L-Нумерация|L-нумерация]], [[M-Нумерация|M-нумерация]], [[T-Нумерация|T-нумерация]], [[Обход графа]], [[Поиск в ширину]], [[Правильная нумерация]], [[Разумная нумерация]], [[Топологическая сортировка]], [[Укладка уграфа]]''. | |||
==Литература== | ==Литература== | ||
[Ахо-Хопкрофт-Ульман], | [Ахо-Хопкрофт-Ульман], | ||
Версия от 13:11, 18 декабря 2009
Поиск в глубину (Depth first search) - метод систематического прохождения (посещения) вершин графа, когда за счет продвижений от текущей вершины по ребру вперед (к еще непросмотренной вершине) всегда, когда это возможно, и возвратов от текущей вершины по пройденному ребру назад (к ранее пройденной вершине), если движение вперед от текущей вершины невозможно, осуществляется движение по всем вершинам графа, достижимым из заданной вершины [math]\displaystyle{ s }[/math], с которой начинается поиск. Поиск в глубину всегда завершается через конечное число шагов в вершине [math]\displaystyle{ s }[/math] --- начале просмотра; после его завершения все ребра связного графа оказываются разбитыми на два класса: древесные, по которым осуществлялись переходы из посещенных вершин в непосещенные, и ребра касания, замыкающие циклы. Частичный граф, порожденный древесными ребрами, называется деревом поиска в глубину; он является каркасом графа. Нумерация вершин графа в порядке их первого посещения в процессе поиска в глубину называется [math]\displaystyle{ M }[/math]-нумерацией. В случае несвязного графа поиск в глубину, завершившийся обходом очередной компоненты связности графа, продолжается с любой еще непросмотренной вершины.
Поиск в глубину в орграфе отличается тем, что при движении вперед дуги проходятся в соответствии с их ориентацией. При этом после завершения пройденные дуги оказываются разбитыми на четыре класса: древесные, прямые, замыкающие какой-либо путь из древесных дуг, обратные, замыкающие контур, и поперечные, ведущие в ранее пройденные вершины и не замыкающие ни контур, ни путь из древесных дуг. Частичный орграф, порожденный древесными дугами, является либо корневым растущим ордеревом (дерево поиска в глубину), либо лесом, каждая компонента которого есть корневое растущее дерево.
Поиск в глубину является основой многих алгоритмов исследования структуры графа.
Другие названия ---Возвратный ход, Бектрекинг, Обход графа в глубину.
См. также
Базисная нумерация, K-нумерация, L-нумерация, M-нумерация, T-нумерация, Обход графа, Поиск в ширину, Правильная нумерация, Разумная нумерация, Топологическая сортировка, Укладка уграфа.
Литература
[Ахо-Хопкрофт-Ульман],
[Касьянов/88],
[Евстигнеев-Касьянов/94]