1023
правки
Рекурсивный алгоритм обхода графа в глубину: различия между версиями
Перейти к навигации
Перейти к поиску
Рекурсивный алгоритм обхода графа в глубину (посмотреть исходный код)
Версия от 23:02, 14 декабря 2011
, 14 декабря 2011нет описания правки
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 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>) | ||
_______'''все''' | _______'''все''' | ||