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

5.3.1.2. Алгоритмы поиска в глубину в неориентированном 
связном графе 
Алгоритм поиска через списки. Введем следующие параметры: 
Num
— последний присвоенный номер посещения, p — указатель конца стека 
Q, т. е. Q(p) — вершина стека Q. В начале работы алгоритма зададим эти па-
раметры: Num=1; numVisit(v0)=Num; Q(p)=v0; F(v0)=0; T=0; 
B= 0; p= 1.
Алгоритм состоит из следующих шагов. 
1. v = Q(p). 
2. Производится поиск вершины w, такой что ребро (v, w) являет-
ся непомеченным; если такое ребро найдено, то перейти к ша-
гу 4, иначе – к шагу 5. 
3. Если вершина w имеет номер посещения, то пометить ребро 
(v, w) как «обратное» и занести в список B. Перейти к шагу 3 и 
продолжить просмотр списка смежных вершин. Иначе 
увеличить Num на единицу и добавить его значение в список 
NumVisit, добавить в список F значение v, пометить ребро (v, w) 
как «прямое» и занести в список T. Кроме того, увеличить на 
единицу значение указателя стека p и, используя обновленное 
значение указателя, занести в стек Q вершину w. После этого 
перейти к шагу 2. 
4. Уменьшить на единицу значение указателя стека p, удалив тем 
самым вершину v из стека Q. Если p = 0, то завершить выпол-
нение алгоритма, иначе перейти к шагу 2. 
Алгоритм поиска пути между двумя вершинами. В алгоритме ис-
пользуется вспомогательный стековый массив вершин Q, q — число элемен-
тов в стеке, массив меток вершин L(n) и массивы меток ребер. Изначально 
все вершины считаются непомеченными. Алгоритм состоит из следующих 
шагов. 
1.
Поместить стартовую вершину в стек: q = 1; Q(q) = s. 
2.
Если стек не пуст, то берем вершину из стека x = Q(q); 
q = q – 1, в противном случае пути нет и алгоритм заканчива-
ет свою работу. 
3.
Если все смежные вершины просмотрены, то выполняем 
шаг 2. В противном случае рассматриваем очередную смеж-
17 / 23

---

156 
ную с x вершину y. Если y — конечная вершина, то путь най-
ден. 
4.
Проверяем наличие метки у вершины y. Если L(y) > 0, то по-
мечаем ребро как «обратное», в противном случае ребро по-
мечаем как «прямое» и присваиваем метку L(y) = L(x) + 1. 
Вершина y помещается в стек q = q + 1; Q(q) = y. 
5.
Выполняем шаг 3.