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

[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]

№г /. [Просмотр вершины] Set /-«-/+1; and VISIT (V)/• Шаг 2. [Поиск непросмотренной вершины, смежной с V] For всех вершин W, смелшых с V, do шаг 3 od; and RETURN. Шаг 3. [Просмотрена ли вершина Г?] И VISIT (Г) не определена then set TT-{V, W)); and CALL DFS(r) fi.

Предложим интуитивное объяснение работы алгоритма. Переменная V показывает текущую вершину, т. е. вершину, в которой мы сейчас находимся. Алгоритм DFS работает, проходя произвольное ребро

ADJ NEXT


INPUT 2,4 3,1 1,5 3,4 1,4 S,2

J

Рис. 3.5.2. Представление сети связанньми списками: (а) сеть, (б) ребра, (в) связанные списки.

ИЗ V, скажем, к вершине W. Если вершина W ранее не была просмотрена, алгоритм рекурсивно обращается к себе самому при помощи оператора CALL DFS(W). Если же, наоборот, вершина W уже просмотрена, алгоритм испытывает другое ребро из V, всегда пытаясь отьюкать непросмотренные вершины для просмотра на следующем шаге. Если непросмотренных вершин, смежных с V, не обнаружено, алгоритм возвращается в вершину, из которой он опустился в V, и проверяет новые ребра отсюда. Если сеть связна, алгоритм DFS «проверит» каждое ребро дважды и найдет остовное дерево.

Теперь проследим шаги алгоритма DFS, работающего на графе рис. 3.5.2, начиная (произвольно) с вершины 4. Первое обращение к алгоритму - DFS(4).

Ребра сети G пройдены в порядке а b с d е f, как показано на рис. 3.5.3, а; окончательное остовное дерево, найденное алгоритмом DFS, приведено на рис. 3.5.3, б.

) Здесь знак -f означает добавление элемента к множеству,- Прим, ред.



DFS(4) V=4.T=ftI = 0 1=1

VISIT(4) = 1 W=i

T=T+(4.1) ШАГ 5.

•DFSd) V=i

V1S1T(1)=2 W = 4 W=5

T=T+(1,5)

DFS(5)

V = 5 1 = 3

V1S1T(5) = 3 W = 2

T=T+(5,2)

DFS(2)

• V=2

1 = 4

V1S1T(2)=4 W = 5 W=4 RETURN to DFS(5) W=1 RETUBN to DFS(n W=3 T=T + (1,3) DFS(3)

V = 3. 1 = 5

V1S1T(3).= 5 W=4 W = 1 RETUBN to DPS(1) RETURN to DFS(4) . W=3 W=2 RETURN

Для реализации алгоритма DFS удобно писать программу на таких языках программирования, как Алгол или ПЛ/1, в которых можно производить рекурсивные обращения к процедурам. Если вы знакомы с таким языком, советуем вам это сделать.

Мы представим реализацию алгоритма DFS на Фортране, так как она поможет проиллюстрировать: (1) создание и использование связанного списка представления сети; (2) использование стека и (3) метод, которым может быть итеративно реализован рекурсивный алгоритм.

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



тельность операций, выполняемых алгоритмом DFS для нахождения остовного дерева графа G (рис. 3.5.2), начиная с вершины 4.

Каждый раз, когда мы производим рекурсивное обращение (CALL), например, к DPS(5), прерывается процесс проверки всех вершин, смежных с вершиной V=\, и заменяется значение V (например, V=b).


Рис. 3.5.3. Остовное дерево, найденное алгоритмом DFS,

После возврата (RETURN) из обращения (CALL) к DFS(5) нам надо как-то запомнить, где мы были, а были мы в вершине 1 и проверили только что следующую вершину 1=5, смежную с V.

Чтобы запомнить местоположение в тот момент, когда мы производили обращение (CALL) к DFS(5), мы запоминаем текущие значения V и W в стеке (т. е. V=l и W=5). Значения V и W называются текущей внешней средой алгоритма DFS. Если во время выполнения обращения (CALL) к DFS(5) произведено другое обращение [например, к DFS(2)], то новая текущая внешняя среда помещается в верхнюю часть стека (именно V=5 и W=2). При каждом возврате (RETURN) из процедуры, к которой мы обращались, берем самую последнюю внешнюю среду из верхней части стека и с ее помощью восстанавливаем предьщущие значения V к W.

Рис. 3.5.4 показывает, что содержалось бы в стеке в этом примере. На рис. 3.5.5 показана реализация на Фортране рекурсивного алгоритма DFS. Заметим, что подпрограмма SUBROUTINE DFS хранит в стеке значения переменной V и указателя К на вершину W вместо самой вершины W.

Относительно алгоритма DPS нужно сделать несколько дополнительных замечаний. Первое касается его названия: почему он называется поиском в глубину? Этот алгоритм на самом деле является алгоритмом с отходом (см. разд. 3.3), осуществляющим поиск по древовидной структуре таким образом, чтобы как можно быстрее найти «нижнюю» вершину. На рис. 3.5.6 показана древовидная структура, исследованная алгоритмом DPS для случая, изображенного на рис. 3.5.2; обведенные окружностями номера показывают порядок,



[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.0012