Общий алгоритм обхода графа с запоминанием дуг: различия между версиями
Перейти к навигации
Перейти к поиску
KVN (обсуждение | вклад) |
KVN (обсуждение | вклад) (→Задача) |
||
| Строка 1: | Строка 1: | ||
== Задача == | == Задача == | ||
О б ъ е к т ы. Ориентированный граф G, каждая вершина которого может находиться в одном из двух состояний: "помечена", "непомечена". | О б ъ е к т ы. Ориентированный граф <math>G</math>, каждая вершина которого может находиться в одном из двух состояний: "помечена", "непомечена". | ||
О п е р а ц и и. Для любой вершины p графа G операция ПОМЕТИТЬ(p) выполнима, если p находится в состоянии "непомечена", и при своем выполнении переводит p в состояние "помечена", а предикат НЕПОМЕЧЕНА(p) ложен, если p находится в состоянии "помечена". | О п е р а ц и и. Для любой вершины <math>p</math> графа <math>G</math> операция ПОМЕТИТЬ(<math>p</math>) выполнима, если <math>p</math> находится в состоянии "непомечена", и при своем выполнении переводит <math>p</math> в состояние "помечена", а предикат НЕПОМЕЧЕНА(<math>p</math>) ложен, если p находится в состоянии "помечена". | ||
Д а н о. Задана вершина <math>p_0</math> такая, что каждая вершина графа G, достижимая из <math>p_0</math>, находится в состоянии "непомечена". | Д а н о. Задана вершина <math>p_0</math> такая, что каждая вершина графа <math>G</math>, достижимая из <math>p_0</math>, находится в состоянии "непомечена". | ||
Т р е б у е т с я. Перевести в состояние "помечена" все вершины графа G, достижимые из <math>p_0</math>. | Т р е б у е т с я. Перевести в состояние "помечена" все вершины графа <math>G</math>, достижимые из <math>p_0</math>. | ||
З а м е ч а н и е. Предполагается, что процедура ПОМЕТИТЬ(p) при своем выполнении осуществляет определенные действия с информационным содержимым вершины p, для реализации которых и производится обход графа. | З а м е ч а н и е. Предполагается, что процедура ПОМЕТИТЬ(<math>p</math>) при своем выполнении осуществляет определенные действия с информационным содержимым вершины <math>p</math>, для реализации которых и производится обход графа. | ||
== Решение == | == Решение == | ||