с ПРОСМОТР ВСЕХ ВЕРШИН.

00 too I S 1.Р

с Vr это 1-я НОВАЯ ВЕРШИНА.

VISIT(V) = I к i V

с СЛЕДУЮЩАЯ СМЕЖНАЯ С V ВЕРШИНА.

£00 К s WEXT(K)

с ЕСТЬ ЛИ ЕЩЕ СМЕЖНЫЕ С V ВЕРШИНЫ?

IF { К .GT. О ) GOTO 300

с ОСТАЛОСЬ ли ЧТО-НИБУДЬ В СТЕКЕ?-

IF •( PTR .ЕО. О I RETURN

С УДАЛЕНИЕ ТРЕХ ВЕРХНИХ ЭЛЕМЕНТОВ

С ИЗ СТЕКА.

V = STOREIPTR) К = ST0BE(PTR-1I STORE(PTR) = О ST0RE(PTR-1I = О PTR = PTR - г

GOTO гоо

с СЛЕДУЮЩАЯ СМЕ.ЖИАЯ С V ВЕРШИНА.

300 U = ADJIKI

с ПРОВЕРЕНА ЛИ ВЕРШИНА W?

IF { visiT(W) .GT. О I GOTO гоо

с ПРИБАВЛЕНИЕ РЕБРА VX,

С К ОСТОВНОМУ ДЕРЕВУ.

TREE(Т.II = V

TREE(Tt2) = W

I = Т + t

с ИМЕЕМ ли мы УЖЕ ОСТОВНОЕ

С ДЕРЕВО?

IF ( Т .EQ. Р ) RETURM

С ЗАНОСИМ К, V И и В СТЕК

с и ПРОВЕРЯЕМ W.

STORe<PTR+Xl = к STORE(PTR+21 = V

PTR = prR + г V = w

400 CONTIWC

с этот ОПЕРАТОР НИКОГДА НЁ ДОЛЖЕН ДОСТИГАТЬСЯ.

Vr1TEI6,1000> . 1000 F0RMAT(lHli25H ERROR IN SUBROUTINE DFS.J RETURN -

Цачада

TIG)

последовательно просматриваются все вершины дерева на уровне k, затем все вершины на уровне кЛ-\ и т. д. При отыскании остовного дерева в сети G, изображенной на рис. 3.5.2, методом поиска в ширину

было бы построено такое дерево, как на рис. 3.5.7.

Теперь для полноты изложения опишем алгоритм отыскания остовного дерева в сети G методом поиска в ширину (алгоритм BFS).

Алгори™ BFS начинает работу с произвольной вершины V и добавляет к списку LIST все смежные с V, еш,е не просмотренные вершины, отмечая каждую из них «просмотрена» в момент, когда она прибавляется к LIST. На каждой из последовательных итераций алгоритма для следующей вершины W из LIST проверяется, нет ли непросмотренных смежных с ней вершин, которые можно добавить к LIST. Как только к LIST добавляется новая вершина, ребро от нее к текущей, уже проверенной вершине добавляется к остовному дереву.

Algorithm BFS {Поиск в ширину). Поиск остовного дерева Т в связной сети G, вершины которой перенуме-e/!ifm рованы 1, 2, . . ., М. Алго-4 ритм начинает работу в вер-3 шине U; VISIT (W)=l озна-I чает, что вершина W уже просмотрена; VISIT (1г)=0, если W не просмотрена.

Рис 3.5.6. Дерево поиска в глубину, построенное алгоритмом DFS.

Ротло здесь

Шаг 0. [Инициализация] Set 1; I; for /с 1 to

М do set USTiK) 0; and VISIT (/<:) -e-0 od;set LIST(l)f/; VISIT(t/)l; and

Рис 3.5.7. Дерево поиска в ширину, построенное алгоритмом BFS.

Шаг 1. [Проверка всех вершин] While LIST(/)#0 do through шаг 3 od; and STOP.

Шаг 2. [Следующая вершина] Set V LIST (J); and J J+ + 1.

Шаг 3. [Поиск всех непросмотренных смежных с V вершин] For всех вершин W, смежных с V, do шаг 4 od. Шаг 4. [Добавление непросмотренной вершины в LIST, а ребра -к Т] If VISIT (W7)=0 then set +1; LIST(/)ir; VISIT (IT) 1; and T-T+iV, W) ii.

Начат sBecb

1 2 3 4 Б

Вектор 4 4 4 0 2

a g в

Рис. 3.5.8. Векторное представление остовного дерева.

Теперь покажем простую, нерекурсивную реализацию алгоритма BFS. Выход VECTOR подпрограммы BFS - это рекурсивное представление остовного дерева Т сети G, которое обсуждалось в конце разд. 2.3. На рис. 3.5.8 показано это представление Т. Полная программа нахождения остовного дерева, использующая поиске ширину, представлена на рис. 3.5.9.

Доказательство правильности и анализ сложности алгоритма BFS можно провести точно так же, как и для алгоритма DFS. Оставляем это читателю. Рассмотрите также следующий вопрос: какой алгоритм предпочтительнее, DFS или BFS? Или это можно установить не во всех случаях? Предлагаем вам проверить оба алгоритма, чтобы ответить на эти вопросы.

Рекурсия в сравнении с итерацией

Полное рассмотрение преимуществ и недостатков рекурсивных и итерационных алгоритаов лежит за пределами этой книги. Так же обстоит дело и с рассмотрением связей между рекурсией и итерацией, представляющих глубокий теоретический интерес. Кое-кто утверждал, что любой рекурсивный алгоритм следует преобразовывать в эквивалентный итеративный алгори™. Другие утверждают, что это не всегда имеет смысл делать.