Алгоритм обхода графов

Построим дерево обхода.

 0 - 1 2 3 

 

. . 3 - 4 5 

 

. . . . 5 - 6 7 8 9 

 

. . . . . . 9 - 

 

. . . . . . 8 - 10 

 

. . . . . . . . 10 - 

 

. . . . . . 7 - 

 

. . . . . . 6 - 

 

. . . . 4 - 11 12 

 

. . . . . . 12 - 13 

 

. . . . . . . .  13 - 14 

 

. . . . . . . . . . . 14 - 15 

 

. . . . . . . . . . . . .  15 - 16 

 

. . . . . . . . . . . . . . . . 16 - 17 18 

 

. . . . . . . . . . . . . . . . . .  18 - 19 

 

. . . . . . . . . . . . . . . . . . . . . 19 - 

 

. . . . . . . . . . . . . . . . . .  17 - 

 

. . . . . . 11 - 

 

. . 2 - 

 

. . 1 -  

Легко видеть, что дерево соответствует поиску в глубину с небольшой модификацией (нерекурсивный вариант с прямым порядком помещения в стек или, в других терминах, с использованием стека вместо очереди).