1023
правки
Общий алгоритм обхода графа с запоминанием дуг: различия между версиями
Материал из WEGA
Общий алгоритм обхода графа с запоминанием дуг (посмотреть исходный код)
Версия от 11:57, 19 декабря 2011
, 19 декабря 2011→Задача
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) (→Задача) |
||
| (не показаны 4 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Задача == | == Задача == | ||
О б ъ е к т ы. Ориентированный граф <math>G</math>, каждая вершина которого может находиться в одном из двух состояний: "помечена", "непомечена". | О б ъ е к т ы. [[Ориентированный граф]] <math>G</math>, каждая [[вершина]] которого может находиться в одном из двух состояний: "помечена", "непомечена". | ||
О п е р а ц и и. Для любой вершины <math>p</math> графа <math>G</math> операция ПОМЕТИТЬ(<math>p</math>) выполнима, если <math>p</math> находится в состоянии "непомечена", и при своем выполнении переводит <math>p</math> в состояние "помечена", а предикат НЕПОМЕЧЕНА(<math>p</math>) ложен, если p находится в состоянии "помечена". | О п е р а ц и и. Для любой вершины <math>p</math> графа <math>G</math> операция ПОМЕТИТЬ(<math>p</math>) выполнима, если <math>p</math> находится в состоянии "непомечена", и при своем выполнении переводит <math>p</math> в состояние "помечена", а предикат НЕПОМЕЧЕНА(<math>p</math>) ложен, если p находится в состоянии "помечена". | ||
| Строка 16: | Строка 16: | ||
'''проц''' ЛЕС(<math>p_0</math>: ''вершина'') = | '''проц''' ЛЕС(<math>p_0</math>: ''вершина'') = | ||
::<math>S</math> : ''семейство дуг'' = <math>\empty</math>; | |||
::<math>q</math>: ''вершина'' = <math>p_0</math>; | |||
::<math>L</math> : '''начало''' ПОМЕТИТЬ(q); | |||
::::<math>S \Leftarrow \overline{\ni} </math>ИСХОД<math>\,(q)</math>; | |||
:::: '''пока''' <math>S \neq \empty </math> '''цикл''' | |||
::::::<math>q</math> := КОНЕЦ(<math>\overline{\ni}S</math>); | |||
::::::'''если''' НЕПОМЕЧЕНА(<math>q</math>) '''то начать''' <math>L</math> '''все''' | |||
:::: '''все''' | |||
:: '''конец''' | |||
'''все''' | '''все''' | ||
П о я с н е н и я. Рассмотрим граф | П о я с н е н и я. Рассмотрим следующий граф | ||
[[Файл:2-47.jpg]] | [[Файл:2-47.jpg]] | ||
При выполнении ЛЕС(<math>p_0</math>) состояние S меняется следующим образом: | При выполнении ЛЕС(<math>p_0</math>) состояние <math>S</math> меняется следующим образом: | ||
<math>\empty, \{ u_1,u_2,u_3 \}, \{ u_2,u_3 \}, \{ u_2,u_3,u_4 \}, \{u_3,u_4 \},\{ u_4 \}, \{ u_6,u_5,u_4 \}, \{ u_5,u_4 \}, \{ u_4\}, \empty</math> | <math>\empty, \{ u_1,u_2,u_3 \}, \{ u_2,u_3 \}, \{ u_2,u_3,u_4 \}, \{u_3,u_4 \},\{ u_4 \}, \{ u_6,u_5,u_4 \}, \{ u_5,u_4 \}, \{ u_4\}, \empty</math> | ||
| Строка 57: | Строка 55: | ||
3. Если <math>S</math> является стеком, то процедура помечает вершины графа <math>G</math>, достижимые из <math>p_0</math>, в порядке поиска в глубину, а если <math>S</math> — очередь, то вершины помечаются в порядке поиска в ширину. | 3. Если <math>S</math> является стеком, то процедура помечает вершины графа <math>G</math>, достижимые из <math>p_0</math>, в порядке поиска в глубину, а если <math>S</math> — очередь, то вершины помечаются в порядке поиска в ширину. | ||
==Литература== | |||
* Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003, 1104 С. | |||
