Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Алгоритм поиска по дереву. Еще один вариант алгоритма поиска в 
глубину основан на представлении ориентированного графа как дерева. 
Выделим одну из вершин ориентированного графа. Построим для гра-
фа дерево универсального покрытия, в качестве корня которого будем ис-
пользовать выделенную вершину. В качестве сыновей корневого узла рас-
сматриваются вершины графа, находящиеся на концах инцидентных ему ре-
бер. Затем этот процесс выполняется для каждого из сыновей корневого узла 
и т.д. Если в графе есть ориентированные циклы, то этот процесс будет бес-
конечным.
Будем предполагать, что ребра, выходящие из каждой вершины графа 
упорядочены (например, пронумерованы). Эта упорядоченность сохранится 
и для узлов дерева универсального покрытия. При обходе дерева сначала 
будет просматриваться корень, а затем – его поддеревья в порядке, опреде-
ляемом нумерацией ведущих в них ребер. Такому обходу дерева соответст-
вует обход графа. После удаления из маршрута этого обхода повторных по-
сещений получим результат, соответствующий поиску в глубину. 
Запишем этот алгоритм более подробно в терминах псевдоязыка (лис-
тинг 5.19). 
Листинг 5.19. Алгоритм поиска в глубину 
procedure FindDepth(n) 
begin 
Node[n].Visit := True; // 
отмечаем, что посетили 
вершину 
Проверить, подходит ли вершина n 
Иначе begin 
for m 
∈ Список соседних вершин do 
if 
Не посещали узел m then FindDepth(m) 
end; 
end; 
18 / 23

---

157 
Изменение поля Node[n].Visit и анализ этого поля при выборе оче-
редного узла обеспечивает нам прохождение каждого узла не более одного 
раза. Пусть N — число узлов. Тогда для каждого i-го узла нам придется про-
смотреть не более M
i
дуг. Поэтому сложность алгоритма не более N + 
ΣM
i
= 
= N + M, т. е. O(N + M). 
В листинге 5.20 приведен полный текст рекурсивной процедуры поиска 
узла по имени nameNode в глубину.