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

Поиск в глубину на графе G=(V,E) осуществляется по следующим правилам:

1. Начинаем поиск с произвольной вершины r. В качестве текущей вершины v берем вершину r.

2. Из текущей вершины v двигаемся в любую, ранее не пройденную вершину w, если такая вершина найдется (если вершины w нет, см. пункт 3). Запоминаем дугу, по которой мы попали в вершину w. В качестве текущей вершины v берем вершину w.

3. Если из вершины v мы не можем попасть в ранее не пройденную вершину w, то возвращаемся в вершину x, из которой мы попали в v. В качестве текущей вершины v берем вершину x.

4. Процесс поиска (пункты 2, 3) заканчивается, когда мы пытаемся вернуться назад из вершины, с которой начался поиск (вершина r).

Поиск в глубину проиллюстрирован на рис. 3.16.