Поиск в глубину
Материал из Википедии — свободной энциклопедии
Порядок обхода дерева в глубину
Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все непройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.
[править] Алгоритм поиска в глубину
Пусть задан граф G = (V,E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:
- Из множества всех белых вершин выберем любую вершину, обозначим её v1.
- Выполняем для нее процедуру
DFS(v1). - Перекрашиваем ее в черный цвет.
- Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.
Процедура DFS (параметр — вершина 
)
- Перекрашиваем вершину u в серый цвет.
- Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:
- Если вершина w окрашена в белый цвет, выполняем процедуру
DFS(w). - Окрашиваем w в черный цвет.
- Если вершина w окрашена в белый цвет, выполняем процедуру
| Алгоритмы поиска на графах |
|---|
[править] Литература
- Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Поиск в глубину // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 212-215. — ISBN 0-201-74395-7
- Кормен Т., Лейзерсон Ч., Ривест Р. Глава 22. Элементарные алгоритмы для работы с графами // Алгоритмы: построение и анализ(второе издание). — М.: «Вильямс», 2005. — С. 622-632.
