Рекурсивный алгоритм обхода графа в глубину

===================== З а д а ч а ==============================

О б ъ е к т ы. Ориентированный граф G.

Т р е б у е т с я. Осуществить обход в глубину графа G.

==================== Р е ш е н и е =============================

М е т о д. Используя рекурсивную процедуру, линейный по временной сложности алгоритм обхода графа G в глубину можно записать следующим образом:

проц РЕКУРСИВНЫЙ-ОБХОД(p: вершина) =

1.______Посетить вершину p;

2.______для всех q из множества вершин, смежных с p цикл

3.____________если q еще не посещалась то

4.___________________РЕКУРСИВНЫЙ-ОБХОД(q)

______________все

________все

все;

начало

1.___для всех p из множества вершин G цикл

2._____ если p еще не посещалась то

3.__________ РЕКУРСИВНЫЙ-ОБХОД(p)

_______все

____все

конец