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

Задача

О б ъ е к т ы. Ориентированный граф 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 \in ИСХОД(q) }[/math];

5.__________ пока [math]\displaystyle{ S \neq \empty }[/math] цикл

6.__________________[math]\displaystyle{ q }[/math] := КОНЕЦ([math]\displaystyle{ S }[/math]);

7.________________________если НЕПОМЕЧЕНА([math]\displaystyle{ q }[/math]) то начать [math]\displaystyle{ L }[/math] все

____________ все

_____ конец

все

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

[math]\displaystyle{ \empty, \{ u1,u2,u3 \}, \{ u2,u3 \}, \{ u2,u3,u4 \}, \{u3,u4 \},\{ u4 \}, \{ u6,u5,u4 \}, \{ u5,u4 \}, \{ u4\}, \empty }[/math]

а вершины графа посещаются в следующей последовательности: [math]\displaystyle{ p_0, p_2, p_1 }[/math]

С в о й с т в а.

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

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

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