Аноним

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

Материал из WEGA

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

Версия от 11:57, 19 декабря 2011

57 байт убрано ,  19 декабря 2011
→‎Задача
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
== Задача ==
== Задача ==


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


О п е р а ц и и. Для любой вершины <math>p</math> графа <math>G</math> операция ПОМЕТИТЬ(<math>p</math>) выполнима, если <math>p</math> находится в состоянии "непомечена", и при своем выполнении переводит <math>p</math> в состояние "помечена", а предикат НЕПОМЕЧЕНА(<math>p</math>) ложен, если p находится в состоянии "помечена".  
О п е р а ц и и. Для любой вершины <math>p</math> графа <math>G</math> операция ПОМЕТИТЬ(<math>p</math>) выполнима, если <math>p</math> находится в состоянии "непомечена", и при своем выполнении переводит <math>p</math> в состояние "помечена", а предикат НЕПОМЕЧЕНА(<math>p</math>) ложен, если p находится в состоянии "помечена".  
Строка 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  \Leftarrow \overline{\ni} </math>ИСХОД(<math>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>\overline{\ni}S</math>);  
::::::<math>q</math> := КОНЕЦ(<math>\overline{\ni}S</math>);  


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


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


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


'''все'''  
'''все'''  
Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10109...10148