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

Перейти к навигации Перейти к поиску
(Новая страница: «== Задача == О б ъ е к т ы. Ориентированный граф G, каждая вершина которого может находиться в …»)
 
Строка 22: Строка 22:
3.____<math>L</math> : '''начало''' ПОМЕТИТЬ(q);  
3.____<math>L</math> : '''начало''' ПОМЕТИТЬ(q);  


4.__________<math>S \in ИСХОД(q)</math>;  
4.__________<math>S ИСХОД(q)</math>;  


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


6.__________________<math>q</math> := КОНЕЦ(<math>  S</math>);  
6.__________________Пусть u - произвольная дуга взятая из S;


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


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


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


а вершины графа посещаются в следующей последовательности:  
а вершины графа посещаются в следующей последовательности:
<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. Алгоритм изменяет состояние непомеченной вершины q тогда и только тогда, когда q достижима из p.  
2. Алгоритм изменяет состояние непомеченной вершины <math>q</math> тогда и только тогда, когда <math>q</math> достижима из <math>p_0</math>.  


3. Если S является стеком, то процедура помечает вершины графа G, достижимые из <math>p_0</math>, в порядке поиска в глубину, а если S — очередь, то вершины помечаются в порядке поиска в ширину.
3. Если <math>S</math> является стеком, то процедура помечает вершины графа <math>G</math>, достижимые из <math>p_0</math>, в порядке поиска в глубину, а если <math>S</math> — очередь, то вершины помечаются в порядке поиска в ширину.
Источник — http://pco.iis.nsk.su/wega/index.php/Общий_алгоритм_обхода_графа_с_запоминанием_дуг