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

Материал из WEGA
Версия от 23:15, 14 декабря 2011; KVN (обсуждение | вклад) (→‎Р е ш е н и е)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

З а д а ч а

О б ъ е к т ы. Ориентированный граф [math]\displaystyle{ G }[/math].

Т р е б у е т с я. Осуществить обход в глубину графа [math]\displaystyle{ G }[/math].

Р е ш е н и е

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

проц РЕКУРСИВНЫЙ-ОБХОД([math]\displaystyle{ p }[/math]: вершина) =

1.______Посетить вершину [math]\displaystyle{ p }[/math];

2.______для всех [math]\displaystyle{ q }[/math] из множества вершин, смежных с [math]\displaystyle{ p }[/math] цикл

3.____________если [math]\displaystyle{ q }[/math] еще не посещалась то

4.___________________РЕКУРСИВНЫЙ-ОБХОД([math]\displaystyle{ q }[/math])

______________все

________все

все;

начало

1.___для всех [math]\displaystyle{ p }[/math] из множества вершин [math]\displaystyle{ G }[/math] цикл

2._____ если [math]\displaystyle{ p }[/math] еще не посещалась то

3.__________ РЕКУРСИВНЫЙ-ОБХОД([math]\displaystyle{ p }[/math])

_______все

____все

конец

Литература

  • Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003, 1104 С.