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

Материал из Википедии — свободной энциклопедии

Поиск в глубину — один из методов обхода графа. Кратко суть алгоритма можно изложить так: для каждой непройденной вершины необходимо найти все непройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска двусвязных компонент, односвязных компонент, топологической сортировки.

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

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

1. Из множества всех белых вершин выберем любую вершину, обозначим её v₁.
2. Выполняем для нее процедуру DFS(v1).
3. Перекрашиваем ее в черный цвет.
4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр — вершина )

1. Перекрашиваем вершину u в серый цвет.
2. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:
   1. Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).
   2. Окрашиваем w в черный цвет.

Алгоритмы поиска на графах
A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению

[править] Ссылки

• ВКИ НГУ: Методы программирования. Обходы графа.
• СпбГУ ИТМО, Факультет информационных технологий и программирования: Дискретная математика. Алгоритмы. Обход графа в глубину.
• Реализация поиска в глубину, а также его приложения к решению задач на maximal.hocomua.ru

[править] Литература

• Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Поиск в глубину // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 212-215. — ISBN 0-201-74395-7

• Кормен Т., Лейзерсон Ч., Ривест Р. Глава 22. Элементарные алгоритмы для работы с графами // Алгоритмы: построение и анализ(второе издание). — М.: «Вильямс», 2005. — С. 622-632.