Общий алгоритм обхода графа с запоминанием дуг: различия между версиями
KVN (обсуждение | вклад) (Новая страница: «== Задача == О б ъ е к т ы. Ориентированный граф G, каждая вершина которого может находиться в …») |
KVN (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
3.____<math>L</math> : '''начало''' ПОМЕТИТЬ(q); | 3.____<math>L</math> : '''начало''' ПОМЕТИТЬ(q); | ||
4.__________<math>S | 4.__________<math>S ИСХОД(q)</math>; | ||
5.__________ '''пока''' <math>S \neq \empty </math> '''цикл''' | 5.__________ '''пока''' <math>S \neq \empty </math> '''цикл''' | ||
6. | 6.__________________Пусть u - произвольная дуга взятая из S; | ||
7. | 7.__________________<math>q</math> := КОНЕЦ(<math>u</math>); | ||
7.__________________'''если''' НЕПОМЕЧЕНА(<math>q</math>) '''то начать''' <math>L</math> '''все''' | |||
____________ '''все''' | ____________ '''все''' | ||
| Строка 38: | Строка 40: | ||
П о я с н е н и я. Рассмотрим граф, изображенный на рис. При выполнении ЛЕС(p0) состояние S меняется следующим образом: | П о я с н е н и я. Рассмотрим граф, изображенный на рис. При выполнении ЛЕС(p0) состояние S меняется следующим образом: | ||
<math>\empty, \{ | <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 достижима из | 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> — очередь, то вершины помечаются в порядке поиска в ширину. | ||
Версия от 00:05, 16 декабря 2011
Задача
О б ъ е к т ы. Ориентированный граф G, каждая вершина которого может находиться в одном из двух состояний: "помечена", "непомечена".
О п е р а ц и и. Для любой вершины p графа G операция ПОМЕТИТЬ(p) выполнима, если p находится в состоянии "непомечена", и при своем выполнении переводит p в состояние "помечена", а предикат НЕПОМЕЧЕНА(p) ложен, если p находится в состоянии "помечена".
Д а н о. Задана вершина [math]\displaystyle{ p_0 }[/math] такая, что каждая вершина графа G, достижимая из [math]\displaystyle{ p_0 }[/math], находится в состоянии "непомечена".
Т р е б у е т с я. Перевести в состояние "помечена" все вершины графа G, достижимые из [math]\displaystyle{ p_0 }[/math].
З а м е ч а н и е. Предполагается, что процедура ПОМЕТИТЬ(p) при своем выполнении осуществляет определенные действия с информационным содержимым вершины p, для реализации которых и производится обход графа.
Решение
М е т о д.
проц ЛЕС([math]\displaystyle{ p_0 }[/math]: вершина) =
1.____[math]\displaystyle{ S }[/math] : семейство дуг = [math]\displaystyle{ \empty }[/math];
2.____[math]\displaystyle{ q }[/math]: вершина = [math]\displaystyle{ p_0 }[/math];
3.____[math]\displaystyle{ L }[/math] : начало ПОМЕТИТЬ(q);
4.__________[math]\displaystyle{ S ИСХОД(q) }[/math];
5.__________ пока [math]\displaystyle{ S \neq \empty }[/math] цикл
6.__________________Пусть u - произвольная дуга взятая из S;
7.__________________[math]\displaystyle{ q }[/math] := КОНЕЦ([math]\displaystyle{ u }[/math]);
7.__________________если НЕПОМЕЧЕНА([math]\displaystyle{ q }[/math]) то начать [math]\displaystyle{ L }[/math] все
____________ все
_____ конец
все
П о я с н е н и я. Рассмотрим граф, изображенный на рис. При выполнении ЛЕС(p0) состояние S меняется следующим образом:
[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] — очередь, то вершины помечаются в порядке поиска в ширину.