Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [ 48 ] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

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

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? Или это можно установить не во всех случаях? Предлагаем вам проверить оба алгоритма, чтобы ответить на эти вопросы.

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

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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [ 48 ] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0009