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

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

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

Д а н о. Задана вершина <math>p_0</math> такая, что каждая вершина графа G, достижимая из <math>p_0</math>, находится в состоянии "непомечена".  

Т р е б у е т с я. Перевести в состояние "помечена" все вершины графа G, достижимые из <math>p_0</math>.  

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

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

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

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

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

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

6.__________________Пусть u - произвольная дуга взятая из S;

7.__________________<math>q</math> := КОНЕЦ(<math>u</math>);

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

____________ '''все'''

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

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