1023
правки
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) (→Задача) |
||
(не показано 7 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
== Задача == | == Задача == | ||
О б ъ е к т ы. Ориентированный граф G, каждая вершина которого может находиться в одном из двух состояний: "помечена", "непомечена". | О б ъ е к т ы. [[Ориентированный граф]] <math>G</math>, каждая [[вершина]] которого может находиться в одном из двух состояний: "помечена", "непомечена". | ||
О п е р а ц и и. Для любой вершины p графа G операция ПОМЕТИТЬ(p) выполнима, если p находится в состоянии "непомечена", и при своем выполнении переводит p в состояние "помечена", а предикат НЕПОМЕЧЕНА(p) ложен, если p находится в состоянии "помечена". | О п е р а ц и и. Для любой вершины <math>p</math> графа <math>G</math> операция ПОМЕТИТЬ(<math>p</math>) выполнима, если <math>p</math> находится в состоянии "непомечена", и при своем выполнении переводит <math>p</math> в состояние "помечена", а предикат НЕПОМЕЧЕНА(<math>p</math>) ложен, если p находится в состоянии "помечена". | ||
Д а н о. Задана вершина <math>p_0</math> такая, что каждая вершина графа G, достижимая из <math>p_0</math>, находится в состоянии "непомечена". | Д а н о. Задана вершина <math>p_0</math> такая, что каждая вершина графа <math>G</math>, достижимая из <math>p_0</math>, находится в состоянии "непомечена". | ||
Т р е б у е т с я. Перевести в состояние "помечена" все вершины графа G, достижимые из <math>p_0</math>. | Т р е б у е т с я. Перевести в состояние "помечена" все вершины графа <math>G</math>, достижимые из <math>p_0</math>. | ||
З а м е ч а н и е. Предполагается, что процедура ПОМЕТИТЬ(p) при своем выполнении осуществляет определенные действия с информационным содержимым вершины p, для реализации которых и производится обход графа. | З а м е ч а н и е. Предполагается, что процедура ПОМЕТИТЬ(<math>p</math>) при своем выполнении осуществляет определенные действия с информационным содержимым вершины <math>p</math>, для реализации которых и производится обход графа. | ||
== Решение == | == Решение == | ||
Строка 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]] | |||
При выполнении ЛЕС(<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> | ||
Строка 53: | Строка 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 С. |