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

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

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

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

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

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

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

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

[править] См. также

• Поиск в ширину

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

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