Рекурсивный алгоритм обхода графа в глубину: различия между версиями
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
== З а д а ч а == | |||
О б ъ е к т ы. Ориентированный граф G. | О б ъ е к т ы. Ориентированный граф <math>G</math>. | ||
Т р е б у е т с я. Осуществить [[Поиск в глубину|обход в глубину]] графа G. | Т р е б у е т с я. Осуществить [[Поиск в глубину|обход в глубину]] графа <math>G</math>. | ||
== Р е ш е н и е == | |||
М е т о д. Используя рекурсивную процедуру, линейный | М е т о д. Используя рекурсивную процедуру, линейный | ||
по временной сложности алгоритм обхода графа G в глубину | по временной сложности алгоритм обхода графа <math>G</math> в глубину | ||
можно записать следующим образом: | можно записать следующим образом: | ||
'''проц''' РЕКУРСИВНЫЙ-ОБХОД(p: ''вершина'') = | '''проц''' РЕКУРСИВНЫЙ-ОБХОД(<math>p</math>: ''вершина'') = | ||
1.______Посетить вершину p; | 1.______Посетить вершину <math>p</math>; | ||
2.______'''для всех''' q из множества вершин, смежных с p '''цикл''' | 2.______'''для всех''' <math>q</math> из множества вершин, смежных с <math>p</math> '''цикл''' | ||
3.____________'''если''' q еще не посещалась '''то''' | 3.____________'''если''' <math>q</math> еще не посещалась '''то''' | ||
4.___________________РЕКУРСИВНЫЙ-ОБХОД(q) | 4.___________________РЕКУРСИВНЫЙ-ОБХОД(<math>q</math>) | ||
______________'''все''' | ______________'''все''' | ||
| Строка 28: | Строка 29: | ||
'''начало''' | '''начало''' | ||
1.___'''для всех''' p '''из''' множества вершин G '''цикл''' | 1.___'''для всех''' <math>p</math> '''из''' множества вершин <math>G</math> '''цикл''' | ||
2._____ '''если''' p еще не посещалась '''то''' | 2._____ '''если''' <math>p</math> еще не посещалась '''то''' | ||
3.__________ РЕКУРСИВНЫЙ-ОБХОД(p) | 3.__________ РЕКУРСИВНЫЙ-ОБХОД(<math>p</math>) | ||
_______'''все''' | _______'''все''' | ||
| Строка 39: | Строка 40: | ||
'''конец''' | '''конец''' | ||
==Литература== | |||
* Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003, 1104 С. | |||
Текущая версия от 23:15, 14 декабря 2011
З а д а ч а
О б ъ е к т ы. Ориентированный граф [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 С.