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

5.3.1.1. Алгоритм обхода графа с поиском в глубину 
Пусть G — неориентированный связный граф. Для организации поиска 
будем использовать признак посещенности узла numVisit и признак про-
хождения по ребру select. Перед началом поиска булевские поля select 
получают значение false (ребра не помечены), а целочисленные признаки 
посещенности вершин – нулевые значения. 
Начинаем с произвольной вершины v
0
, присваиваем ей номер посеще-
ния, равный 1, и выбираем произвольное ребро (v
0
, w). Ребро (v
0
, w) помеча-
ется как «прямое», а вершина w, достигнутая из v
0
, получает номер посеще-
ния, равный 2. После этого переходим в вершину w. 
Пусть в результате выполнения нескольких шагов этого процесса мы 
пришли в вершину x, и пусть Num — последний присвоенный номер посеще-
ния. Возможны следующие ситуации: 
− имеются непомеченные ребра, инцидентные этой вершине; 
− все ребра, инцидентные вершине x, помечены.
В первом случае анализируем первое из непомеченных ребер (x, y). Ес-
ли у вершины y уже есть номер посещения, то это ребро помечается как «об-
ратное» и продолжается поиск непомеченного ребра, инцидентного вершине 
x. Если вершина y не имеет номера посещения, то переходим в эту вершину, 
увеличивая число ее посещений на единицу и помечая ребро (x, y) как «пря-
мое». Вершина y считается получившей свой номер посещения из вершины x. 
На следующем шаге начинаем просматривать ребра, инцидентные вершине y. 
Во втором случае возвращаемся в вершину, из которой x получила свой 
номер посещения. Процесс закончится, когда все ребра будут помечены и 
произойдет возвращение в вершину v
0
. 
Описанный процесс можно реализовать так, чтобы время работы соот-
ветствующего алгоритма составляло O(M + N), где M — число ребер графа, 
N — число вершин графа. Для этого по мере обработки графа необходимо 
16 / 23

---

155 
формировать четыре списка: список посещений NumVisit, список имен 
вершин F, список ориентированных «прямых» ребер T, список ориентиро-
ванных «обратных» ребер B. Ребра графа получают ориентацию в процессе 
работы алгоритма. Если ребро (x, y) помечается из вершины x как «прямое», 
то в T заносится дуга (x, y), а если как «обратное», то эта дуга заносится в 
список B. Элементом списка NumVisit является номер посещения вершины, 
а элементом списка F – имя вершины, из которой соответствующая вершина 
получила свой номер посещения.