ВУЗ:
Составители:
Рубрика:
else b:=not new [U[t]
↑
.dat];
while b do
begin
U[t]:=U[t]
↑
.next;
if U[t]=nil then b:=false
else b:=not new [U[t]
↑
.dat]
end;
if U[t]
≠
nil then (найдена новая нерассмотренная
вершина)
begin
w:=U[t]
↑
.dat; stack
←
w;
рассмотреть w; new[w]:=false
end;
else (вершина t рассмотрена)
t
←
stack (удалить верхний элемент стека)
end
end
Пояснение к алгоритму.
Начинаем из вершины v. Пусть на не-
котором шаге мы попали в вершину u. Идем далее из вершины u в
вершину w, смежную с u. Если w уже рассматривалась, то возвра-
щаемся в u и идем в другую смежную с ней вершину. Если же w
еще не рассматривалась, то применяем к ней описанную выше
процедуру. Процесс завершается при попытке вернуться назад из
начальной вершины v.
Пример 11.1.
Пояснения к алгоритму будем давать на примере
графа, изображенного на рисунке.
5 (6)
4 (5)
8 (8)
6 (3)
3 (4)
7 (7)
2 (2)
1 (1)
Порядок прохождения
вершин указан на рисунке
в круглых скобках рядом с
номером вершины.
41
Страницы
- « первая
- ‹ предыдущая
- …
- 39
- 40
- 41
- 42
- 43
- …
- следующая ›
- последняя »
