Общий алгоритм обхода графа с запоминанием дуг: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «== Задача == О б ъ е к т ы. Ориентированный граф G, каждая вершина которого может находиться в …»)
 
 
(не показано 8 промежуточных версий этого же участника)
Строка 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>: ''вершина'') =  


1.____<math>S</math> : ''семейство дуг'' = <math>\empty</math>;  
::<math>S</math> : ''семейство дуг'' = <math>\empty</math>;  


2.____<math>q</math>: ''вершина'' = <math>p_0</math>;  
::<math>q</math>: ''вершина'' = <math>p_0</math>;  


3.____<math>L</math> : '''начало''' ПОМЕТИТЬ(q);  
::<math>L</math> : '''начало''' ПОМЕТИТЬ(q);  


4.__________<math>S \in ИСХОД(q)</math>;  
::::<math>S \Leftarrow \overline{\ni} </math>ИСХОД<math>\,(q)</math>;  


5.__________ '''пока''' <math>S \neq \empty </math> '''цикл'''  
:::: '''пока''' <math>S \neq \empty </math> '''цикл'''  


6.__________________<math>q</math> := КОНЕЦ(<math> S</math>);  
::::::<math>q</math> := КОНЕЦ(<math>\overline{\ni}S</math>);  


7.________________________'''если''' НЕПОМЕЧЕНА(<math>q</math>) '''то начать''' <math>L</math> '''все'''
::::::'''если''' НЕПОМЕЧЕНА(<math>q</math>) '''то начать''' <math>L</math> '''все'''


____________ '''все'''
:::: '''все'''


_____ '''конец'''  
:: '''конец'''  


'''все'''  
'''все'''  


П о я с н е н и я. Рассмотрим граф, изображенный на рис. При выполнении ЛЕС(p0) состояние S меняется следующим образом:
П о я с н е н и я. Рассмотрим следующий граф  


<math>\empty, \{ u1,u2,u3 \}, \{ u2,u3 \}, \{ u2,u3,u4 \}, \{u3,u4 \},\{ u4 \}, \{ u6,u5,u4 \}, \{ u5,u4 \}, \{ u4\}, \empty</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>p_0, p_2, p_1</math>
<math>p_0, p_2, p_1</math>


С в о й с т в а.  
С в о й с т в а.  


1. Временная сложность алгоритма составляет O(k) времени, где k — число дуг графа G, достижимых из вершины <math>p_0</math>.  
1. Временная сложность алгоритма составляет <math>O(k)</math> времени, где <math>k</math> — число дуг графа <math>G</math>, достижимых из вершины <math>p_0</math>.
 
2. Алгоритм изменяет состояние непомеченной вершины <math>q</math> тогда и только тогда, когда <math>q</math> достижима из <math>p_0</math>.
 
3. Если <math>S</math> является стеком, то процедура помечает вершины графа <math>G</math>, достижимые из <math>p_0</math>, в порядке поиска в глубину, а если <math>S</math> — очередь, то вершины помечаются в порядке поиска в ширину.


2. Алгоритм изменяет состояние непомеченной вершины q тогда и только тогда, когда q достижима из p.
==Литература==


3. Если S является стеком, то процедура помечает вершины графа G, достижимые из <math>p_0</math>, в порядке поиска в глубину, а если S — очередь, то вершины помечаются в порядке поиска в ширину.
* Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003, 1104 С.

Текущая версия от 11:57, 19 декабря 2011

Задача

О б ъ е к т ы. Ориентированный граф [math]\displaystyle{ G }[/math], каждая вершина которого может находиться в одном из двух состояний: "помечена", "непомечена".

О п е р а ц и и. Для любой вершины [math]\displaystyle{ p }[/math] графа [math]\displaystyle{ G }[/math] операция ПОМЕТИТЬ([math]\displaystyle{ p }[/math]) выполнима, если [math]\displaystyle{ p }[/math] находится в состоянии "непомечена", и при своем выполнении переводит [math]\displaystyle{ p }[/math] в состояние "помечена", а предикат НЕПОМЕЧЕНА([math]\displaystyle{ p }[/math]) ложен, если p находится в состоянии "помечена".

Д а н о. Задана вершина [math]\displaystyle{ p_0 }[/math] такая, что каждая вершина графа [math]\displaystyle{ G }[/math], достижимая из [math]\displaystyle{ p_0 }[/math], находится в состоянии "непомечена".

Т р е б у е т с я. Перевести в состояние "помечена" все вершины графа [math]\displaystyle{ G }[/math], достижимые из [math]\displaystyle{ p_0 }[/math].

З а м е ч а н и е. Предполагается, что процедура ПОМЕТИТЬ([math]\displaystyle{ p }[/math]) при своем выполнении осуществляет определенные действия с информационным содержимым вершины [math]\displaystyle{ p }[/math], для реализации которых и производится обход графа.

Решение

М е т о д.

проц ЛЕС([math]\displaystyle{ p_0 }[/math]: вершина) =

[math]\displaystyle{ S }[/math] : семейство дуг = [math]\displaystyle{ \empty }[/math];
[math]\displaystyle{ q }[/math]: вершина = [math]\displaystyle{ p_0 }[/math];
[math]\displaystyle{ L }[/math] : начало ПОМЕТИТЬ(q);
[math]\displaystyle{ S \Leftarrow \overline{\ni} }[/math]ИСХОД[math]\displaystyle{ \,(q) }[/math];
пока [math]\displaystyle{ S \neq \empty }[/math] цикл
[math]\displaystyle{ q }[/math] := КОНЕЦ([math]\displaystyle{ \overline{\ni}S }[/math]);
если НЕПОМЕЧЕНА([math]\displaystyle{ q }[/math]) то начать [math]\displaystyle{ L }[/math] все
все
конец

все

П о я с н е н и я. Рассмотрим следующий граф

2-47.jpg

При выполнении ЛЕС([math]\displaystyle{ p_0 }[/math]) состояние [math]\displaystyle{ S }[/math] меняется следующим образом:

[math]\displaystyle{ \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]\displaystyle{ p_0, p_2, p_1 }[/math]

С в о й с т в а.

1. Временная сложность алгоритма составляет [math]\displaystyle{ O(k) }[/math] времени, где [math]\displaystyle{ k }[/math] — число дуг графа [math]\displaystyle{ G }[/math], достижимых из вершины [math]\displaystyle{ p_0 }[/math].

2. Алгоритм изменяет состояние непомеченной вершины [math]\displaystyle{ q }[/math] тогда и только тогда, когда [math]\displaystyle{ q }[/math] достижима из [math]\displaystyle{ p_0 }[/math].

3. Если [math]\displaystyle{ S }[/math] является стеком, то процедура помечает вершины графа [math]\displaystyle{ G }[/math], достижимые из [math]\displaystyle{ p_0 }[/math], в порядке поиска в глубину, а если [math]\displaystyle{ S }[/math] — очередь, то вершины помечаются в порядке поиска в ширину.

Литература

  • Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003, 1104 С.
Источник — http://pco.iis.nsk.su/wega/index.php?title=Общий_алгоритм_обхода_графа_с_запоминанием_дуг&oldid=10148